【bzoj4129】Haruna’s Breakfast 树上莫队+分块

AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=4129

【题解】

这题是糖果公园和mex的结合，仿照糖果公园搞树上莫队，然后分块统计答案。

注意不要把块状树和分块搞混，博主因为这个搞了2天。。。

另外这题跑了7.92s，和糖果公园的100s不成正比，我也只能说莫队是玄学。

/************
  bzoj 4129
  by chty
  2016.12.1
************/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
#define FILE "read"
#define MAXN 50010
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
struct node{int y,next;}e[MAXN*2];
struct NODE{int x,y,id,time,pre;}b[MAXN],c[MAXN];
int n,m,len,cnt1,cnt2,block,top,bcnt;
int a[MAXN],Link[MAXN],pre[MAXN],deep[MAXN],belong[MAXN],vis[MAXN],cnt[MAXN],ans[MAXN],blo[MAXN],stack[MAXN],bin[20],l[MAXN],r[MAXN],Belong[MAXN],anc[MAXN][20];
void insert(int x,int y){e[++len].next=Link[x];Link[x]=len;e[len].y=y;}
namespace INIT{
	char buf[1<<15],*fs,*ft;
	inline char getc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
	inline int read(){
		int x=0,f=1;  char ch=getc();
		while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getc();}
		while(isdigit(ch))  {x=x*10+ch-'0';  ch=getc();}
		return x*f;
	}
}using namespace INIT;
bool operator <(NODE a,NODE b){
	if(belong[a.x]==belong[b.x]&&belong[a.y]==belong[b.y])  return a.time<b.time;
	else if(belong[a.x]==belong[b.x])  return belong[a.y]<belong[b.y];
	else return belong[a.x]<belong[b.x];
}
int dfs(int x){
	int size=0;
	up(i,1,16)if(deep[x]>=bin[i])anc[x][i]=anc[anc[x][i-1]][i-1];else break;
	for(int i=Link[x];i;i=e[i].next)if(e[i].y!=anc[x][0]){
		anc[e[i].y][0]=x;
		deep[e[i].y]=deep[x]+1;
		size+=dfs(e[i].y);
		if(size>=block){
			bcnt++;
			up(j,1,size) belong[stack[top--]]=bcnt;
			size=0;
		}
	}
	stack[++top]=x;
	return size+1;
}
void cal(int x){
	if(a[x]>n)  return;
	if(vis[x])  {if(!--cnt[a[x]])blo[Belong[a[x]]]--;}
	else {if(!cnt[a[x]]++)blo[Belong[a[x]]]++;}
	vis[x]^=1;
}
void change(int x,int v){
	if(vis[x])  {cal(x);  a[x]=v;  cal(x);}
	else a[x]=v;
}
void solve(int x,int y){
	while(x!=y){
		if(deep[x]>deep[y])  cal(x),x=anc[x][0];
		else cal(y),y=anc[y][0];
	}
}
int query(){
	if(!cnt[0])  return 0;
	int i;
	for(i=1;l[i];i++)  if(r[i]-l[i]+1!=blo[i])  break;
	int temp=i;
	up(i,l[temp],r[temp])  if(!cnt[i])  return i;
	return n;
}
int lca(int x,int y){  
    if(deep[x]<deep[y])swap(x,y);  
    int t=deep[x]-deep[y];  
    for(int i=0;bin[i]<=t;i++)if(bin[i]&t)x=anc[x][i];  
    down(i,16,0)if(anc[x][i]!=anc[y][i])x=anc[x][i],y=anc[y][i];  
    if(x==y)return x;  
    return anc[x][0];  
}  
void init(){
	n=read();  m=read();  block=(int)sqrt(n*1.0);
	for(int i=1;(i-1)*block+1<=n;i++)  l[i]=(i-1)*block+1,r[i]=min(i*block,n);
	up(i,1,n)  Belong[i]=(i-1)/block+1;
	up(i,1,n)  pre[i]=a[i]=read();
	bin[0]=1;  up(i,1,16)  bin[i]=bin[i-1]<<1;
	up(i,1,n-1)  {int x=read(),y=read();insert(x,y);insert(y,x);}
	dfs(1);
	while(top)  belong[stack[top--]]=bcnt;
	up(i,1,m){
		int flag=read(),x=read(),y=read();
		if(flag==0) {b[++cnt1].x=x; b[cnt1].y=y; b[cnt1].pre=pre[x]; pre[x]=y;}
		else {c[++cnt2].x=x; c[cnt2].y=y; c[cnt2].time=cnt1; c[cnt2].id=cnt2;}
	}
}
void work(){
	sort(c+1,c+cnt2+1);
	up(i,1,c[1].time)  change(b[i].x,b[i].y);
	solve(c[1].x,c[1].y);  
	int t=lca(c[1].x,c[1].y);
	cal(t);  ans[c[1].id]=query();  cal(t);
	up(i,2,cnt2){
		up(j,c[i-1].time+1,c[i].time)  change(b[j].x,b[j].y);
		down(j,c[i-1].time,c[i].time+1)  change(b[j].x,b[j].pre);
		solve(c[i].x,c[i-1].x);
		solve(c[i].y,c[i-1].y);
		int t=lca(c[i].x,c[i].y);
		cal(t);  ans[c[i].id]=query();  cal(t);
	}
	up(i,1,cnt2)  printf("%d\n",ans[i]);
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	init();
	work();
	return 0;
}