3720: Gty的妹子树
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 412 Solved: 153
[Submit][Status]
Description
我曾在弦歌之中听过你，
檀板声碎，半出折子戏。
舞榭歌台被风吹去，
岁月深处尚有余音一缕……
Gty神(xian)犇(chong)从来不缺妹子……
他来到了一棵妹子树下，发现每个妹子有一个美丽度……
由于Gty很哲♂学，他只对美丽度大于某个值的妹子感兴趣。
他想知道某个子树中美丽度大于k的妹子个数。
某个妹子的美丽度可能发生变化……
树上可能会出现一只新的妹子……
维护一棵初始有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)
最开始时lastans=0。
Input
输入第一行包括一个正整数n(1<=n<=30000)，代表树上的初始节点数。
接下来n-1行，每行2个整数u,v，为树上的一条无向边。
任何时刻，树上的任何权值大于等于0，且两两不同。
接下来1行，包括n个整数wi，表示初始时每个节点的权值。
接下来1行，包括1个整数m(1<=m<=30000)，表示操作总数。
接下来m行，每行包括三个整数 op,u,v：
op,u,v的含义见题目描述。
保证题目涉及的所有数在int内。
Output
对每个op=0，输出一行，包括一个整数，意义见题目描述。
Sample Input
2
1 2
10 20
1
0 1 5
1 2
10 20
1
0 1 5
Sample Output
2
HINT
Source
块状树，网上很多题解，这里就不说了。一般都是把整块的排序，非整块的不排，而我直接套了的一个平衡树，应该还是要快一点吧。
写的时候一直T，结果发现是忘记size++，导致整棵树只有一块，居然还跑的很快，随机数据2s就能跑过。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
#define MAXN 61000
#define MAXB 100
#define MAXV MAXN
#define MAXE MAXN*2
#define MAXT MAXN*2
int L[MAXT],R[MAXT],S[MAXT],V[MAXT];
int topt_sbt;
#define update(now) S[now]=S[L[now]]+S[R[now]]+1;
inline int nextInt()
{
register char ch;
register int x=;
while (ch=getchar(),ch<'' || ch>'');
while (x=x*+ch-'',ch=getchar(),ch<='' && ch>='');
return x;
}
inline void r_rotate(register int &now)
{
register int t=L[now];
L[now]=R[t];update(now);
R[t]=now;update(t);
now=t;
}
inline void l_rotate(register int &now)
{
register int t=R[now];
R[now]=L[t];update(now);
L[t]=now;update(t);
now=t;
}
void maintain(register int &now)
{
if (S[L[L[now]]]>S[R[now]])
{
r_rotate(now);
maintain(L[now]);
// maintain(R[now]);
maintain(now);
return ;
}
if (S[R[R[now]]]>S[L[now]])
{
l_rotate(now);
maintain(R[now]);
// maintain(L[now]);
maintain(now);
return ;
}
if (S[L[R[now]]]>S[L[now]])
{
r_rotate(R[now]);
l_rotate(now);
maintain(L[now]);
maintain(R[now]);
maintain(now);
return ;
}
if (S[R[L[now]]]>S[R[now]])
{
l_rotate(L[now]);
r_rotate(now);
maintain(L[now]);
maintain(R[now]);
maintain(now);
return ;
}
}
void Insert(register int &now,int v)
{
if (!now)
{
now=++topt_sbt;
V[now]=v;
S[now]=;
return ;
}
if (v<V[now])
Insert(L[now],v);
else
Insert(R[now],v);
update(now);
maintain(now);
return ;
}
void Erase(register int &now,int v)
{
if (!now)return;
if (V[now]==v)
{
if (!L[now] && !R[now])now=;
else
{
if (!L[now])now=R[now];
else if (!R[now])now=L[now];
else
{
r_rotate(now);
Erase(R[now],v);
}
update(now);
maintain(now);
}
return ;
}
if (v<V[now])Erase(L[now],v);
else Erase(R[now],v);
update(now);
maintain(now);
}
int Count_greater(int now,int v)
{
if (!now)return ;
return (V[now]>v)?S[R[now]]++Count_greater(L[now],v):Count_greater(R[now],v);
}
void Scan(int now)
{
if (!now)
return ;
Scan(L[now]);
printf("%d ",V[now]);
Scan(R[now]);
}
struct Edge
{
int np;
Edge *next;
}E[MAXE*],*V1[MAXV],*V2[MAXV];
int tope=-;
inline void addedge(int x,int y)
{
E[++tope].np=y;
E[tope].next=V1[x];
V1[x]=&E[tope];
}
inline void addedge2(int x,int y)
{
E[++tope].np=y;
E[tope].next=V2[x];
V2[x]=&E[tope];
}
int q[MAXV];
int fa[MAXV];
int w[MAXV];
void bfs()
{
register int head=-,tail=;
register int now;
register Edge *ne;
q[]=;
fa[]=;
while (head<tail)
{
now=q[++head];
for (ne=V1[now];ne;ne=ne->next)
{
if (ne->np==fa[now])continue;
fa[ne->np]=now;
q[++tail]=ne->np;
}
}
}
int bb[MAXV],sb[MAXN],tp[MAXN];
int root[MAXN];
int ss;
int topb=;
inline void Add_node(int f,int id,int ww)
{
w[id]=ww;
if (sb[bb[f]]>=ss)
{
bb[id]=++topb;
tp[topb]=id;
addedge2(bb[f],topb);
}
else
bb[id]=bb[f];
sb[bb[id]]++;
Insert(root[bb[id]],ww);
}
inline void Modify_node(int now,int v)
{
Erase(root[bb[now]],w[now]);
w[now]=v;
Insert(root[bb[now]],w[now]);
} int Scan_block(register int now,int kk)
{
register int ret=;
register Edge *ne;
ret+=Count_greater(root[now],kk);
for (ne=V2[now];ne;ne=ne->next)
ret+=Scan_block(ne->np,kk);
return ret;
}
int Search_tree(register int now,int kk)
{
if (tp[bb[now]]==now)
return Scan_block(bb[now],kk);
else
{
register int ret=w[now]>kk;
register Edge *ne;
for (ne=V1[now];ne;ne=ne->next)
ret+=Search_tree(ne->np,kk);
return ret;
}
}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
int i,x,y,n;
int m;
int now;
n=nextInt();
for (i=;i<n;i++)
{
x=nextInt();y=nextInt();
addedge(x,y);
addedge(y,x);
}
for (i=;i<=n;i++)
w[i]=nextInt();
bfs();
memset(V1,,sizeof(V1));
tope=-;
for (i=;i<=n;i++)addedge(fa[i],i);
ss=(int)sqrt(n);
sb[]=;bb[]=;
for (i=;i<n;i++)
{
now=q[i];
Add_node(fa[now],now,w[now]);
}
m=nextInt();
int opt=;
int lastans=;
for (i=;i<m;i++)
{
opt=nextInt();
x=nextInt();y=nextInt();
x^=lastans;y^=lastans;
if (opt==)
{
printf("%d\n",lastans=Search_tree(x,y));
}else if (opt==)
{
Modify_node(x,y);
}else if (opt==)
{
Add_node(x,++n,y);
addedge(x,n);
fa[n]=x;
}
}
}