题目概述

有一棵树，每个节点有一个权值 $t_i$ 。现在有 $m$ 次操作，每次操作表示一个节点被删除了或被重新添加了，每次操作后统计子树中被删除节点 $>t_i$ 且没被删除的节点的个数。

解题报告

好像是一种对操作序列分块的套路？看到 $10^5$ 我是想到了分块，但是没想到是对操作序列分块……

可以发现每次操作都是对一条到根路径进行 $t_i\pm1$ ，这完全可以打tag，用指针维护 $t_i<0$ 和 $t_i\ge 0$ 的分界点（去重之后由于每次只加减 $1$ 所以最多移动一次）。但是有很多条到根路径，导致树被分成很多块，统计很困难。如果能想办法让分成的块数少就可做了。

操作的点都是操作序列上的，所以我们对操作序列分块，然后对每一块操作序列的点建虚树，块数就少了，这样就可以每次愉快的暴力向上修改并移动分界指针。因为被删除的点是不算的，所以细节挺多，对拍查错……

示例程序

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
const int maxn=100000,Log=17,maxm=100000;

int n,S,m,a[maxn+5],q[maxm+5],ans[maxm+5],dep[maxn+5],ST[maxn+5][Log+5];
int E,lnk[maxn+5],son[maxn+5],nxt[maxn+5];bool vis[maxn+5];
int ti,Lt[maxn+5],Rt[maxn+5],p[maxn+5],top,stk[maxn+5],Key[maxn+5],us[maxn+5];
int fa[maxn+5],now[maxn+5],tag[maxn+5],pos[maxn+5];vector< pair<int,int> > v[maxn+5];

#define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E)
void Dfs(int x,int pre=0){
    dep[x]=dep[pre]+1;ST[x][0]=pre;for (int j=1;j<=Log;j++) ST[x][j]=ST[ST[x][j-1]][j-1];
    Lt[x]=++ti;for (int j=lnk[x];j;j=nxt[j]) Dfs(son[j],x);Rt[x]=ti;
}
inline int LCA(int x,int y){
    if (dep[x]<dep[y]) swap(x,y);for (int j=Log;dep[x]>dep[y]&&~j;j--) if (dep[ST[x][j]]>=dep[y]) x=ST[x][j];
    if (x==y) return x;for (int j=Log;~j;j--) if (ST[x][j]!=ST[y][j]) x=ST[x][j],y=ST[y][j];return ST[x][0];
}
inline bool Lcmp(const int &a,const int &b) {return Lt[a]<Lt[b];}
inline bool Acmp(const int &A,const int &B) {return a[A]<a[B];}
#define Son(fa,x) (Lt[fa]<=Lt[x]&&Rt[x]<=Rt[fa])
inline void Join(int x,int y){
    fa[y]=x;now[0]=0;for (int i=y;i!=x;i=ST[i][0]) now[++now[0]]=i;sort(now+1,now+1+now[0],Acmp);
    for (int i=(v[y].clear(),1),j;i<=now[0];i=j){
        int tot=0;for (j=i;j<=now[0]&&a[now[i]]==a[now[j]];j++) tot+=!vis[now[j]]&&Key[now[j]]<Key[0];
        v[y].push_back(mp(a[now[i]],tot));
    }tag[y]=0;for (pos[y]=-1;pos[y]+1<v[y].size()&&v[y][pos[y]+1].fr<0;pos[y]++);
}
inline void Solve(int l,int r){
    p[0]=0;Key[0]++;for (int i=l;i<=r;i++) p[++p[0]]=q[i],Key[q[i]]=Key[0];sort(p+1,p+1+p[0],Lcmp);
    for (int i=2,si=p[0];i<=si;i++) p[++p[0]]=LCA(p[i-1],p[i]);p[++p[0]]=1;
    sort(p+1,p+1+p[0],Lcmp);p[0]=unique(p+1,p+1+p[0])-p-1;Join(0,1);top=0;
    for (int i=1;i<=p[0];i++){
        while (top&&!Son(stk[top],p[i])) top--;
        if (top) Join(stk[top],p[i]);stk[++top]=p[i];
    }
    for (int i=l;i<=r;i++){
        us[0]++;for (int j=l;j<=r;j++) if (us[q[j]]<us[0]&&!vis[q[j]]&&a[q[j]]+tag[q[j]]<0) ans[i]--,us[q[j]]=us[0];
        for (int f=(vis[q[i]]?1:-1),x=q[i];x;x=fa[x]){
            tag[x]+=f;while (~pos[x]&&v[x][pos[x]].fr+tag[x]>=0) ans[i]-=v[x][pos[x]].sc,pos[x]--;
            while (pos[x]+1<v[x].size()&&v[x][pos[x]+1].fr+tag[x]<0) pos[x]++,ans[i]+=v[x][pos[x]].sc;
        }vis[q[i]]^=1;
        us[0]++;for (int j=l;j<=r;j++) if (us[q[j]]<us[0]&&!vis[q[j]]&&a[q[j]]+tag[q[j]]<0) ans[i]++,us[q[j]]=us[0];
    }
    for (int i=1;i<=p[0];i++) for (int x=p[i];x!=fa[p[i]];x=ST[x][0]) a[x]+=tag[p[i]];
    for (int i=l;i<=r;i++) ans[i]+=ans[i-1],printf("%d",ans[i]),putchar(i<m?' ':'\n');
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&m);S=sqrt(m*log2(n))+1;for (int i=2,fa;i<=n;i++) scanf("%d",&fa),Add(fa,i);Dfs(1);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);for (int i=1;i<=m;i++) scanf("%d",&q[i]),q[i]<0?q[i]=-q[i]:0;
    for (int l=1,r=min(l+S-1,m);l<=m;l+=S,r=min(l+S-1,m)) Solve(l,r);return 0;
}