被卡成 MLE 了求救

1000000
W 1
(上一行再重复 999996 次)
? 1
Z 1
? 1

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>
void in(T &x){
	char c=getchar();T f=1; x=0;
	while(c<'0'||c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	x*=f;
}
const int N=2000010,M=2000000;
vector<int> g[N],h[N];
int n,m,p;
char str[2];
char op[N];
int now[N],cur[N],nwc[N],nxt[N];
int dfn[N],lst[N],anc[N],ck;
queue<int> q;
void dfs(int u){
    dfn[u]=lst[u]=++ck;
    for(int v:g[u]){
        anc[v]=anc[u];
        dfs(v);
        lst[u]=max(lst[u],lst[v]);
    }
    for(int v:h[u]){
        anc[v]=u;
        q.push(v);
    }
}
struct BIT{
    int a[N];
    int lowbit(int x){return x&-x;}
    void update(int x,int y){
        for(;x<=M;x+=lowbit(x))
            a[x]+=y;
    }
    int query(int x){
        int res=0;
        for(;x;x-=lowbit(x))
            res+=a[x];
        return res;
    }
}bita,bitb;
int main(){
    in(n); m=1; nwc[1]=1;
    for(int i=0;i<=n;i++){
        if(i==0){
            str[0]='W';
            cur[i]=1;
        }else{
            scanf("%s",str);
            in(cur[i]);
        }
        if(str[0]=='?') continue;
        now[i]=++m; nwc[m]=m;
        if(str[0]=='W'){
            op[i]=1;
            g[nwc[cur[i]]].push_back(M-p);
            nwc[cur[i]]=nxt[nwc[cur[i]]]=M-p;
            p++;
            h[nwc[cur[i]]].push_back(m);
        }else{
            op[i]=2;
            g[nwc[cur[i]]].push_back(m);
        }
    }
    q.push(1);
    while(!q.empty()){
        dfs(q.front());
        q.pop();
    }
    bitb.update(dfn[1],1);
    for(int i=1;i<=m;i++) nwc[i]=i;
    for(int i=0;i<=n;i++){
        int u=nwc[cur[i]]; int v=anc[cur[i]];
        if(op[i]==0){
            int ans=bita.query(dfn[u]);
            if(v) ans+=bitb.query(lst[v])-bitb.query(dfn[v]-1);
            printf("%d\n",ans);
        }else if(op[i]==1){
            bitb.update(dfn[nwc[now[i]]],1);
            bitb.update(dfn[u],-1);
            nwc[cur[i]]=u=nxt[u];
            bitb.update(dfn[u],1);
            if(u){
                bita.update(dfn[u],1);
                bita.update(lst[u]+1,-1);
            }
        }else{
            bitb.update(dfn[nwc[now[i]]],1);
            if(v){
                bita.update(dfn[v],1);
                bita.update(lst[v]+1,-1);
            }
        }
    }
}