【UOJ#435】【集训队作业2018】Simple Tree 分块+树链剖分

题目大意：

有一棵有根树，根为 1 ，点有点权。
现在有 m 次操作，操作有 3 种：
1 x y w ，将 x 到 y 的路径上的点点权加上 w (其中 $w = \pm 1$

数据范围：$n,m≤10^5$，点权的绝对值$≤10^9$。

这一题正常的做法并不是特别优秀，我们考虑一些分块做法

考虑求一个连续的区间内有多少个数$>0$，我们显然可以将原序列分成$sqrt{n}$块，对于每一个块我们开一个桶存储块内所有数，然后类似前缀和的方式扫一遍，查询一个块就可以$O(1)$实现查询了

修改怎么做？

首先是整个块一起变大/变小的情况，我们对整一块打一个标记$tag[x]$，下次查询时不要查询$>0$的，改为查询块内$>tag[x]$的数的数量。

某个块更改一部分的情况：我们修改原数，然后直接更改该块对应的桶即可，详见代码。

这个做法既然可以针对某一个区间，且资瓷修改。

回到原先的问题中，我们对给出的树树剖一下，每条链我们都分块维护一下，在此不再赘述。

查询某条路径的话，我们将询问拆成$log{n}$条链，分别查询然后加起来即可。

查询某个子树内的话，直接查就可以了。

时间复杂度：$O(n^{1.5}log n)$，代码只要3k。

别想什么树分块！！！

 1 #include<bits/stdc++.h>
 2 #define L long long
 3 #define M 100005
 4 #define N 500
 5 using namespace std;
 6 
 7 int B[M]={0},S[M]={0},tag[M]={0},E[M]={0},pos[M]={0},a[M]={0};short num[M/N+3][M*4]={0};
 8 void upd(short x[],int &y,int Val){if(Val==1) ++x[++y+200002];else --x[y--+200002];}
 9 void updata(int l,int r,int w){
10     if(B[l]==B[r]){for(int i=l;i<=r;i++) upd(num[B[i]],a[i],w); return;}
11     for(int i=l;B[i]==B[l];i++) upd(num[B[i]],a[i],w);
12     for(int i=r;B[i]==B[r];i--) upd(num[B[i]],a[i],w);
13     for(int i=B[l]+1;i<B[r];i++) tag[i]+=w;
14 }
15 L query(int l,int r){
16     L res=0;
17     if(B[l]==B[r]){for(int i=l;i<=r;i++) res+=(a[i]+tag[B[i]]>0); return res;}
18     for(int i=l;B[i]==B[l];i++) res+=(a[i]+tag[B[i]]>0);
19     for(int i=r;B[i]==B[r];i--) res+=(a[i]+tag[B[i]]>0);
20     for(int i=B[l]+1;i<B[r];i++) res+=num[i][200003-tag[i]];
21     return res;
22 }
23 
24 struct edge{int u,next;}e[M*2]={0}; int head[M]={0},use=0;
25 void add(int x,int y){use++;e[use].u=y;e[use].next=head[x];head[x]=use;}
26 int siz[M]={0},son[M]={0},dep[M]={0},fa[M]={0},dfn[M]={0},low[M]={0},top[M]={0},t=0;
27 void dfs(int x){
28     siz[x]=1; dep[x]=dep[fa[x]]+1;
29     for(int i=head[x];i;i=e[i].next) if(e[i].u!=fa[x]){
30         fa[e[i].u]=x; dfs(e[i].u);
31         siz[x]+=siz[e[i].u];
32         if(siz[son[x]]<siz[e[i].u]) son[x]=e[i].u;
33     }
34 }
35 void dfs(int x,int Top){
36     top[x]=Top; dfn[x]=++t;
37     if(son[x]) dfs(son[x],Top);
38     for(int i=head[x];i;i=e[i].next) if(e[i].u!=fa[x]&&e[i].u!=son[x]) dfs(e[i].u,e[i].u);
39     low[x]=t;
40 }
41 
42 L Query(int x,int y){
43     L res=0;
44     for(;top[x]!=top[y];x=fa[top[x]]){
45         if(dep[top[x]]<dep[top[y]]) swap(x,y);
46         res+=query(dfn[top[x]],dfn[x]);
47     }
48     res+=query(min(dfn[x],dfn[y]),max(dfn[x],dfn[y]));
49     return res;
50 }
51 void Updata(int x,int y,int w){
52     for(;top[x]!=top[y];x=fa[top[x]]){
53         if(dep[top[x]]<dep[top[y]]) swap(x,y);
54         updata(dfn[top[x]],dfn[x],w);
55     }
56     updata(min(dfn[x],dfn[y]),max(dfn[x],dfn[y]),w);
57 }
58 
59 #define MFLONG 18000000                                                                          
60 #define NUM(x) ((48<=x&&x<=57)||x=='-')
61 char _c[MFLONG];int _ns=0,_nw=0;int _x[30],_ld;
62 inline void rd(int &_q){int _fu;if(_c[_ns]==0) return;while(!NUM(_c[_ns])) _ns++;if(_c[_ns]=='-') _fu=-1,_ns++;else _fu=1;_q=0;while(NUM(_c[_ns])) _q=_q*10+_c[_ns++]-48;_q=_fu*_q;}
63 
64 int n,m,T,ans=0;
65 int main(){
66     fread(_c,1,MFLONG,stdin);
67     memset(S,1,sizeof(S));
68     rd(n); rd(m); rd(T);
69     for(int i=1;i<=n;i++){
70         B[i]=i/N+1;
71         S[B[i]]=min(S[B[i]],i);
72         E[B[i]]=max(E[B[i]],i);
73     }
74     for(int i=1,x,y;i<n;i++) rd(x),rd(y),add(x,y),add(y,x);
75     dfs(1); dfs(1,1);
76     for(int i=1;i<=n;i++){
77         rd(a[dfn[i]]);
78         if(a[dfn[i]]>1e5) a[dfn[i]]=1e5;
79         if(a[dfn[i]]<-1e5) a[dfn[i]]=-1e5;
80     }
81     for(int x=1;x<=B[n];x++){
82         for(int i=S[x];i<=E[x];i++) ++num[x][a[i]+200002];
83         for(int j=400003;~j;j--) num[x][j]+=num[x][j+1];
84     }
85     while(m--){
86         int op,x,y,w; rd(op); rd(x); x^=T*ans;
87         if(op==3) {printf("%lld
",ans=query(dfn[x],low[x])); continue;}
88         rd(y); y^=T*ans;
89         if(op==2) {printf("%lld
",ans=Query(x,y)); continue;}
90         rd(w); Updata(x,y,w);
91     }
92 }