原文链接www.cnblogs.com/zhouzhendong/p/UOJ435.html
前言
分块题果然是我这种蒟蒻写不动的。由于种种原因，我写代码的时候打错了很多东西，最致命的是数组开小了。**windows不能检测数组越界，能眼查出来这运气是真的好。
题解
首先树链剖分，把问题转化为序列上的问题。
然后我们分块。
考虑如何维护每一块的答案。
初始时，我们预处理将每一块的相同值元素合并。
考虑修改操作：
如果是整块修改，那么临界指针位移即可。
否则就是零散修改，我们可以直接重构整个块。由于时间复杂度要求比较紧，所以我们需要想一个不带 log 的重构方法。
首先一个棘手的问题就是我们难以在不带 log 的前提下对要修改的值在块内有序序列中的定位。
于是我们考虑再维护一个不离散化的有序表，并提前处理出每一个值在这个有序表中的位置。这样，我们在修改了一些值之后，只需要做一次对两个有序表进行归并即可。
（写完代码后才发现似乎可以简单些……）
由于套了一层树链剖分，所以看起来时间复杂度是 $O(m\sqrt{n}\log n)$ 的。
但是仔细看可以发现，单次操作中，整块修改的次数是 $O(\sqrt n)$ 的，块内重构的次数是 $O(\sqrt n\log n)$ 的。
于是，通过调整块大小，就可以得到了一个 $O(n\sqrt{n \log n})$ 的算法。
代码
#include <bits/stdc++.h>
#define clr(x) memset(x,0,sizeof (x))
#define For(i,a,b) for (int i=a;i<=b;i++)
#define Fod(i,b,a) for (int i=b;i>=a;i--)
#define pb(x) push_back(x)
using namespace std;
typedef long long LL;
LL read(){
LL x=0,f=0;
char ch=getchar();
while (!isdigit(ch))
f|=ch=='-',ch=getchar();
while (isdigit(ch))
x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return f?-x:x;
}
const int N=100005;
int n,m,type;
int a[N];
vector <int> e[N];
int fa[N],depth[N],size[N],son[N],top[N],I[N],O[N],aI[N];
void dfs1(int x,int pre,int d){
fa[x]=pre,depth[x]=d,size[x]=1,son[x]=0;
for (auto y : e[x])
if (y!=pre){
dfs1(y,x,d+1);
size[x]+=size[y];
if (!son[x]||size[y]>size[son[x]])
son[x]=y;
}
}
int Time=0;
void dfs2(int x,int Top){
I[x]=++Time;
aI[Time]=x;
top[x]=Top;
if (son[x])
dfs2(son[x],Top);
for (auto y : e[x])
if (y!=fa[x]&&y!=son[x])
dfs2(y,y);
O[x]=Time;
}
int lastans=0;
const int B=50;
int v[N/B+5][B+5],c[N/B+5][B+5],v2[N/B+5][B+5];
int cnt[N/B+5],d[N/B+5],p[N/B+5],tot[N/B+5],cnt2[N/B+5];
int pos[N];
int bid(int x){
return x==0?-1:(x-1)/B;
}
void getv(int b){
v[b][1]=a[v2[b][1]];
c[b][1]=cnt[b]=1;
For(i,2,cnt2[b]){
if (a[v2[b][i]]==a[v2[b][i-1]])
c[b][cnt[b]]++;
else {
c[b][++cnt[b]]=1;
v[b][cnt[b]]=a[v2[b][i]];
}
}
tot[b]=d[b]=0,p[b]=cnt[b]+1;
while (p[b]>1&&v[b][p[b]-1]>0)
tot[b]+=c[b][--p[b]];
}
void rebuild(int b,int L,int R,int v){
static int f[B+5],tmp[B+5],id[B+5];
For(i,1,cnt2[b])
a[v2[b][i]]+=d[b];
d[b]=0,clr(f),clr(tmp);
For(i,L,R){
int x=aI[i],ps=pos[x];
f[ps]=1,tmp[ps]=x,a[x]+=v;
}
int idc=0,i=1,j=1;
while (1){
while (i<=cnt2[b]&&f[i])
i++;
while (j<=cnt2[b]&&!f[j])
j++;
if (i>cnt2[b]&&j>cnt2[b])
break;
if (i<=cnt2[b]&&(j>cnt2[b]||a[v2[b][i]]<a[tmp[j]]))
id[++idc]=v2[b][i++];
else
id[++idc]=tmp[j++];
}
cnt2[b]=idc;
For(i,1,idc)
v2[b][i]=id[i];
For(i,1,cnt2[b])
pos[v2[b][i]]=i;
getv(b);
}
void Upd(int L,int R,int w){
int Lid=bid(L),Rid=bid(R);
if (Lid==Rid)
rebuild(Lid,L,R,w);
else {
rebuild(Lid,L,(Lid+1)*B,w);
rebuild(Rid,Rid*B+1,R,w);
For(i,Lid+1,Rid-1){
d[i]+=w;
while (p[i]<=cnt[i]&&v[i][p[i]]+d[i]<=0)
tot[i]-=c[i][p[i]++];
while (p[i]>1&&v[i][p[i]-1]+d[i]>0)
tot[i]+=c[i][--p[i]];
}
}
}
bool cmp(int x,int y){
return a[x]<a[y];
}
void update(int x,int y,int v){
int fx=top[x],fy=top[y];
while (fx!=fy){
if (depth[fx]<depth[fy])
swap(fx,fy),swap(x,y);
Upd(I[fx],I[x],v);
x=fa[fx],fx=top[x];
}
if (depth[x]>depth[y])
swap(x,y);
Upd(I[x],I[y],v);
}
int Query_block(int L,int R){
int ans=0,Lid=bid(L),Rid=bid(R);
if (Lid==Rid){
For(i,L,R)
ans+=a[aI[i]]+d[Lid]>0;
}
else {
Fod(i,(Lid+1)*B,L)
ans+=a[aI[i]]+d[Lid]>0;
For(i,Rid*B+1,R)
ans+=a[aI[i]]+d[Rid]>0;
For(i,Lid+1,Rid-1)
ans+=tot[i];
}
return ans;
}
int Query(int x,int y){
int ans=0,fx=top[x],fy=top[y];
while (fx!=fy){
if (depth[fx]<depth[fy])
swap(fx,fy),swap(x,y);
ans+=Query_block(I[fx],I[x]);
x=fa[fx],fx=top[x];
}
if (depth[x]>depth[y])
swap(x,y);
ans+=Query_block(I[x],I[y]);
return ans;
}
int main(){
n=read(),m=read(),type=read();
For(i,1,n-1){
int x=read(),y=read();
e[x].pb(y),e[y].pb(x);
}
For(i,1,n)
a[i]=read();
dfs1(1,0,0);
dfs2(1,1);
For(i,1,n){
int b=bid(I[i]);
v2[b][++cnt2[b]]=i;
}
int mxb=bid(n);
For(i,0,mxb){
sort(v2[i]+1,v2[i]+cnt2[i]+1,cmp);
For(j,1,cnt2[i])
pos[v2[i][j]]=j;
getv(i);
}
while (m--){
int op=read();
if (op==1){
int x=read(),y=read(),w=read();
if (type)
x^=lastans,y^=lastans;
update(x,y,w);
}
else if (op==2){
int x=read(),y=read();
if (type)
x^=lastans,y^=lastans;
printf("%d\n",lastans=Query(x,y));
}
else if (op==3){
int x=read();
if (type)
x^=lastans;
printf("%d\n",lastans=Query_block(I[x],O[x]));
}
}
return 0;
}
