【块状树】

orz lzt的神题
发现我根本不会块状树
…………写了好久调了……一上午是有了
总结一下
块状树是分块数据结构，即把树分为根号n块，块内暴力快外整体查询。【据研究显示(nlogn)^1/2会更快】
先分块，分块的时候注意要存张树的图和块的图
查询的时候块内暴力如果连到块外整个块一起查
如果要加点，若能合并到上一个块则合并，若不行则新开一个块
错误点：（自己犯2就不说了）
1、不能从查询点所在块直接往下搜块。这样会导致有些不应被计入的块被计入。这样子的话就需要存一个整图而不是块内图，在加点的时候也需要改动

2、vector真是简单直白……

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath> 
#include<vector>
#define maxn 60001
using namespace std;
int top[maxn],size[maxn];
struct map
{int widen;int next[maxn],point[maxn],v[maxn];void addedge(int x,int y){widen++;next[widen]=point[x];point[x]=widen;v[widen]=y;}
} org,block,b;
int border,sum=0,lastans;
int w[maxn],fa[maxn];
vector<int>list[maxn];
int n,m;
int readln()
{char c=getchar();int bj=1,result=0;while (c!='-'&&!(c<='9'&&c>='0')) c=getchar();if (c=='-') bj=-1,c=getchar();while (c<='9'&&c>='0') result=result*10+c-'0',c=getchar();return result*bj;
}
void makeblock(int now)
{int root=top[now];list[root].push_back(w[now]);for (int k=org.point[now];k!=0;k=org.next[k])if (org.v[k]!=fa[now]){fa[org.v[k]]=now;block.addedge(now,org.v[k]);if (size[root]<border){size[root]++;top[org.v[k]]=root;}else b.addedge(root,org.v[k]);makeblock(org.v[k]);}
}
void queryblock(int now,int num)
{sum=sum+list[now].end()-upper_bound(list[now].begin(),list[now].end(),num);for (int k=b.point[now];k!=0;k=b.next[k])        queryblock(b.v[k],num);
}
void query(int now,int num)
{if (w[now]>num) sum++;for (int k=block.point[now];k!=0;k=block.next[k])if (top[now]==top[block.v[k]])query(block.v[k],num);else queryblock(block.v[k],num);
} 
int main()
{int i,j,k,l,s,t,root,u,v,z,x,y,xx;n=readln();border=(int)ceil(sqrt(n)*log2(n));for (i=1;i<n;i++){u=readln();v=readln();org.addedge(u,v);org.addedge(v,u);}for (i=1;i<=n;i++) {w[i]=readln();size[i]=1;top[i]=i;}makeblock(1);for (i=1;i<=n;i++)if (top[i]==i)   sort(list[i].begin(),list[i].end());m=readln();lastans=0;for (int o=1;o<=m;o++){z=readln();x=readln()^lastans;y=readln()^lastans;if (z==0) {sum=0;if (x==top[x]) queryblock(x,y);else query(x,y);lastans=sum;printf("%d
",sum);}if (z==1){list[top[x]].erase(lower_bound(list[top[x]].begin(),list[top[x]].end(),w[x]));list[top[x]].insert(lower_bound(list[top[x]].begin(),list[top[x]].end(),y),y);w[x]=y;}if (z==2) {w[++n]=y;fa[n]=x;root=top[x];block.addedge(x,n);if(size[root]<border){size[root]++;list[top[x]].insert(lower_bound(list[root].begin(),list[root].end(),y),y);top[n]=root;} else{size[n]=1;top[n]=n;list[n].push_back(y);b.addedge(top[x],n);}}}
}