bzoj4129 Haruna’s Breakfast 莫队
这个思想不难理解了前面几个就能懂
但是代码比较复杂,大概会和之前几次碰到难题的时候一样,一步步思考下去,然后把难点分成好几个板块讲下qwq
首先读入这颗树,预处理下lca,然后就分块,这个时候就会碰到第一个难点了
第一个点是,怎么分块
对不起无法理解无法证明为什么是酱婶的,但是实现并不难qwq
首先明确的是块的大小是n0.45不要问我为什么不会:D
就是如果这个块内的任意俩点距离都小于块的大小,就可以放在一块中
然后这个可以通过dfs+栈实现
代码大概就酱婶的↓
qwqinline void dfs(int x) { int gg=cnt; for(register int i=head[x];i;i=edge[i].next) { if(fa[x][0]==edge[i].to)continue; fa[edge[i].to][0]=x;deep[edge[i].to]=deep[x]+1; rp(j,1,19)fa[edge[i].to][j]=fa[fa[edge[i].to][j-1]][j-1]; dfs(edge[i].to); if(cnt-gg>=len){++tot;while(cnt!=gg)bl[stck[cnt--]]=tot;} } stck[++cnt]=x; }
分块搞完之后就可以读入修改和询问了,这里就没有太难感觉,用俩结构体就是了
然后排序,就和带修莫队是一样的,不讲
然后就开始解决问题
这个板子题有个很美滋滋的事儿,就是它修改起来特别简单,一路照着链走就是了,然后^修改就是了
但是又会遇到第二个,不算难点,大概是坑点qwq
第二个点是,lca很委屈
显然lca那个点会求两次
所以要另外求一次
那就另外搞个lca的函数求一下就欧克辽嘛
代码也比较简单嘛qwq
就是个板子嘛QAQinline int lca(int x,int y) { if(x==y)return x;if(deep[x]<deep[y])swap(x,y); my(i,19,0)if(deep[fa[x][i]]>=deep[y])x=fa[x][i]; my(i,19,0)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i]; return x==y?x:fa[x][0]; }
umm布星我发现我理解还是不够透彻,关于那个直接移动那儿我依然没有理解得十分清楚
所以先咕着了QAQ可能要过一阵子再写QAQ
over
然后原来的代码先放着但是显然是有错误的?先放着趴之后方便改,实在不想全部重码遍了QAQ
#include<bits/stdc++.h> using namespace std; #define rp(i,x,y) for(register int i=x;i<=y;++i) #define my(i,x,y) for(register int i=x;i>=y;--i) const int N=2500000+100,sqtN=50000+10; int now,tot,n,m,c[N],cc[N],len,bl[N],ans[N],cnt; //umm还是分别写下分工?nm读入不说,c读入和之后莫队修改颜色操作在此处,cc用来搞oldnew的,len是树上块的长度 //bl是树上分块的belong,ans存答案.now是当前时间点,tot开始是树上栈的个数后来是change个数,cnt开始是存边的后来是存栈内元素个数的 int bll[N],cjkcjk,lenlen,num[N],sum[sqtN],sz[sqtN]; //这一行是存查答案那个操作的,bll表示答案的属于,cjkcjk是答案的块个数,lenlen是答案的块的长度,num是每个数个数,sum表示这个块有多少个存在的,sz表示这个块有几个数 int head[N],deep[N],fa[N][20],stck[sqtN]; //这一行是专门搞那个边的,比较中规中矩没什么可说的 bool vis[N]; //vis存的是这个点在链上嘛 struct qest{int l,r,id,tim;}q[N]; struct chan{int p,nc,oc;}cg[N]; struct ed{int to,next;}edge[N]; inline int read() { char ch=getchar();int x=0;bool y=1; while(ch!='-' && (ch<'0' || ch>'9'))ch=getchar(); if(ch=='-')ch=getchar(),y=0; while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=getchar(); return y?x:-x; } inline void add(int x,int y){edge[++cnt].to=x;edge[cnt].next=head[y];head[y]=cnt;} inline bool cmp(qest gold,qest genius){return bl[gold.l]==bl[genius.l]?bl[gold.r]==bl[genius.r]?gold.tim<genius.tim:bl[gold.r]<bl[genius.r]:bl[gold.l]<bl[genius.l];} inline void ad(int x){sum[bll[x]]+=(++num[x])==1;} inline void dl(int x){sum[bll[x]]-=(--num[x])==0;} inline int as(){rp(i,1,cjkcjk)if(sum[i]!=sz[i])rp(j,lenlen*(i-1),lenlen*(i-1)+sz[i]-1)if(!num[j])return j;} inline void update(int x){if(vis[x])dl(c[x]);else ad(c[x]);vis[x]^=1;} inline void change(int x,int y){if(vis[x])dl(c[x]),ad(y);c[x]=y;} inline void dfs(int x) { int gg=cnt; for(register int i=head[x];i;i=edge[i].next) { if(fa[x][0]==edge[i].to)continue; fa[edge[i].to][0]=x;deep[edge[i].to]=deep[x]+1; rp(j,1,19)fa[edge[i].to][j]=fa[fa[edge[i].to][j-1]][j-1]; dfs(edge[i].to); if(cnt-gg>=len){++tot;while(cnt!=gg)bl[stck[cnt--]]=tot;} } stck[++cnt]=x; } inline int lca(int x,int y) { if(x==y)return x;if(deep[x]<deep[y])swap(x,y); my(i,19,0)if(deep[fa[x][i]]>=deep[y])x=fa[x][i]; my(i,19,0)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i]; return x==y?x:fa[x][0]; } inline void move(int x,int y) { if(x==y)return;if(deep[x]<deep[y])swap(x,y); while(deep[x]!=deep[y])update(x),x=fa[x][0]; while(x!=y)update(x),update(y),x=fa[x][0],y=fa[y][0]; } inline void pre() { n=read();m=read();len=pow(n,0.45); lenlen=sqrt(n);cjkcjk=n/lenlen+1;rp(i,0,n)bll[i]=(i-1)/lenlen+1,++sz[(i-1)/lenlen+1]; rp(i,1,n)c[i]=read(),cc[i]=c[i]; rp(i,1,n-1){int t1=read(),t2=read();add(t1,t2);add(t2,t1);} cnt=0;rp(i,0,19)fa[1][i]=1;dfs(1);++tot;while(cnt)bl[stck[cnt--]]=tot;cnt=0;tot=0; rp(i,1,m) { bool op=read(); if(op)q[i-tot].l=read(),q[i-tot].r=read(),q[i-tot].id=i-tot,q[i-tot].tim=tot; else cg[++tot].p=read(),cg[tot].nc=read(),cg[tot].oc=cc[cg[tot].p],cc[cg[tot].p]=cg[tot].nc; } sort(q+1,q+1+m-tot,cmp); } int main() { pre(); move(q[1].l,q[1].r);update(lca(q[1].l,q[1].r));ans[q[1].id]=as(); // printf("id=%d l=%d r=%d lca=%d\n",q[1].id,q[1].l,q[1].r,lca(q[1].l,q[1].r));rp(i,1,n)if(vis[i])printf("%d-%d ",i,c[i]);printf("\n\n"); update(lca(q[1].l,q[1].r)); // printf("\n------------\n"); rp(i,2,m-tot) { while(now<q[i].tim)change(cg[now+1].p,cg[now+1].nc),++now; while(now>q[i].tim)change(cg[now].p,cg[now].oc),--now; move(q[i].l,q[i-1].l);move(q[i].r,q[i-1].r); update(lca(q[i].l,q[i].r)); ans[q[i].id]=as(); // printf("id=%d l=%d r=%d lca=%d ans=%d\n",q[i].id,q[i].l,q[i].r,lca(q[i].l,q[i].r),ans[q[i].id]); // rp(j,1,n)if(vis[j])printf("%d-%d ",j,c[j]);printf("\n\n"); update(lca(q[i].l,q[i].r)); // printf("\n------------\n"); } rp(i,1,m-tot)printf("%d\n",ans[i]); return 0; }
...难受死了不想做这题了,先这样趴至少样例过了?
很烦躁了QAQ