【BZOJ3052】[wc2013]糖果公园

Description

Input

Output

Sample Input

Sample Input

Sample Output

84

131

27

84

HINT

题解：区间中的带修改的莫队做法：将块的大小设为n^2/3，将所有询问按照(l所在块，r所在块，time)排序，每次暴力移动三个指针即可。

树上莫队做法：将树按siz分块(如果fa的siz<B则加入到fa的块中，否则新建一块)，将询问按(l所在块，r的DFS序)排序，每次暴力移动两个指针即可。

但是当我们扫过移动指针时，需要将经过的所有点的状态取反。但是这能处理边权。所以我们要将LCA单独拿出来特判。

所以带修改的树上莫队呢~将两者合起来就行了。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;const int maxn=100010;typedef long long ll;int n,m,q,now,tot,B,sum,cnt,flag;ll ans,f[maxn],v[maxn],w[maxn];int fa[18][maxn],next[maxn<<1],to[maxn<<1],head[maxn],dep[maxn],siz[maxn],bel[maxn];int pa[maxn],pb[maxn],pc[maxn],last[maxn],s[maxn],vis[maxn],c[maxn];struct node{	int a,b,tim,org;}p[maxn];int rd(){	int ret=0,f=1;	char gc=getchar();	while(gc<'0'||gc>'9')	{if(gc=='-')f=-f;	gc=getchar();}	while(gc>='0'&&gc<='9')	ret=ret*10+gc-'0',gc=getchar();	return ret*f;}void add(int a,int b){	to[++cnt]=b,next[cnt]=head[a],head[a]=cnt;}void dfs(int x){	if(x==1||siz[bel[fa[0][x]]]==B)	bel[x]=++sum;	else	bel[x]=bel[fa[0][x]];	siz[bel[x]]++;	for(int i=head[x];i;i=next[i])	if(!dep[to[i]])	fa[0][to[i]]=x,dep[to[i]]=dep[x]+1,dfs(to[i]);}bool cmp(node a,node b){	return (bel[a.a]==bel[b.a])?((bel[a.b]==bel[b.b])?(a.tim
           
            
             
              dep[b]) rev(a),a=fa[0][a]; while(a!=b) rev(a),rev(b),a=fa[0][a],b=fa[0][b];}int lca(int a,int b){ if(dep[a]
              
               =0;i--) if(dep[fa[i][a]]>=dep[b]) a=fa[i][a]; if(a==b) return a; for(int i=17;i>=0;i--) if(fa[i][a]!=fa[i][b]) a=fa[i][a],b=fa[i][b]; return fa[0][a];}int main(){ n=rd(),m=rd(),q=rd(); int i,j,a,b,lc; for(i=1;i<=m;i++) v[i]=rd(); for(i=1;i<=n;i++) w[i]=rd(); for(i=1;i
               
                p[i].tim) { if(vis[pa[now]]) rev(pa[now]),c[pa[now]]=pc[now],rev(pa[now]); c[pa[now]]=pc[now],now--; } f[p[i].org]=ans,rev(lc); } for(i=1;i<=q-tot;i++) printf("%lld\n",f[i]); return 0;}//4 3 5 1 9 2 7 6 5 1 2 3 3 1 3 4 1 2 3 2 1 1 2 1 4 2 0 2 1 1 1 2 1 4 2