[bzoj4129][树上带修莫队][分块]Haruna’s Breakfast

本文主要是介绍[bzoj4129][树上带修莫队][分块]Haruna’s Breakfast，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

Haruna每天都会给提督做早餐！这天她发现早饭的食材被调皮的 Shimakaze放到了一棵

树上，每个结点都有一样食材，Shimakaze要考验一下她。每个食材都有一个美味度，Shimakaze会进行两种操作：
1、修改某个结点的食材的美味度。 2、对于某条链，询问这条链的美味度集合中，最小的未出现的自然数是多少。即mex值。
请你帮帮Haruna吧。

Input

第一行包括两个整数n，m，代表树上的结点数(标号为1~n)和操作数。

第二行包括n个整数a1…an，代表每个结点的食材初始的美味度。接下来n-1行，每行包括两个整数u，v，代表树上的一条边。接下来m
行，每行包括三个整数 0 u x 代表将结点u的食材的美味度修改为 x。 1 u v 代表询问以u，v 为端点的链的mex值。

Output

对于每次询问，输出该链的mex值。

Sample Input

10 10

1 0 1 0 2 4 4 0 1 0

1 2

2 3

2 4

2 5

1 6

6 7

2 8

3 9

9 10

0 7 14

1 6 6

0 4 9

1 2 2

1 1 8

1 8 3

0 10 9

1 3 5

0 10 0

0 7 7

Sample Output

0

1

2

2

3

HINT

1<=n<=5*10^4

1<=m<=5*10^4

0<=ai<=10^9

题解

