题解 P2137 【Gty的妹子树】
Mr_Spade
2018-07-10 20:54:32
为什么这道题没有题解啊，那不如我来贡献一发吧。
做完之后去网上搜了一下其它做法，发现居然要树分块，这不是超麻烦的吗。所以我们可以考虑另一种分块方法：对**时间**分块。
对时间分治是需要离线的，但是对时间分块是可以在线的。
我们先可以考虑静态的情况，如果这道题是静态的询问，那么我们只要根据dfs序列建一棵归并树(线段树的一种，每个节点保存这个区间的权值排序过以后的序列)，再进行区间查询就可以了。
那么如果在查询之前进行过若干次修改的话，我们可以暴力扫描一遍这些修改，对查询的答案计算贡献。分两种修改讨论：
如果是修改点权，我们只要先查询这个点是否在被查询的点的子树内，再查询它的修改对答案是否有影响就可以了。
如果是添加一个点，也是类似的，查询是否在这棵子树内以及是否对答案有影响即可。
那么如何查询一个点是否在被查询点的子树内呢？我们可以在添加点的时候预先进行倍增处理这个点向上跳$2^i$层的祖先，这样只要用倍增数组往上跳就可以查询了。
综合一下之前的讨论，如果我们在查询之前的修改不超过$\sqrt m$次时，就在归并树上查询后暴力扫描修改计算贡献；如果修改超过了$\sqrt m$次时，我们只要根据修改重建一下归并树就可以清除掉这些修改，可以发现归并树的重建不会超过$\sqrt m$次。
来分析一下复杂度，为了省事我们把$n$和$m$看成是同阶的，瓶颈显然在暴力扫描计算贡献和归并树的重建上，计算贡献时，最多扫描$O(\sqrt n)$次修改，每次需要$O(\log n)$的复杂度(倍增)，所以这部分的复杂度是$O(n\sqrt n \log n)$。而重建归并树每次是$O(n\log n)$的，一共$O(\sqrt n)$次，因此这部分的复杂度也是$O(n\sqrt n \log n)$。
因此复杂度是$O(n\sqrt n \log n)$，通过了这道题。
细节可以参考代码注释
```cpp
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
using std::upper_bound;
using std::merge;
using std::vector;
inline int read()
{
int res=0;
char x;
while((x=getchar())<'0'||x>'9');
for(;x>='0'&&x<='9';x=getchar())
res=res*10+x-'0';
return res;
}
inline void write(int x)
{
if(x>=10)
write(x/10);
putchar(x%10+'0');
return;
}
const int N=1e5+5,LGN=25;
int n,m,unit,tot,idx,lastans;
int w[N],wi[N],id[N],deep[N],size[N];
int p[N][LGN];//倍增数组
int v[N<<1],first[N],next[N<<1];
struct cell
{
int opt,u,x,y;
};
vector<cell> V;
struct node
{
int l,r;
vector<int> V;
}sgt[N<<2];
void build(int now,int l,int r)//构建归并树
{
sgt[now].l=l;sgt[now].r=r;
sgt[now].V.clear();
if(l==r)
{
sgt[now].V.push_back(wi[l]);
return;
}
int mid=(l+r)>>1;
build(now<<1,l,mid);
build(now<<1|1,mid+1,r);
sgt[now].V.resize(r-l+1);
merge(sgt[now<<1].V.begin(),sgt[now<<1].V.end(),sgt[now<<1|1].V.begin(),sgt[now<<1|1].V.end(),sgt[now].V.begin());
return;
}
int query(int now,int l,int r,int k)//查询
{
if(sgt[now].l>r||sgt[now].r<l)
return 0;
if(sgt[now].l>=l&&sgt[now].r<=r)
return sgt[now].V.end()-upper_bound(sgt[now].V.begin(),sgt[now].V.end(),k);
return query(now<<1,l,r,k)+query(now<<1|1,l,r,k);
}
inline void add_edge(int from,int to)
{
tot+=2;
v[tot+1]=from;v[tot]=to;
next[tot]=first[from];first[from]=tot;
next[tot+1]=first[to];first[to]=tot+1;
return;
}
void dfs(int now,int father)//dfs，用于在重建归并树之前更新一些数据
{
register int go;
id[now]=++idx;size[now]=1;
wi[id[now]]=w[now];/*这个是为了方便建归并树*/p[now][0]=father;
for(go=first[now];go;go=next[go])
if(v[go]!=father)
{
deep[v[go]]=deep[now]+1;
dfs(v[go],now);
size[now]+=size[v[go]];
}
return;
}
inline bool anc(int u,int v)//查询v是否在u的子树内
{
int res=v;
register int i;
if(deep[v]<deep[u])
return 0;
for(i=20;~i;i--)
if((deep[v]-deep[u])>>i&1)
res=p[res][i];
return res==u;
}
inline void rebuild()//更新并重建
{
V.clear();
idx=0;dfs(1,0);
build(1,1,n);
return;
}
signed main()
{
int from,to;
int u,x,res;
register int i,j;
n=read();
for(i=1;i<=n-1;i++)
{
from=read();to=read();
add_edge(from,to);
}
for(i=1;i<=n;i++)
w[i]=read();
idx=0;dfs(1,0);
for(i=1;i<=n;i++)
for(j=1;j<=20;j++)
p[i][j]=p[p[i][j-1]][j-1];
build(1,1,n);
m=read();unit=ceil(sqrt(m)*5);//块大小
while(m--)
switch(read())
{
case 0:
u=read()^lastans;x=read()^lastans;
res=query(1,id[u],id[u]+size[u]-1,x);
for(i=0;i<(int)V.size();i++)
if(V[i].opt==1)
{
if(((V[i].x>x)^(V[i].y>x))&&anc(u,V[i].u))
res+=(V[i].y>x)?1:-1;
}
else
{
if((V[i].y>x)&&anc(u,V[i].u))
res++;
}
write(lastans=res);putchar('\n');
break;
case 1:
u=read()^lastans;x=read()^lastans;
V.push_back(cell{1,u,w[u],x});w[u]=x;
if((int)V.size()>=unit)
rebuild();
break;
case 2:
u=read()^lastans;x=read()^lastans;
V.push_back(cell{2,n+1,u,x});
add_edge(u,++n);
w[n]=x;deep[n]=deep[u]+1;
p[n][0]=u;
for(i=1;i<=20;i++)
p[n][i]=p[p[n][i-1]][i-1];
if((int)V.size()>=unit)
rebuild();
break;
}
return 0;
}
```