毒瘤数据结构复习系列.
设0为未安装, 1为已安装, 当安装某个包x时, 统计root~x路径上0的个数, 再把整条路径设为1
卸载包x时, 统计x为根的子树1的个数, 再把整颗子树设为0
线段树的区间覆盖只要把懒标记的+=改为=就行了
看到题解中还有一种更妙的做法: 只进行update操作, 统计线段树根节点sum值变化即可, 理论上常数是我的一半(妙啊)
#include<cstdio> #define re register #define in inline #define lc p<<1 #define rc p<<1|1 in int read() { int s=0,b=0;char ch; do{ch=getchar();if(ch=='-') b=1;}while(ch<'0'||ch>'9'); while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+(ch^48);ch=getchar();} return b?-s:s; } const int N=100001; int n,m; struct edge{int t,nxt;}e[N]; int head[N],cnt; in void add(int f,int t){++cnt;e[cnt].t=t,e[cnt].nxt=head[f],head[f]=cnt;} int f[N],id[N],son[N],d[N],subt[N],top[N]; struct SegmentTree{int l,r,sum,set;}t[N*4]; in void build(int p,int l,int r) { t[p].l=l,t[p].r=r,t[p].set=-1;//每个节点的set都要赋为-1 !!! 而不是只赋叶子节点!!! if(l==r) return; int mid=(l+r)>>1; build(lc,l,mid); build(rc,mid+1,r); } in void spread(int p) { if(t[p].set==-1) return; t[lc].sum=t[p].set*(t[lc].r-t[lc].l+1); t[rc].sum=t[p].set*(t[rc].r-t[rc].l+1); t[lc].set=t[p].set,t[rc].set=t[p].set; t[p].set=-1; } int ask(int p,int l,int r,int w) { if(l<=t[p].l&&t[p].r<=r) return w?t[p].sum:(t[p].r-t[p].l+1-t[p].sum); spread(p); int mid=(t[p].l+t[p].r)>>1,ans=0; if(l<=mid) ans+=ask(lc,l,r,w); if(r>mid) ans+=ask(rc,l,r,w); return ans; } void upd(int p,int l,int r,int w) { if(l<=t[p].l&&t[p].r<=r){t[p].set=w,t[p].sum=w*(t[p].r-t[p].l+1);return;} spread(p); int mid=(t[p].l+t[p].r)>>1; if(l<=mid) upd(lc,l,r,w); if(r>mid) upd(rc,l,r,w); t[p].sum=t[lc].sum+t[rc].sum;//别忘了!!! } void dfs1(int now) { d[now]=d[f[now]]+1,subt[now]=1; int maxson=0; for(re int i=head[now];i;i=e[i].nxt) { dfs1(e[i].t); subt[now]+=subt[e[i].t]; if(subt[e[i].t]>maxson) maxson=subt[e[i].t],son[now]=e[i].t; } } void dfs2(int now,int topfa) { id[now]=++cnt,top[now]=topfa; if(!son[now]) return; dfs2(son[now],topfa); for(re int i=head[now];i;i=e[i].nxt) if(e[i].t!=son[now]) dfs2(e[i].t,e[i].t); } void updr(int x,int y,int w) { while(top[x]!=top[y]) { if(d[top[x]]<d[top[y]]) x^=y,y^=x,x^=y; upd(1,id[top[x]],id[x],w); x=f[top[x]]; } if(d[x]<d[y]) x^=y,y^=x,x^=y; upd(1,id[y],id[x],w); } int askr(int x,int y,int w) { int ans=0; while(top[x]!=top[y]) { if(d[top[x]]<d[top[y]]) x^=y,y^=x,x^=y; ans+=ask(1,id[top[x]],id[x],w); x=f[top[x]]; } if(d[x]<d[y]) x^=y,y^=x,x^=y; ans+=ask(1,id[y],id[x],w); return ans; } signed main() { //注意:软件包编号统一+1 n=read(); for(re int i=2;i<=n;++i){int x=read();f[i]=x+1;add(x+1,i);} cnt=0; dfs1(1); dfs2(1,1); build(1,1,n); m=read(); for(re int i=1;i<=m;++i) { char s[11]; scanf("%s",s); int x=read(); ++x; if(s[0]=='i'){ printf("%d\n",askr(1,x,0)); updr(1,x,1); } else{ printf("%d\n",ask(1,id[x],id[x]+subt[x]-1,1)); upd(1,id[x],id[x]+subt[x]-1,0); } } return 0; }
最新评论