【BZOJ4196】软件包管理器
裸的树链剖分，就是再加一个修改子树的操作，子树在线段树里是连续的。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 | #include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn=100010;struct Segment_Tree{ int sum[maxn<<2]; int tag_same[maxn<<2]; int tag_clear[maxn<<2]; int _l,_r; int n; #define ls (o<<1) #define rs ((o<<1)|1) #define mid ((l+r)>>1) void Mark_Clear(int o) { sum[o]=0; tag_same[o]=0; tag_clear[o]=1; } void Mark_Same(int o,int l,int r) { sum[o]=r-l+1; tag_clear[o]=0; tag_same[o]=1; } void Push_Down(int o,int l,int r) { if (l==r) return; if (tag_clear[o]) { Mark_Clear(ls); Mark_Clear(rs); tag_clear[o]=0; } if (tag_same[o]) { Mark_Same(ls,l,mid); Mark_Same(rs,mid+1,r); tag_same[o]=0; } } void Update(int o) {sum[o]=sum[ls]+sum[rs];} void Change_Same(int o,int l,int r) { if (_l<=l && r<=_r) {Mark_Same(o,l,r);return;} Push_Down(o,l,r); if (_l<=mid) Change_Same(ls,l,mid); if (_r>mid) Change_Same(rs,mid+1,r); Update(o); } void Change_Clear(int o,int l,int r) { if (_l<=l && r<=_r) {Mark_Clear(o);return;} Push_Down(o,l,r); if (_l<=mid) Change_Clear(ls,l,mid); if (_r>mid) Change_Clear(rs,mid+1,r); Update(o); } int Query(int o,int l,int r) { if (_l<=l && r<=_r) return sum[o]; Push_Down(o,l,r); int res=0; if (_l<=mid) res+=Query(ls,l,mid); if (_r>mid) res+=Query(rs,mid+1,r); Update(o); return res; } int Sum() {return sum[1];} void Change_Same(int _a,int _b) {_l=_a;_r=_b;Change_Same(1,1,n);} void Change_Clear(int _a,int _b) {_l=_a;_r=_b;Change_Clear(1,1,n);} #undef ls #undef rs #undef mid}ST;struct Tree{ int head[maxn],next[maxn<<1],E[maxn<<1],Ecnt; int fa[maxn],dep[maxn]; int top[maxn],wson[maxn]; int id[maxn],ids; int l[maxn],r[maxn]; void Add_Edge(int x,int y) {next[++Ecnt]=head[x];head[x]=Ecnt;E[Ecnt]=y;next[++Ecnt]=head[y];head[y]=Ecnt;E[Ecnt]=x;} int DFS1(int x,int father,int depth) { int sons=0,maxsons=0; fa[x]=father;dep[x]=depth; for (int i=head[x];i;i=next[i]) if (E[i]!=father) { int tsons=DFS1(E[i],x,depth+1); sons+=tsons; if (tsons>maxsons) maxsons=tsons,wson[x]=E[i]; } return sons+1; } void DFS2(int x,int is_wson) { id[x]=++ids; l[x]=ids; if (is_wson) top[x]=top[fa[x]];else top[x]=x; if (wson[x]) DFS2(wson[x],1); for (int i=head[x];i;i=next[i]) if (E[i]!=fa[x] && E[i]!=wson[x]) DFS2(E[i],0); r[x]=ids; } void Build(int n) { (void)DFS1(0,0,1); DFS2(0,1); ST.n=n; } int Install(int x) { int pre=ST.Sum(); while (x!=0) ST.Change_Same(id[top[x]],id[x]),x=fa[top[x]]; ST.Change_Same(id[0],id[0]); return ST.Sum()-pre; } int Unistall(int x) { int pre=ST.Sum(); ST.Change_Clear(l[x],r[x]); return pre-ST.Sum(); }}T;void read(int &x) {char ch;while ((ch=getchar())<'0' || ch>'9');x=ch-'0';while ((ch=getchar())>='0' && ch<='9') x=x*10+ch-'0';}char ctr[20];int n,q;int main(){ read(n); for (int i=1,y;i<n;i++) read(y),T.Add_Edge(i,y); T.Build(n); read(q); for (int i=1,x;i<=q;i++) { scanf("%s",ctr); read(x); if (ctr[0]=='i') printf("%d\n",T.Install(x)); if (ctr[0]=='u') printf("%d\n",T.Unistall(x)); } return 0;} |
评论 (0)
