3720: Gty的妹子树
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 1889 Solved: 654
[Submit][Status][Discuss]
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
2017.9.28新加数据一组by GXZlegend,未重测
Source
书上分块，块大小调为0.4*sqrt(1.0*n)较为合适
细节太多了太多了，调了我一天
注意排序和复原
#include <bits/stdc++.h>
#define ll long long
#define inf 0x7fffffff
using namespace std;
inline int read(){
int x=0;int f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int MAXN=1e6+10;
struct node{
int y,next;
}e[MAXN];
struct bloc{
int nov,v,num,dep;
}blo[400][410<<1];
int len=0,linkk[MAXN],n,m,a[MAXN],O,dep[MAXN],tot=1,siz[MAXN],to[MAXN],min_b[MAXN],dfs_clock=0,dfn[MAXN],pos[MAXN],ine[MAXN],ans;
inline bool cmp_v(bloc n,bloc m){
return n.v>m.v;
}
inline bool cmp_nov(bloc n,bloc m){
return n.nov<m.nov;
}
inline void insert(int xx,int yy){
e[++len].y=yy;e[len].next=linkk[xx];linkk[xx]=len;
}
inline void dfs(int st,int father){
dfn[st]=++dfs_clock;
pos[dfs_clock]=st;
for(int i=linkk[st];i;i=e[i].next){
if(e[i].y!=father){
dep[e[i].y]=dep[st]+1;
dfs(e[i].y,st);
}
}
}
void init(){
n=read();
for(int i=1;i<n;i++){
int xx=read();int yy=read();
insert(xx,yy);insert(yy,xx);
}
for(int i=1;i<=n;i++){
a[i]=read();
}
dfs(1,0);
}
void pre(){
int k=1;
O=(int)(sqrt(n)*0.4);
memset(min_b,127,sizeof(min_b));
for(int i=1;i<=dfs_clock;i++){
ine[pos[i]]=tot;siz[tot]++;
min_b[tot]=min(min_b[tot],dep[pos[i]]);
blo[tot][k].num=pos[i];blo[tot][k].v=a[pos[i]];
blo[tot][k].nov=k;blo[tot][k].dep=dep[pos[i]];
if(++k>O) tot++,k=1;
}
for(int i=1;i<=tot;i++) sort(blo[i]+1,blo[i]+siz[i]+1,cmp_v),to[i]=i+1;
to[tot]=inf;
}
void solve(){
m=read();
while(m--){
int t=read();int x=read();int y=read();
x^=ans;y^=ans;
int now=ine[x];
if(t==0){
bool flag=true;int i;
sort(blo[now]+1,blo[now]+siz[now]+1,cmp_nov);
for(i=1;i<=siz[now];i++){
if(blo[now][i].num==x) break;
}
ans=(blo[now][i].v>y);
int limit=blo[now][i].dep;
for(i=i+1;i<=siz[now]&&flag;i++){
if(blo[now][i].dep>limit){
ans+=(blo[now][i].v>y);
}
else flag=false;
}
sort(blo[now]+1,blo[now]+siz[now]+1,cmp_v);
if(!flag){
printf("%d
",ans);
continue;
}
for(i=to[now];i&&i!=inf;i=to[i]){
if(min_b[i]>limit){
int l=1;int r=siz[i];
int maxn=0;
while(l<=r){
int mid=(l+r)>>1;
if(blo[i][mid].v>y) l=mid+1,maxn=max(maxn,mid);
else r=mid-1;
}
ans+=maxn;
}
else break;
}
if(i==inf){
printf("%d
",ans);
continue;
}
sort(blo[i]+1,blo[i]+siz[i]+1,cmp_nov);
for(int j=1;j<=siz[i]&&blo[i][j].dep>limit;j++){
ans+=(blo[i][j].v>y);
}
sort(blo[i]+1,blo[i]+siz[i]+1,cmp_v);
printf("%d
",ans);
}
if(t==1){
for(int i=1;i<=siz[now];i++){
if(blo[now][i].num==x){
blo[now][i].v=y;
break;
}
}
sort(blo[now]+1,blo[now]+siz[now]+1,cmp_v);
}
if(t==2){
if(siz[now]+1==2*O){
sort(blo[now]+1,blo[now]+O*2,cmp_nov);
++tot;siz[now]=siz[tot]=O;++n;
to[tot]=to[now];to[now]=tot;
int i;
for(i=1;i<O<<1;i++){
if(blo[now][i].num==x) break;
}
blo[now][O<<1].nov=blo[now][i].nov+1;
for(i=i+1;i<O<<1;i++) blo[now][i].nov+=1;
dep[n]=blo[now][O<<1].dep=dep[x]+1;
blo[now][O<<1].v=y;blo[now][O<<1].num=n;
sort(blo[now]+1,blo[now]+O*2+1,cmp_nov);
for(i=O+1;i<=O<<1;i++){
blo[tot][i-O]=blo[now][i];
ine[blo[now][i].num]=tot;
blo[tot][i-O].nov=i-O;
}
if(!ine[n]) ine[n]=now;
for(min_b[tot]=inf,i=1;i<=siz[tot];i++) min_b[tot]=min(min_b[tot],blo[tot][i].dep);
for(min_b[now]=inf,i=1;i<=siz[now];i++) min_b[now]=min(min_b[now],blo[now][i].dep);
sort(blo[tot]+1,blo[tot]+O+1,cmp_v);
sort(blo[now]+1,blo[now]+O+1,cmp_v);
}
else{
sort(blo[now]+1,blo[now]+siz[now]+1,cmp_nov);
ine[++n]=now;
int i;
for(i=1;i<=siz[now];i++){
if(blo[now][i].num==x) break;
}
++siz[now];
blo[now][siz[now]].nov=blo[now][i].nov+1;
for(i=i+1;i<siz[now];i++) blo[now][i].nov++;
blo[now][siz[now]].v=y;
blo[now][siz[now]].num=n;
dep[n]=blo[now][siz[now]].dep=dep[x]+1;
sort(blo[now]+1,blo[now]+siz[now]+1,cmp_v);
}
}
}
}
int main(){
//freopen("All.in","r",stdin);
//freopen("zhang.out","w",stdout);
init();
pre();
solve();
return 0;
}