[BZOJ4129]Haruna’s Breakfast（樹上帶修改莫隊(duì)+權(quán)值分塊）

2019-11-06 06:49:39

字體：大中小

供稿：網(wǎng)友

=== ===

這里放傳送門

=== ===

題解

mex這個(gè)東西非常討厭啊，沒有辦法合并也沒有辦法前綴和之類的。但是這個(gè)題的話它最多只有n個(gè)數(shù)，也就是說它的mex值一定在[0..n]這個(gè)區(qū)間之內(nèi)。那么如果我們用分塊維護(hù)mex的話，可以維護(hù)每個(gè)塊內(nèi)的數(shù)有沒有全部出現(xiàn)過，如果沒有全部出現(xiàn)過就可以暴力進(jìn)去找到底是誰沒有出現(xiàn)過。這樣的話修改是O(1)的。

修改這么快那就可以跑莫隊(duì)辣樹上帶修莫隊(duì)。。跟糖果公園那個(gè)~~超級(jí)卡評(píng)測(cè)題~~的做法是基本上一樣的。樹上莫隊(duì)之類的話可以看一下BZOJ3757蘋果樹帶修莫隊(duì)之類的話可以看一下BZOJ2120數(shù)顏色然后就把這些東西拼拼湊湊就出來這個(gè)題了= =

莫隊(duì)這玩意兒復(fù)雜度太玄了。。樹分塊開到n√ $/sqrt n$ 大數(shù)據(jù)就1.1s+，如果換成n23 $n^{2 /over 3}$ 大數(shù)據(jù)就0.5s+。。而且常數(shù)寫不好還死T死T的。。。重點(diǎn)就是把修改部分的常數(shù)搞得好一點(diǎn)就差不多了。

代碼

#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;//對(duì)每個(gè)節(jié)點(diǎn)維護(hù)它自己的棧底 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];//為了提前把修改做一遍所以要另存一下權(quán)值 } 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è)域 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);//兩個(gè)端點(diǎn)要按照dfs序排列，減少不必要的移動(dòng) 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;//棧內(nèi)剩下的元素出棧 sort(q+1,q+qcnt+1,comp); len[0]=-1;//第0個(gè)塊的結(jié)尾設(shè)為-1，這樣在find_mex中才能訪問到第1個(gè)塊的起點(diǎn)0 for (int i=0;i<=n;i=tail+1){ tail=min(i+vblock-1,n); ++vcnt;//對(duì)權(quán)值分塊 len[vcnt]=tail; for (int j=i;j<=tail;j++) vpos[j]=vcnt; } Time(1);//維護(hù)時(shí)間 move(q[1].u,q[1].v); lca=find_lca(q[1].u,q[1].v);//注意節(jié)點(diǎn)的lca要單獨(dú)計(jì)算 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;}

上一篇：forward 和redirect的區(qū)別

下一篇：九度oj 題目1047：素?cái)?shù)判定