题解 CF925E 【May Holidays】
mrsrz
2019-12-01 23:21:22
[可能更好的体验](https://mrsrz.github.io/2019/12/01/CF925E/)
提供一种时间复杂度 $O(n\sqrt n)$，空间复杂度 $O(n)$ 的在线分块做法。
~~虽然因为常数大了点跑不过 $O(n\sqrt n\log n)$ 的做法了呐不过空间完爆它哇~~
我们转化一下问题：
每次修改一个节点的颜色，相当于把它到根路径上的所有点的点权 $-1/+1$，然后把自己这个点本身的点权变为无穷大/变回来。然后询问树上点权为负的点的个数。
一个非常简单的思路是对树进行树链剖分后对 dfs 序进行分块，每个块里按节点的点权进行排序。
然后整个块 $+1/-1$ 操作直接打标记，答案二分更新。单点赋值和边界修改的话，暴力改然后重新排序即可。
设块大小为 $S$，那么单次修改的复杂度为 $O(S\log^2 n+\frac{n}{S}\log n)$，这个东西只能平衡到 $O(n\sqrt{n\log n}\log n)$，非常不优秀。
开始对其进行优化。
从边角的暴力修改开始。由于块内本身就排好序了，我们直接在那个排好序的数组里把要修改的数和不用修改的数拿出来，那么此时两个数组依然是有序的。而那些要修改的数，同时增加相同的值，其大小关系不变，仍然有序。然后就是将两个有序数组合并，归并即可。那么单次复杂度就是 $O(S)$。
此时我们已经将单次复杂度优化为 $O(S\log n+\frac{n}{S}\log n)$，可以平衡至 $O(n\sqrt n\log n)$。
开始对整块修改进行优化。我们发现，整块修改时，每次只会增减 $1$。再观察可以发现，本题点权的值域是 $O(n)$ 的，那么一个思路就是把答案扔桶里，每次移动一个位置，然后更新当前答案。这样确实把单次时间复杂度优化至了 $O(\frac n S)$，但其空间复杂度变为了 $O(\frac{n^2}S)$。
考虑如果是一个有序数组，为什么不能记录答案所在的那个点，然后暴力移动？因为会有重复，导致移动的复杂度是错误的。那么我们把重复的缩起来就好了嘛。就是对每个出现过的点权，再记录点权的出现次数，然后就可以记录一个位置，每次 $O(1)$ 移动了。
那么这里就和上面的边角暴力矛盾了：把点权缩起来，怎么知道哪些点要变化？事实上，我们并不关心变化的点的编号，而只想知道变化的点的点权。我们事先开一个桶，记录哪些点权要变化，这个点权有多少个数要变化。然后再扫描排好序的数组，把要变化的位置对应变化的量提取出来。这也是个有序的数组，然后就可以合并辣。注意合并的时候删掉出现次数为 $0$ 的，把点权相同的元素并成一个元素。这样的复杂度还是原来的复杂度。
至此，我们单次的时间复杂度优化至 $O(S\log n+\frac n S)$，总复杂度可平衡至 $O(n\sqrt{n\log n})$。
这玩意还不够优！
考虑利用树链剖分的性质。我们从上往下考虑。每次从重链的某处切换到另一条重链顶的时候，子树大小至少缩小一半。而这条重链长不超过子树大小。
对一条长度为 $k$ 的重链，我们对其进行一次操作的复杂度为 $O(S+\frac k S)$，如果仅就这个 $k$ 而言，其复杂度可以平衡至 $O(\sqrt k)$。
那我们如果对不同的重链，根据其重链长度，使用不同的块大小分块，那么单次操作的复杂度就是 $O(\sqrt n+\sqrt{\frac n 2}+\sqrt{\frac n 4}+\sqrt{\frac n 8}+\dots)=O(\sqrt n)$ 的。
所以总的时间复杂度 $O(n\sqrt n)$，空间复杂度 $O(n)$。
而上述空间复杂度 $O(n\sqrt n)$ 的做法虽然有更小的常数，但无法把那个 $\log$ 卡下来，因为按照上述分法，分成的块的个数是 $O(n)$ 的，你就需要 $O(n^2)$ 的空间复杂度，这显然不能接受。
## Code：
```cpp
#include<iostream>
#include<vector>
#include<cmath>
#include<utility>
#include<algorithm>
using namespace std;
const int N=1e5+5;
struct edge{
int to,nxt;
}e[N];
bool col[N];
int n,m,fa[N],head[N],cnt,dfn[N],idx,top[N],sz[N],son[N],dep[N],bel[N],idfn[N],tail[N];
int t[N];
int all,blocks;
vector<int>tmp;
int tot[600005];
struct Block{
int L,R,len,tag;
vector<int>a;
vector<pair<int,int> >b;
int it,ans;
void re(){
tmp=a;
sort(tmp.begin(),tmp.end());
b.clear();
int v=tmp[0],x=1;
for(int i=1;i<tmp.size();++i)
if(tmp[i]!=v)b.push_back(make_pair(v,x)),x=1,v=tmp[i];else ++x;
b.push_back(make_pair(v,x));
for(int i=1;i<b.size();++i)b[i].second+=b[i-1].second;
it=upper_bound(b.begin(),b.end(),make_pair(-tag,0x3fffffff))-b.begin();
ans=it?b[it-1].second:0;
}
void init(int l,int r){
L=l,R=r;
for(int i=l;i<=r;++i)a.push_back(t[idfn[i]]);
re();
}
void _erase(int val){
vector<pair<int,int> >::iterator pos=lower_bound(b.begin(),b.end(),make_pair(val,0));
for(vector<pair<int,int> >::iterator i=pos+1;i<b.end();++i)--i->second;
--pos->second;
if((pos==b.begin()&&!pos->second)||pos->second==(pos-1)->second)b.erase(pos);
}
void _insert(int val){
vector<pair<int,int> >::iterator pos=lower_bound(b.begin(),b.end(),make_pair(val,0));
for(vector<pair<int,int> >::iterator i=pos;i<b.end();++i)++i->second;
if(pos==b.end()||pos->first!=val){
int ct=(pos==b.begin()?1:(pos-1)->second+1);
b.insert(pos,make_pair(val,ct));
}
}
void add(int id,int x){
all-=ans;
id=id-L;
_erase(a[id]);
_insert(a[id]+=x);
it=upper_bound(b.begin(),b.end(),make_pair(-tag,0x3fffffff))-b.begin();
ans=it?b[it-1].second:0;
all+=ans;
}
void dec(int l,int r){
all-=ans;
l=max(l,L),r=min(r,R);
if(L==l&&r==R){
--tag;
if(it<b.size()&&b[it].first+tag<=0)++it;
ans=it?b[it-1].second:0;
all+=ans;
return;
}else{
static pair<int,int>t1[N],t2[N];int top1=0,top2=0;
for(int i=l;i<=r;++i){
int&x=a[i-L];
++tot[200001+x];
--x;
}
for(int i=b.size()-1;i;--i)b[i].second-=b[i-1].second;
for(int i=0;i<b.size();++i)
if(tot[200001+b[i].first]){
int&x=tot[200001+b[i].first];
t1[++top1]=make_pair(b[i].first-1,x);
b[i].second-=x,x=0;
}
int it1=0,it2=1;
while(it1<b.size()&&it2<=top1)
if(b[it1].first==t1[it2].first){
int x=b[it1].second+t1[it2].second;
if(x)t2[++top2]=make_pair(b[it1].first,x);
++it1,++it2;
}else
if(b[it1].first<t1[it2].first){
int x=b[it1].second;
if(x)t2[++top2]=make_pair(b[it1].first,x);
++it1;
}else{
int x=t1[it2].second;
if(x)t2[++top2]=make_pair(t1[it2].first,x);
++it2;
}
while(it1<b.size()){
int x=b[it1].second;
if(x)t2[++top2]=make_pair(b[it1].first,x);
++it1;
}
while(it2<=top1){
int x=t1[it2].second;
if(x)t2[++top2]=make_pair(t1[it2].first,x);
++it2;
}
b.clear();
for(int i=1;i<=top2;++i)t2[i].second+=t2[i-1].second,b.push_back(t2[i]);
it=upper_bound(b.begin(),b.end(),make_pair(-tag,0x3fffffff))-b.begin();
ans=it?b[it-1].second:0;
all+=ans;
}
}
void inc(int l,int r){
all-=ans;
l=max(l,L),r=min(r,R);
if(L==l&&r==R){
++tag;
if(it&&b[it-1].first+tag>0)--it;
ans=it?b[it-1].second:0;
all+=ans;
return;
}else{
static pair<int,int>t1[N],t2[N];int top1=0,top2=0;
for(int i=l;i<=r;++i){
int&x=a[i-L];
++tot[200001+x];
++x;
}
for(int i=b.size()-1;i;--i)b[i].second-=b[i-1].second;
for(int i=0;i<b.size();++i)
if(tot[200001+b[i].first]){
int&x=tot[200001+b[i].first];
t1[++top1]=make_pair(b[i].first+1,x);
b[i].second-=x,x=0;
}
int it1=0,it2=1;
while(it1<b.size()&&it2<=top1)
if(b[it1].first==t1[it2].first){
int x=b[it1].second+t1[it2].second;
if(x)t2[++top2]=make_pair(b[it1].first,x);
++it1,++it2;
}else
if(b[it1].first<t1[it2].first){
int x=b[it1].second;
if(x)t2[++top2]=make_pair(b[it1].first,x);
++it1;
}else{
int x=t1[it2].second;
if(x)t2[++top2]=make_pair(t1[it2].first,x);
++it2;
}
while(it1<b.size()){
int x=b[it1].second;
if(x)t2[++top2]=make_pair(b[it1].first,x);
++it1;
}
while(it2<=top1){
int x=t1[it2].second;
if(x)t2[++top2]=make_pair(t1[it2].first,x);
++it2;
}
b.clear();
for(int i=1;i<=top2;++i)t2[i].second+=t2[i-1].second,b.push_back(t2[i]);
it=upper_bound(b.begin(),b.end(),make_pair(-tag,0x3fffffff))-b.begin();
ans=it?b[it-1].second:0;
all+=ans;
}
}
}G[N];
void dfs(int now){
sz[now]=1,son[now]=0;
for(int i=head[now];i;i=e[i].nxt){
dep[e[i].to]=dep[now]+1;
dfs(e[i].to);
sz[now]+=sz[e[i].to];
if(!son[now]||sz[son[now]]<sz[e[i].to])son[now]=e[i].to;
}
}
void dfs2(int now){
idfn[dfn[now]=++idx]=now;
if(son[now])top[son[now]]=top[now],dfs2(son[now]);else tail[top[now]]=now;
for(int i=head[now];i;i=e[i].nxt)
if(e[i].to!=son[now])dfs2(top[e[i].to]=e[i].to);
if(top[now]==now){
int l=dfn[now],r=dfn[tail[now]],siz=0.7*sqrt(r-l+1);
if(siz<1)siz=1;
for(int i=l;i<=r;i+=siz){
const int L=i,R=min(i+siz-1,r);
G[++blocks].init(L,R);
for(int j=L;j<=R;++j)bel[j]=blocks;
all+=G[blocks].ans;
}
}
}
void erase(int x){
int id=dfn[x];
if(col[x])return;
col[x]=1;
G[bel[id]].add(id,100001);
for(x=fa[x];x;x=fa[top[x]]){
int L=dfn[top[x]],R=dfn[x];
const int bL=bel[L],bR=bel[R];
for(int i=bL;i<=bR;++i)G[i].dec(L,R);
}
}
void add(int x){
int id=dfn[x];
if(!col[x])return;
col[x]=0;
G[bel[id]].add(id,-100001);
for(x=fa[x];x;x=fa[top[x]]){
int L=dfn[top[x]],R=dfn[x];
const int bL=bel[L],bR=bel[R];
for(int i=bL;i<=bR;++i)G[i].inc(L,R);
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=2;i<=n;++i){
cin>>fa[i];
e[++cnt]=(edge){i,head[fa[i]]},head[fa[i]]=cnt;
}
for(int i=1;i<=n;++i)cin>>t[i],++t[i];
dfs(dep[1]=1);
dfs2(top[1]=1);
while(m--){
int k;
cin>>k;
if(k>0)erase(k);else add(-k);
cout<<all<<' ';
}
return 0;
}
```