Gty的超級妹子樹
Time Limit: 7 Sec Memory Limit: 32 MB
Submit: 500 Solved: 122
[Submit][Status][Discuss]
Description
我曾在青山之中遇過你，
新竹做杖，鬓插紫茱萸。
跣足踏過無邊絲雨，
又拾起燕川雪片片落如席……
Gty神(xian)犇(chong)從來不缺妹子……
他又來到了一棵妹子樹下，發現每個妹子有一個美麗度……
由于Gty很 哲♂學 也很 機♂智，他隻對美麗度大于某個值的妹子感興趣。
他想知道某個子樹中美麗度大于x的妹子個數。
某個妹子的美麗度可能發生變化……
樹上可能會出現一隻新的妹子……
但是……樹枝可能會斷裂，于是，Gty驚訝地發現，他的面前變成了一片妹子樹組成的森林……
維護一棵初始有n個節點的有根樹(根節點為1)，樹上節點編号為1-n，每個點有一個權值wi。它可能會變成森林。
支援以下操作：
0 u x 詢問以u為根的子樹中，嚴格大于x的值的個數。(u^=lastans,x^=lastans)
1 u x 把u節點的權值改成x。(u^=lastans,x^=lastans)
2 u x 添加一個編号為"目前樹中節點數+1"的節點，其父節點為u，其權值為x。(u^=lastans,x^=lastans)
3 u 删除節點u與其父節點之間的路徑。此時u的父節點變成葉子節點，u變成分裂出的樹的根。(u^=lastans)
最開始時lastans=0。
Input
輸入第一行包括一個正整數n(1<=n<=100000)，代表樹上的初始節點數。
接下來n-1行，每行2個整數u,v，為樹上的一條無向邊。
任何時刻，樹上的任何權值大于等于0，且兩兩不同。
接下來1行，包括n個整數wi，表示初始時每個節點的權值。
接下來1行，包括1個整數m(1<=m<=100000)，表示操作總數。
接下來m行，每行最開始包括一個整數op,
若op=3，該行還會有一個整數u；
若op不等于3，該行還會有兩個整數u,x；
op,u,x的範圍見題目描述。
保證題目涉及的所有數在int内。
Output
對每個op=0，輸出一行，包括一個整數，意義見題目描述。
Sample Input
2
1 2
10 20
1
0 1 5
Sample Output
HINT
資料範圍見描述。
Source
題解：分塊的方式真的不行，被菊花圖卡的飛起，這裡加了一個删除操作，就是将一個塊分成兩個，如果剛好一個塊的話就直接分出，其實
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <cmath>
5 #include <cstdlib>
6 #include <algorithm>
7 #include <vector>
8 #define N 200006
9 #define M 400006
10
11 using namespace std;
12 inline int read(){
13 int ret=0;char ch=getchar();
14 while (ch<'0'||ch>'9') ch=getchar();
15 while ('0'<=ch&&ch<='9'){
16 ret=ret*10-48+ch;
17 ch=getchar();
18 }
19 return ret;
20 }
21
22 const int KK=400;
23 vector<int> seq[N];
24
25 struct edge{
26 int adj,next;
27 edge(){}
28 edge(int _adj,int _next):adj(_adj),next(_next){}
29 } e[M];
30 int n,g[N],m;
31 void AddEdge(int u,int v){
32 e[++m]=edge(v,g[u]);g[u]=m;
33 e[++m]=edge(u,g[v]);g[v]=m;
34 }
35 int w[N];
36
37 vector<int> nxt[N];
38 int fa[N],bl[N],sz[N],cnt,top[N];
39 void refresh(int u,int p){
40 for (;p>0&&seq[u][p]<seq[u][p-1];--p)swap(seq[u][p],seq[u][p-1]);
41 for (;p<sz[u]-1&&seq[u][p]>seq[u][p+1];++p)swap(seq[u][p],seq[u][p+1]);
42 }
43 void newnode(int u){
44 if (sz[bl[fa[u]]]==KK){
45 sz[bl[u]=++cnt]=0;
46 top[cnt]=u;
47 }
48 else bl[u]=bl[fa[u]];
49 ++sz[bl[u]];
50 }
51 void dfs(int u){
52 newnode(u);
53 for (int i=g[u];i;i=e[i].next){
54 int v=e[i].adj;
55 if (v==fa[u]) continue;
56 fa[v]=u;
57 dfs(v);
58 }
59 }
60 void dfs_pre(int u){
61 seq[bl[u]].push_back(w[u]);++sz[bl[u]];
62 for (int i=g[u];i;i=e[i].next)if (fa[e[i].adj]==u){
63 int v=e[i].adj;
64 if (bl[v]==bl[u]) dfs_pre(v);
65 else nxt[bl[u]].push_back(bl[v]);
66 }
67 }
68 void prepare(int id){
69 seq[id].clear();vector<int>(seq[id]).swap(seq[id]);
70 nxt[id].clear();vector<int>(nxt[id]).swap(nxt[id]);
71 sz[id]=0;
72 dfs_pre(top[id]);
73 sort(seq[id].begin(),seq[id].end());
74 }
75
76 int solve(int u,int lmt){
77 int l=-1,r=sz[u],mid;
78 while (l+1<r){
79 mid=l+r>>1;
80 if (seq[u][mid]<=lmt) l=mid;
81 else r=mid;
82 }
83 int ret=sz[u]-l-1;
84 for (int j=nxt[u].size()-1;j>=0;--j) ret+=solve(nxt[u][j],lmt);
85 return ret;
86 }
87 int query(int u,int lmt){
88 if (bl[u]!=bl[fa[u]]) return solve(bl[u],lmt);
89 int ret=w[u]>lmt;
90 for (int i=g[u];i;i=e[i].next)if (fa[e[i].adj]==u)ret+=query(e[i].adj,lmt);
91 return ret;
92 }
93
94 void modify(int u,int x){
95 int p;
96 for (int i=0;i<sz[bl[u]];++i)
97 if (seq[bl[u]][i]==w[u]){p=i;break;}
98 w[u]=x;seq[bl[u]][p]=x;
99 refresh(bl[u],p);
100 }
101
102 void create(int u,int x){
103 AddEdge(u,++n);fa[n]=u;w[n]=x;
104 int tmp=cnt;
105 newnode(n);
106 seq[bl[n]].push_back(w[n]);
107 refresh(bl[n],sz[bl[n]]-1);
108 if (tmp<cnt) nxt[bl[u]].push_back(cnt);
109 }
110
111 void dfs_update(int u,int last,int now){
112 bl[u]=now;
113 for (int i=g[u];i;i=e[i].next)if (fa[e[i].adj]==u)
114 if (bl[e[i].adj]==last) dfs_update(e[i].adj,last,now);
115 }
116
117 void cut(int u){
118 int lst=bl[u];
119 if (bl[fa[u]]!=bl[u]){
120 int f=bl[fa[u]];
121 for (vector<int>::iterator it=nxt[f].begin();it!=nxt[f].end();++it)
122 if ((*it)==lst){nxt[f].erase(it);break;}
123 fa[u]=0;return;
124 }
125 top[++cnt]=u;
126 fa[u]=0;
127 dfs_update(u,lst,cnt);
128 prepare(lst);
129 prepare(cnt);
130 }
131
132 int main(){
133 n=read();
134 memset(g,0,sizeof(g));m=1;
135 for (int i=1;i<n;++i) AddEdge(read(),read());
136 for (int i=1;i<=n;++i) w[i]=read();
137 fa[1]=0;bl[0]=0;sz[0]=KK;cnt=0;
138 dfs(1);
139 int lastans=0;
140 for (int i=1;i<=cnt;++i) prepare(i);
141 for (int Q=read();Q;Q--){
142 int op=read(),u=read()^lastans,x;
143 if (op<3) x=read()^lastans;
144 else cut(u);
145 if (op==0) printf("%d\n",lastans=query(u,x));
146 else if (op==1) modify(u,x);
147 else if (op==2) create(u,x);
148 }
149 }