bzoj 4129 Haruna’s Breakfast（树上带修莫队）

本文主要是介绍bzoj 4129 Haruna’s Breakfast（树上带修莫队），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

思路：

树上带修莫队+块状数组，基本上还是很裸的
但是写起来很麻烦，看到好多人硬是压到90多行，真是跪了
总体思路就是，树上询问和修改还是莫队，但是在查询的时候，肯定不能O(n)地去询问，而线段树因为莫队每次移动区间都需要修改，会让总体复杂度多出一个logn，所以在查答案的时候用块状数组维护，这样由块状数组产生的复杂度是$O(n\sqrt{n})$,不会使总体复杂度提高

错误及反思：

因为在修改时间的时候，要判断这个点在不在u,v的路径上且不是lca,一时脑抽地写了
if( (lca( l , po )==po|| lca( r , po )== po)&&( po != lca( l , r ) ))
这个写法很明显的bug，就是当po是lca(l,r)的父亲是就会发生错误。明明判下vis就行的东西，硬是自己脑抽卡了一下午

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 51000;int blocks,block[N][2],n,m,totq=1,totc=1,ans[N],last[N],tot=1;
int blockval[N],from[N],en[N],cnt[N],to[N][20],depth[N],val[N],totb=1;
int st[N],tp=0;
bool vis[N];
vector<int> son[N];struct Q{int l,r,ti,id;
}q[N];struct C{int u,to,pre;
}c[N];bool cmp(Q a,Q b){if(block[a.l][1]!=block[b.l][1])return block[a.l][1]<block[b.l][1];else if(block[a.r][1]!=block[b.r][1])return block[a.r][1]<block[b.r][1];return a.ti<b.ti;
}void dfs(int now,int fa,int dep){int si=tp;to[now][0]=fa;depth[now]=dep;for(int i=0;i<son[now].size();i++){if(son[now][i]!=fa){dfs(son[now][i],now,dep+1);if(tp-1-si>=blocks){while(tp-1!=si)block[st[--tp]][1]=tot;tot++;}}}st[tp++]=now;
}void getlca(){for(int i=1;i<=18;i++)for(int j=1;j<=n;j++)to[j][i]=to[to[j][i-1]][i-1];
}int lca(int a,int b){if(depth[a]>depth[b])swap(a,b);for(int i=18;i>=0;i--)if(depth[to[b][i]]>=depth[a])b=to[b][i];if(a==b) return a;for(int i=18;i>=0;i--){if(to[a][i]!=to[b][i]){a=to[a][i];b=to[b][i];}}return to[a][0];
}void modify(int add,int del,int x){int po=c[x].u;if(po==0) return ;if(vis[po]){cnt[del]--;if(cnt[del]==0)blockval[block[del][0]]--;cnt[add]++;if(cnt[add]==1)blockval[block[add][0]]++;}val[po]=add;
}void change(int u,int v){while(u!=v){if(vis[u]){cnt[val[u]]--;if(cnt[val[u]]==0)blockval[block[val[u]][0]]--;}else{cnt[val[u]]++;if(cnt[val[u]]==1)blockval[block[val[u]][0]]++;}vis[u]=!vis[u];u=to[u][0];}
}int main(){scanf("%d%d",&n,&m);blocks=pow(n,0.6666);block[0][0]=1;for(int i=1;i<=n;i++){scanf("%d",&val[i]);val[i]=min(n,val[i]);last[i]=val[i];block[i][0]=i/blocks+1;totb=max(totb,block[i][0]);}for(int i=0;i<=n;i++){if(!from[block[i][0]])from[block[i][0]]=i;en[block[i][0]]=max(en[block[i][0]],i);}from[1]=0;for(int i=0,ta,tb;i<n-1;i++){scanf("%d%d",&ta,&tb);son[ta].push_back(tb);son[tb].push_back(ta);}for(int i=1,ta;i<=m;i++){scanf("%d",&ta);if(ta){scanf("%d%d",&q[totq].l,&q[totq].r);q[totq].id=totq;q[totq++].ti=totc;}else{scanf("%d%d",&c[totc].u,&c[totc].to);c[totc].to=min(n,c[totc].to);c[totc].pre=last[c[totc].u];last[c[totc].u]=c[totc++].to;}}dfs(1,1,1);while(tp)block[st[--tp]][1]=tot-1;getlca();sort(q+1,q+totq,cmp);for(int i=1,l=1,r=1,t=0;i<totq;i++){for(;t<q[i].ti;t++) modify(c[t].to,c[t].pre,t);for(;t>q[i].ti;t--) modify(c[t-1].pre,c[t-1].to,t-1);if(l!=q[i].l){int lc=lca(l,q[i].l);change(l,lc);change(q[i].l,lc);}if(r!=q[i].r){int lc=lca(r,q[i].r);change(r,lc);change(q[i].r,lc);}int zx=lca(q[i].l,q[i].r);cnt[val[zx]]++;if(cnt[val[zx]]==1)blockval[block[val[zx]][0]]++;for(int j=1;j<=totb;j++){if(blockval[j]<en[j]-from[j]+1){for(int k=from[j];k<=en[j];k++){if(cnt[k]==0){ans[q[i].id]=k;break;}}break;}}cnt[val[zx]]--;if(cnt[val[zx]]==0)blockval[block[val[zx]][0]]--;l=q[i].l; r=q[i].r;}for(int i=1;i<totq;i++) printf("%d\n",ans[i]);
}

这篇关于bzoj 4129 Haruna’s Breakfast（树上带修莫队）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---