bzoj 3720: Gty的妹子树 块状树

bzoj 3720: Gty的妹子树 块状树

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

Sample Output

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=0;while (ch=getchar(),ch<'0' || ch>'9');while (x=x*10+ch-'0',ch=getchar(),ch<='9' && ch>='0');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]=1;return ;}if (v<V[now])Insert(L[now],v);elseInsert(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=0;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 0;return (V[now]>v)?S[R[now]]+1+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*2],*V1[MAXV],*V2[MAXV];
int tope=-1;
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=-1,tail=0;register int now;register Edge *ne;q[0]=1;fa[1]=1;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=1;
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);}elsebb[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=0;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(&#","r",stdin);//freopen(&#","w",stdout);int i,x,y,n;int m;int now;n=nextInt();for (i=1;i<n;i++){x=nextInt();y=nextInt();addedge(x,y);addedge(y,x);}for (i=1;i<=n;i++)w[i]=nextInt();bfs();memset(V1,0,sizeof(V1));tope=-1;for (i=2;i<=n;i++)addedge(fa[i],i);ss=(int)sqrt(n);sb[1]=1;bb[1]=1;for (i=1;i<n;i++){now=q[i];Add_node(fa[now],now,w[now]);}m=nextInt();int opt=0;int lastans=0;for (i=0;i<m;i++){opt=nextInt();x=nextInt();y=nextInt();x^=lastans;y^=lastans;if (opt==0){printf("%dn",lastans=Search_tree(x,y));}else if (opt==1){Modify_node(x,y);}else if (opt==2){Add_node(x,++n,y);addedge(x,n);fa[n]=x;}}
}

转载于:.html