[BZOJ4129]Haruna’s Breakfast（树上带修改莫队+权值分块）

=== ===

这里放传送门

=== ===

题解

mex这个东西非常讨厌啊，没有办法合并也没有办法前缀和之类的。 但是这个题的话它最多只有n个数，也就是说它的mex值一定在[0..n]这个区间之内。 那么如果我们用分块维护mex的话，可以维护每个块内的数有没有全部出现过，如果没有全部出现过就可以暴力进去找到底是谁没有出现过。 这样的话修改是O(1)的。

修改这么快那就可以跑莫队辣 树上带修莫队。。跟糖果公园那个超级卡评测题的做法是基本上一样的。 树上莫队之类的话可以看一下BZOJ3757苹果树 带修莫队之类的话可以看一下BZOJ2120数颜色 然后就把这些东西拼拼凑凑就出来这个题了= =

莫队这玩意儿复杂度太玄了。。树分块开到n√大数据就1.1s+，如果换成n23大数据就0.5s+。。而且常数写不好还死T死T的。。。重点就是把修改部分的常数搞得好一点就差不多了。

代码

#include<cmath> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,m,v[50010],p[50010],a[100010],next[100010],pos[50010],tblock,vblock,vcnt,tot,tail,vpos[50010]; int deep[50010],gcnt,qcnt,st[50010],top,bcnt,len[400],fa[50010][18],sum[400],cnt[50010],last[50010]; int w[50010],wcnt,lca,ans[50010]; bool ext[50010]; struct question{ int u,v,tim,id; }q[50010]; struct changes{ int u,to,PRe; }g[50010]; void add(int x,int y){ tot++;a[tot]=y;next[tot]=p[x];p[x]=tot; } int comp(question x,question y){ if (pos[x.u]==pos[y.u]&&pos[x.v]==pos[y.v]) return x.tim<y.tim; if (pos[x.u]==pos[y.u]) return pos[x.v]<pos[y.v]; return pos[x.u]<pos[y.u]; } void dfs(int u,int father){ int bot=top; deep[u]=deep[father]+1; w[u]=++wcnt; for (int i=1;i<=16;i++) fa[u][i]=fa[fa[u][i-1]][i-1]; for (int i=p[u];i!=0;i=next[i]) if (a[i]!=father){ int v=a[i];fa[v][0]=u; dfs(a[i],u); if (top-bot>=tblock){ ++bcnt;//对每个节点维护它自己的栈底 while (top!=bot) pos[st[top--]]=bcnt; } } st[++top]=u; } void change(int u){ ext[u]^=1; if (v[u]>n) return; if (ext[u]==true){ ++cnt[v[u]]; if (cnt[v[u]]==1) ++sum[vpos[v[u]]]; }else{ --cnt[v[u]]; if (cnt[v[u]]==0) --sum[vpos[v[u]]]; } } void Time(int i){ for (int j=q[i-1].tim+1;j<=q[i].tim;j++) if (ext[g[j].u]==true){ change(g[j].u);v[g[j].u]=g[j].to;change(g[j].u); }else v[g[j].u]=g[j].to; for (int j=q[i-1].tim;j>q[i].tim;j--) if (ext[g[j].u]==true){ change(g[j].u);v[g[j].u]=g[j].pre;change(g[j].u); }else v[g[j].u]=g[j].pre; } int find_lca(int x,int y){ if (deep[x]!=deep[y]){ if (deep[x]<deep[y]) swap(x,y); for (int i=17;i>=0;i--) if (deep[fa[x][i]]>=deep[y]) x=fa[x][i]; } for (int i=17;i>=0;i--) if (fa[x][i]!=fa[y][i]){ x=fa[x][i];y=fa[y][i]; } while (x!=y){ x=fa[x][0];y=fa[y][0]; } return x; } void move(int u,int v){ while (u!=v){ if (deep[u]<deep[v]) swap(u,v); change(u);u=fa[u][0]; } } int find_mex(){ for (int i=1;i<=vcnt;i++) if (sum[i]<vblock) for (int j=len[i-1]+1;j<=len[i];j++) if (cnt[j]==0) return j; } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++){ scanf("%d",&v[i]); last[i]=v[i];//为了提前把修改做一遍所以要另存一下权值 } for (int i=1;i<n;i++){ int x,y;scanf("%d%d",&x,&y); add(x,y);add(y,x); } for (int i=1;i<=m;i++){ int k,u,v;scanf("%d%d%d",&k,&u,&v); if (k==0){ ++gcnt;//记下修改操作，注意是pre和to两个域 g[gcnt].u=u;g[gcnt].to=v; g[gcnt].pre=last[u];last[u]=v; }else{ ++qcnt;q[qcnt].id=qcnt; if (w[u]>w[v]) swap(u,v);//两个端点要按照dfs序排列，减少不必要的移动 q[qcnt].u=u;q[qcnt].v=v;q[qcnt].tim=gcnt; } } tblock=floor(pow(n,2.0/3.0));//注意块的大小 vblock=floor(sqrt(n)); dfs(1,0);++bcnt; while (top!=0) pos[st[top--]]=bcnt;//栈内剩下的元素出栈 sort(q+1,q+qcnt+1,comp); len[0]=-1;//第0个块的结尾设为-1，这样在find_mex中才能访问到第1个块的起点0 for (int i=0;i<=n;i=tail+1){ tail=min(i+vblock-1,n); ++vcnt;//对权值分块 len[vcnt]=tail; for (int j=i;j<=tail;j++) vpos[j]=vcnt; } Time(1);//维护时间 move(q[1].u,q[1].v); lca=find_lca(q[1].u,q[1].v);//注意节点的lca要单独计算 change(lca); ans[q[1].id]=find_mex(); change(lca); for (int i=2;i<=qcnt;i++){ Time(i); move(q[i-1].u,q[i].u); move(q[i-1].v,q[i].v); lca=find_lca(q[i].u,q[i].v); change(lca); ans[q[i].id]=find_mex(); change(lca); } for (int i=1;i<=qcnt;i++) printf("%d\n",ans[i]); return 0; }