学了一发树上莫队
~~按括号序搞的好资瓷啊我就不树上分块了吧~~
来一发括号序其实就是每个点在访问完他的子树后再向DFS序列中加入他
两个点的路径就可以用他们之间的括号序表示出来
注意括号序在前的点要用他出dfs的编号在后的要用进dfs的编号
如此不在路径上的点要不被算了两次要不一次都没有被计算
莫队的时候判掉即可
注意LCA是否在这两个点的情况
如果LCA不在这两个点那在莫队完之后你还要暴力把LCA的贡献加入再计算答案
因为LCA不在括号序中
这题再对权值分一下块…
就没了
~~真的难码啊~~

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#define LL long long
#define mp(x,y) make_pair(x,y)
using namespace std;
inline int read()
{int f=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
inline void write(int x)
{if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');
}
inline void print(int x){write(x);printf(" ");}
struct node{int x,y,next;}a[210000];int len,last[110000];
void ins(int x,int y){len++;a[len].x=x;a[len].y=y;a[len].next=last[x];last[x]=len;}
int pa[110000],in[110000],ot[110000],dfn;
int fa[110000][25],bin[25],dep[110000];
void pre_tree_node(int x)
{in[x]=++dfn;pa[dfn]=x;for(int i=1;bin[i]<=dep[x];i++)fa[x][i]=fa[fa[x][i-1]][i-1];for(int k=last[x];k;k=a[k].next){int y=a[k].y;if(y!=fa[x][0]){fa[y][0]=x;dep[y]=dep[x]+1;pre_tree_node(y);}}ot[x]=++dfn;pa[dfn]=x;
}
int lca(int x,int y)
{if(dep[x]<dep[y])swap(x,y);for(int i=20;i>=0;i--)if(bin[i]<=dep[x]&&dep[fa[x][i]]>=dep[y])x=fa[x][i];if(x==y)return x;for(int i=20;i>=0;i--)if(bin[i]<=dep[x]&&fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];return fa[x][0];
}
struct modify{int u,c,pre;}B[210000];int l2;
struct ask{int l,r,T,op;}A[110000];int l1;
int pos[110000],block;
bool cmp(ask n1,ask n2)
{if(pos[n1.l]!=pos[n2.l])return pos[n1.l]<pos[n2.l];if(pos[n1.r]!=pos[n2.r])return pos[n1.r]<pos[n2.r];return n1.T<n2.T;
}
int n,m;
int hh[110000];
int l,r,vis[110000];
int block1,numb,p1[110000],st[320],ed[320];
int s1[320],s2[320][50005];//这个块里有多少数字  这个块里的这些数字出现了多少次
int col[110000];//这个点当前的数字是什么
void cal(int x,int op)
{int u,p;if(op==1)u=pa[x],p=p1[col[u]];//序列中这个点实际树上的位置 块的位置 else u=x,p=p1[col[u]];if(vis[u]){if(!(--s2[p][col[u]]))s1[p]--;}else{if(!s2[p][col[u]])s1[p]++;s2[p][col[u]]++;}vis[u]^=1;
}
void ch(int u,int c)//把树上点u改成c
{int p=p1[col[u]];if(vis[u]){if(!(--s2[p][col[u]]))s1[p]--;}col[u]=c;p=p1[col[u]];if(vis[u]){if(!s2[p][col[u]])s1[p]++;s2[p][col[u]]++;}
}
void up_time(int t1,int t2)
{for(int i=t1;i>=t2+1;i--)ch(B[i].u,B[B[i].pre].c);for(int i=t1+1;i<=t2;i++)ch(B[i].u,B[i].c);
}
int getmex()
{int i;for(i=1;i<=numb;i++)if(s1[i]!=block1)break;for(int j=(i==1?0:block1*(i-1));j<=block1*i;j++)if(s2[i][j]==0)return j;
}
int ans[110000];
int main()
{bin[0]=1;for(int i=1;i<=20;i++)bin[i]=bin[i-1]<<1;n=read();m=read();memset(hh,-1,sizeof(hh));block1=int(sqrt(double(n)));for(int i=0;i<=n;i++){p1[i]=i/block1+1;if(i!=0&&p1[i]!=p1[i-1])st[p1[i]]=i,ed[p1[i-1]]=i-1;}numb=p1[n];st[1]=0;ed[block1]=n;for(int i=1;i<=n;i++){B[i].c=read(),B[i].u=i;if(B[i].c>n)B[i].c=n;B[i].pre=hh[B[i].u];hh[B[i].u]=i;}for(int i=1;i<n;i++){int x=read(),y=read();ins(x,y);ins(y,x);}pre_tree_node(1);l2=n;for(int i=1;i<=m;i++){int op=read(),x=read(),y=read();if(!op){l2++;B[l2].c=y;B[l2].u=x;if(B[l2].c>n)B[l2].c=n;B[l2].pre=hh[B[l2].u];hh[B[l2].u]=l2;}else {int LA=lca(x,y);if(in[x]>in[y])swap(x,y);if(LA!=x&&LA!=y)A[++l1].l=ot[x],A[l1].r=in[y],A[l1].T=l2,A[l1].op=l1;else A[++l1].l=in[x],A[l1].r=in[y],A[l1].T=l2,A[l1].op=l1;}}
//	for(int i=1;i<=l2;i++)printf("%d   %d %d %d\n",i,B[i].u,B[i].c,B[i].pre);//initblock=pow(n,2.0/3.0);for(int i=1;i<=2*n;i++)pos[i]=(i-1)/block+1;sort(A+1,A+1+l1,cmp);int T=A[1].T;up_time(0,A[1].T);for(int i=A[1].l;i<=A[1].r;i++)cal(i,1);int LA=lca(pa[A[1].l],pa[A[1].r]);if(LA!=pa[A[1].l]&&LA!=pa[A[1].r]){cal(LA,2);ans[A[1].op]=getmex();cal(LA,2);}else ans[A[1].op]=getmex();l=A[1].l;r=A[1].r;for(int i=2;i<=m;i++){up_time(T,A[i].T);T=A[i].T;while(l<A[i].l)cal(l++,1);while(l>A[i].l)cal(--l,1);while(r<A[i].r)cal(++r,1);while(r>A[i].r)cal(r--,1);LA=lca(pa[A[i].l],pa[A[i].r]);if(LA!=pa[A[i].l]&&LA!=pa[A[i].r]){cal(LA,2);ans[A[i].op]=getmex();cal(LA,2);}else ans[A[i].op]=getmex();}for(int i=1;i<=l1;i++)printf("%d\n",ans[i]);return 0;
}