预估分数：
100
+
100
+
[
0
,
20
]
+
100
=
[
300
,
320
]
100+100+[0,20]+100=[300,320]
100+100+[0,20]+100=[300,320]
实际分数：
100
+
100
+
10
+
100
=
310
100+100+10+100=310
100+100+10+100=310
只是粗略观察表就急于写决策单调性优化，写完后才发现有些位置不单调，以后需要用程序 c h e c k check check，而不是自己肉眼看
没想到人类智慧的结论：直径可以衡量树的减少
感觉学到了一个套路
不说了，就一个二分 + d f s +dfs +dfs 的事
感觉挺套路的，先写一个暴力的
d
p
dp
dp（需要费用提前计算，否则不好优化）
因为有最大最小值，所以用单调栈 + 线段树优化
有一个插曲是我打表转移点，看了前二十个，以为是单调的，然后写了个决策单调性，发现
W
A
WA
WA 了，然后才发现打表中有几个转移点不单调！！！
神仙博弈题
考虑树在不断减小的过程中，用什么来衡量减小的量？直径！
可以发现，当直径长度
>
2
>2
>2 时，每次操作可以让直径长度
−
1
-1
−1 或
−
2
-2
−2，考虑问题变成了一堆石子，每次可以取
1
/
2
1/2
1/2 个，求先手必胜还是后手必胜
这就很
e
a
s
y
easy
easy 了，对于
%
3
\%3
%3 的余数分类讨论即可
现在考虑维护直径，有一个很常用我却想不到 的方法是用线段树
因为直径是可以合并的
考虑到查询的情况只有 3 种不同的
树上两点距离用
r
m
q
rmq
rmq 即可
时间复杂度
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)
#include
for(int i=1;i<=n<<1;i++) st[i][0]=depth[eul[i]];
for(int j=1;j<20;j++) for(int i=1;i+(1<<j)-1<=n<<1;i++) st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
for(int j=1;j<20;j++) for(int i=1;i<=n;i++) up[i][j]=up[up[i][j-1]][j-1];
// cout<
sg.build(1,n,1);
for(int i=1;i<=n;i++){
Node t=sg.query(1,n,1,dfn[i],dfn[i]+siz[i]-1);
f[i]=calc(t.u,t.v);
int l1=1,r1=dfn[i]-1;
int l2=dfn[i]+siz[i],r2=n;
if(l1<=r1&&l2<=r2) t=sg.pushup(sg.query(1,n,1,l1,r1),sg.query(1,n,1,l2,r2));
else if(l1<=r1) t=sg.query(1,n,1,l1,r1);
else t=sg.query(1,n,1,l2,r2);
g[i]=calc(t.u,t.v);
}
// for(int i=1;i<=n;i++) cout<
while(q--){
int x=read(),y=read(),ans;
// cerr<<"+++"<<'\n';
if(x==y) ans=f[1];
//y是x的祖先
else if(dfn[y]<=dfn[x]&&dfn[x]<=dfn[y]+siz[y]-1) ans=g[get_low_anc(y,x)];
else ans=f[y];
if(ans%3==2) puts("Yohane");
else puts("Riko");
}
return 0;
}
首先枚举从
0
0
0 开始顺时针和逆时针到的位置，然后选短的一条走两遍，现在问题便成了一段区间中最多能选多少个数，使它们的和不超过
l
i
m
i
t
limit
limit，这可以用优先队列维护
这样
O
(
n
2
)
O(n^2)
O(n2) 暴力就写完了，打表发现顺时针走到的位置增加时，逆时针走到的最优位置也会增加，这就是决策单调性
考虑用分治的方法解决决策单调性问题，里面用线段树进行维护
时间复杂度
O
(
n
l
o
g
2
n
)
O(nlog^2n)
O(nlog2n)
#include
if(mx<=res) mx=res,bpos=k;
}
for(int k=min(tr,n);k>=max(mid+1,tl);k--) sg.modify(1,n,1,t[k],-1);
// cout<
ans=max(ans,mx);
// cout<
solve(mid+1,r,bpos,tr);
for(int i=max(1ll,l);i<=mid;i++) sg.modify(1,n,1,t[i],-1);
for(int i=min(tr,n);i>bpos;i--) sg.modify(1,n,1,t[i],1);
solve(l,mid-1,tl,bpos);
for(int i=min(tr,n);i>bpos;i--) sg.modify(1,n,1,t[i],-1);
}
signed main(){
freopen("decalcomania.in","r",stdin);
freopen("decalcomania.out","w",stdout);
n=read(),T=read();
for(int i=1;i<=n;i++) d[i]=read(),disc[i]=t[i]=read();
for(int i=1;i<=n;i++) d1[i]=d1[i-1]+d[i];
for(int i=n;i>=1;i--) d2[i]=d2[i+1]+d[i];
sort(disc+1,disc+n+1);
cnt=unique(disc+1,disc+n+1)-disc-1;
for(int i=1;i<=n;i++) t[i]=lower_bound(disc+1,disc+cnt+1,t[i])-disc;
// for(int i=1;i<=n;i++) cout<
solve(0,n,1,n+1);
printf("%lld",ans);
return 0;
}