[BZOJ4129]Haruna’s Breakfast（樹上帶修改莫隊+分塊）

2019-11-06 06:13:34

字體：大中小

來源：轉載

供稿：網友

題目描述

傳送門

題解

樹上帶修改莫隊的方法是裸題對吧。。關鍵是怎么查詢一種比較好的方法是將權值分塊，每一個塊記錄出現過了幾個權值，然后可以做到O(1) $O(1)$ 修改；查詢的時候暴力枚舉權值沒有全部出現的塊，然后再在塊內暴力找到第一個沒出現的權值，所以是O(n√) $O(/sqrt n)$ 查詢我的方法好蠢啊，就是需要將所有的權值離散，并且如果兩個權值不相鄰的話還需要再中間插入一個權值（較小的+1），并且還需要加入0和最大的權值+1這兩個權值但是實際上更優(yōu)越的做法是（orz ATP），因為是查詢mex，并且一共就有n個數，所以mex不會超過[0..n]的范圍。所以只需要對[0..n]分塊，其余的直接扔掉就可以了

代碼

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;#define N 200005#define sz 16int n,m,x,y,cc,cq,a[N];int tot,point[N],nxt[N*2],v[N*2];int b,tr,dfs_clock,belong[N],stack[N],top,in[N],f[N][sz+3],h[N];struct data{int x,y,r,t,id,ans;}ch[N],q[N];int lsh[N],LSH;int now,block,t,last[N],cnt[N],sum[N],num[N],L[N],R[N];bool ext[N];void add(int x,int y){ ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y;}void dfs(int x,int fa){ in[x]=+dfs_clock;h[x]=h[fa]+1; for (int i=1;i<sz;++i) f[x][i]=f[f[x][i-1]][i-1]; int bottom=top; for (int i=point[x];i;i=nxt[i]) if (v[i]!=fa) { f[v[i]][0]=x; dfs(v[i],x); if (top-bottom>=b) { ++tr; while (top!=bottom) belong[stack[top--]]=tr; } } stack[++top]=x;}int lca(int x,int y){ if (h[x]<h[y]) swap(x,y); int k=h[x]-h[y]; for (int i=0;i<sz;++i) if ((k>>i)&1) x=f[x][i]; if (x==y) return x; for (int i=sz-1;i>=0;--i) if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i]; return f[x][0];}int cmp(data a,data b){ return belong[a.x]<belong[b.x]|| (belong[a.x]==belong[b.x]&&belong[a.y]<belong[b.y])|| (belong[a.x]==belong[b.x]&&belong[a.y]==belong[b.y]&&a.t<b.t);}int find(int x){ int l=1,r=LSH,mid,ans; while (l<=r) { mid=(l+r)>>1; if (lsh[mid]>=x) ans=mid,r=mid-1; else l=mid+1; } return ans;}void change(int x,int val){ if (val==1) { if (!cnt[x]) ++sum[num[x]]; ++cnt[x]; } else { --cnt[x]; if (!cnt[x]) --sum[num[x]]; }}int query(){ for (int i=1;i<=t;++i) if (sum[i]<R[i]-L[i]+1) { for (int j=L[i];j<=R[i];++j) if (!cnt[j]) return j; }}void rev(int x){ if (ext[x]) change(a[x],-1); else change(a[x],1); ext[x]^=1;}void modui(int x,int y){ if (h[x]<h[y]) swap(x,y); while (h[x]>h[y]&&x!=y) rev(x),x=f[x][0]; if (h[x]>h[y]) return; while (x!=y) { rev(x);rev(y); x=f[x][0],y=f[y][0]; }}int main(){ scanf("%d%d",&n,&m); for (int i=1;i<=n;++i) scanf("%d",&a[i]),lsh[++LSH]=a[i]; for (int i=1;i<n;++i) { scanf("%d%d",&x,&y); add(x,y),add(y,x); } b=(int)pow(n,2.0/3.0);dfs(1,0); while (top) belong[stack[top--]]=tr; for (int i=1;i<=m;++i) { int opt;scanf("%d",&opt); if (opt==0) { ++cc; scanf("%d%d",&ch[cc].x,&ch[cc].y); lsh[++LSH]=ch[cc].y; } else { ++cq;scanf("%d%d",&q[cq].x,&q[cq].y); q[cq].id=cq;q[cq].t=cc;q[cq].r=lca(q[cq].x,q[cq].y); if (in[q[cq].x]>in[q[cq].y]) swap(q[cq].x,q[cq].y); } } sort(lsh+1,lsh+LSH+1);lsh[LSH+1]=lsh[LSH]+1;++LSH; LSH=unique(lsh+1,lsh+LSH+1)-lsh-1; for (int i=1,j=LSH;i<j;++i) if (lsh[i+1]-lsh[i]>1) lsh[++LSH]=lsh[i]+1; if (lsh[1]!=0) lsh[++LSH]=0; sort(lsh+1,lsh+LSH+1);LSH=unique(lsh+1,lsh+LSH+1)-lsh-1; for (int i=1;i<=n;++i) a[i]=find(a[i]); for (int i=1;i<=cc;++i) ch[i].y=find(ch[i].y); block=sqrt(LSH);t=(LSH-1)/block+1; for (int i=1;i<=LSH;++i) num[i]=(i-1)/block+1; L[1]=1,R[1]=block; for (int i=2;i<=t;++i) L[i]=L[i-1]+block,R[i]=R[i-1]+block;R[t]=LSH; sort(q+1,q+cq+1,cmp);now=q[1].t; for (int i=1;i<=q[1].t;++i) { last[i]=a[ch[i].x]; a[ch[i].x]=ch[i].y; } modui(q[1].x,q[1].y); change(a[q[1].r],1); q[q[1].id].ans=query(); change(a[q[1].r],-1); for (int i=2;i<=cq;++i) { if (now<q[i].t) { for (int j=now+1;j<=q[i].t;++j) { if (ext[ch[j].x]) change(a[ch[j].x],-1),change(ch[j].y,1); last[j]=a[ch[j].x]; a[ch[j].x]=ch[j].y; } } else { for (int j=now;j>q[i].t;--j) { if (ext[ch[j].x]) change(a[ch[j].x],-1),change(last[j],1); a[ch[j].x]=last[j]; } } now=q[i].t; modui(q[i-1].x,q[i].x); modui(q[i-1].y,q[i].y); int fa=q[i].r; change(a[fa],1); q[q[i].id].ans=query(); change(a[fa],-1); } for (int i=1;i<=cq;++i) { q[i].ans=lsh[q[i].ans];