Code

#include 
     
      #include 
      
       #include 
       
        #define MID int mid=(l+r)>>1,ls=id<<1,rs=id<<1|1#define len (r-l+1)#define N 100010using namespace std;struct info{int to,nex;}e[N*2];int n,A[N],tot,head[N],T[N*4],tag[N*4];int dep[N],fa[N],sz[N],son[N];int cnt,tp[N],tw[N],tid[N];inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}    return x*f;}void dfs(int u,int pre){	sz[u]=1;	for(int i=head[u],mx=0;i;i=e[i].nex){		int v=e[i].to;		if(v==pre) continue;		dep[v]=dep[u]+1;		fa[v]=u;		dfs(v,u);		sz[u]+=sz[v];		if(sz[v]>mx) son[u]=v,mx=sz[v];	}}inline void Link(int u,int v){	e[++tot].nex=head[u];e[tot].to=v;head[u]=tot;}void dddfs(int u,int top){	tp[u]=top;	tid[u]=++cnt;	tw[cnt]=A[u];	if(!son[u]) return;		dddfs(son[u],top);	for(int i=head[u];i;i=e[i].nex){		int v=e[i].to;		if(v!=son[u]&&v!=fa[u]) dddfs(v,v);	}}inline void Init(){	memset(tag,-1,sizeof(tag));	n=read();	for(int i=1;i
        
         mid) res+=query(mid+1,r,rs,L,R);	return res;}inline int qRange(int u,int v){	int res=0;	while(tp[u]!=tp[v]){		if(dep[tp[u]]
         
          dep[v]) swap(u,v);	res+=query(1,n,1,tid[u],tid[v]);	return res;}void update(int l,int r,int id,int L,int R,int f){	if(L<=l&&r<=R){		tag[id]=f;T[id]=len*f;		return;	}	if(tag[id]!=-1) pushdown(l,r,id);	MID;	if(tag[id]) 	if(L<=mid) update(l,mid,ls,L,R,f);	if(R>mid) update(mid+1,r,rs,L,R,f);	T[id]=T[ls]+T[rs];}inline void updRange(int u,int v,int f){	while(tp[u]!=tp[v]){		if(dep[tp[u]]
          
           dep[v]) swap(u,v); update(1,n,1,tid[u],tid[v],f);}int ins(int u){ int res=dep[u]+1-qRange(0,u); updRange(0,u,1); return res;}int uni(int u){ int res=query(1,n,1,tid[u],tid[u]+sz[u]-1); update(1,n,1,tid[u],tid[u]+sz[u]-1,0); return res;} inline void solve(){ int m=read(),u; char s[20]; while(m--){ scanf("%s%d\n",s,&u); if(s[0]=='i') printf("%d\n",ins(u)); else printf("%d\n",uni(u)); }}int main(){Init();solve();}