BZOJ 4129: Haruna’s Breakfast

经典题目。

分块还是有点用的，可以支持O(1)单点修改，O(sqrt(n))区间查询，我想反之亦然吧。

AC code

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<cmath>
#define maxn 100005
#define lim 18
using namespace std;

int n,m,s[maxn],fa[maxn],S,T,seq[maxn],dep[maxn],ans[maxn],f[lim][maxn];
int info[maxn],Prev[maxn*2],to[maxn*2],cnt_e;
inline void Node(int u,int v){ Prev[++cnt_e]=info[u],info[u]=cnt_e,to[cnt_e]=v; }

int pre[maxn],nxt[maxn],loc[maxn];

int x[maxn],y[maxn],bl[maxn],c[maxn],tim[maxn],cnt_bl,cnt_q,cnt_cg;
int tp,Q[maxn];
void dfs(int now,int ff)
{
	dep[now]=dep[f[0][now]=fa[now]=ff]+1;
	int bt=tp;
	for(int i=info[now];i;i=Prev[i])
		if(to[i]!=ff)
		{
			dfs(to[i],now);
			if(tp-bt>=S)
			{
				++cnt_bl;
				for(;tp>bt;bl[Q[--tp]]=cnt_bl);
			}
		}
	Q[tp++]=now;
}

int Lca(int u,int v)
{
	if(dep[v]<dep[u]) swap(u,v);
	for(int i=0;i<lim && dep[v]-dep[u];i++)
		if((dep[v]-dep[u]) & (1<<i))
			v=f[i][v];
	if(u==v) return u;
	for(int i=lim-1;i>=0;i--)
		if(f[i][u]!=f[i][v])
			u=f[i][u],v=f[i][v];
	return f[0][u];
}

inline bool cmp(const int &a,const int &b)
{
	return bl[x[a]]==bl[x[b]]?bl[y[a]]==bl[y[b]]?tim[a]<tim[b]:bl[y[a]]<bl[y[b]]:bl[x[a]]<bl[x[b]];
}

int sum[maxn],sizlb[maxn],sbl[maxn];

void insert(int loc){if(loc<=n)sizlb[sbl[loc]]+=sum[loc]++==0;}
void erase(int loc){ if(loc<=n)sizlb[sbl[loc]]-=--sum[loc]==0;}
int Query_mex()
{ 
	for(int i=0;;i++)
		if(sizlb[i]<T)
		{
			for(int j=0;j<T;j++)
				if(!sum[i*T+j])
					return i*T+j;
		}
}

bool vis[maxn];

void modify(int loc)
{
	vis[loc]^=1;
	if(vis[loc]) insert(s[loc]);
	else erase(s[loc]);
}

void Move(int a,int b,int c,int d,int t1,int t2)
{
	while(t1>t2)
	{
		if(vis[loc[t1]])
		{
			erase(nxt[t1]);
			s[loc[t1]]=pre[t1];
			insert(pre[t1--]);
		}
		else s[loc[t1]]=pre[t1--];
	}
	while(t1<t2)
	{
		if(vis[loc[++t1]])
		{
			erase(pre[t1]);
			s[loc[t1]]=nxt[t1];
			insert(nxt[t1]);
		}
		else s[loc[t1]]=nxt[t1];
	}
	if(dep[a]>dep[c]) swap(a,c);
	for(;dep[a]<dep[c];) modify(c),c=fa[c];
	for(;a!=c;) modify(a),modify(c),a=fa[a],c=fa[c];
	if(dep[b]>dep[d]) 
		swap(b,d);
	for(;dep[b]<dep[d];) 
		modify(d),d=fa[d];
	for(;b!=d;) modify(b),modify(d),b=fa[b],d=fa[d];
}


int main()
{
	
	//freopen("1.in","r",stdin);
	
	int u,v,tag;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&s[i]),seq[i]=s[i];
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&u,&v);
		Node(u,v),Node(v,u);
	}
	S=pow(n,0.66);
	dfs(1,0);
	
	for(int j=1;j<lim;j++)
		for(int i=1;i<=n;i++)
			f[j][i]=f[j-1][f[j-1][i]];
	for(int i=1;i<=m;i++)
	{
		scanf("%d",&tag);
		if(tag==1)
		{
			++cnt_q;
			scanf("%d%d",&x[cnt_q],&y[cnt_q]);
			c[cnt_q]=cnt_q;
			tim[cnt_q]=cnt_cg;
		}
		else
		{
			++cnt_cg;
			scanf("%d%d",&u,&v);
			loc[cnt_cg]=u;
			pre[cnt_cg]=seq[u];
			nxt[cnt_cg]=(seq[u]=v);
		}
	}
	
	sort(c+1,c+1+cnt_q,cmp);
	
	T=ceil(sqrt(n+2));
	for(int i=0;i<=n;i++) sbl[i]=i/T; 
	
	x[c[0]]=1,y[c[0]]=1;
	for(int i=1;i<=cnt_q;i++)
	{
		Move(x[c[i-1]],y[c[i-1]],x[c[i]],y[c[i]],tim[c[i-1]],tim[c[i]]);
		insert(s[Lca(x[c[i]],y[c[i]])]);
		ans[c[i]]=Query_mex();
		erase(s[Lca(x[c[i]],y[c[i]])]);
	}
		
	for(int i=1;i<=cnt_q;i++)
		printf("%d\n",ans[i]);
}