bzoj 3052: [wc2013]糖果公园(带修改的树上莫队)
程序员文章站
2022-05-03 12:39:50
time limit:200 secmemory limit:512 mb
submit:892solved:425
description
input
output
 ...
time limit:200 secmemory limit:512 mb
submit:892solved:425
description
input
output
sample input
sample input
sample output
84131
27
84
hint
source
题解:bzoj 2120 和 bzoj 3757 的结合版。
注意在排序的时候第一关键字为左端点所在的块,第二关键字为右端点所在的块,第三关键字为离当前询问最近的一次修改的时间(修改是在询问之前的)
#include #include #include #include #include #define n 100003 #define ll long long using namespace std; int n,m,k,block,top; int next[n*2],v[n*2],mi[20]; int point[n],deep[n],st[n],num[n],fa[n][20]; int c[n],tot,sz,cnt,num1,num2; int belong[n],dfsn[n],vis[n],last[n]; ll ans[n],v[n],w[n],ans1; struct data{ int x,y,id,time; }q[n]; struct data1{ int pre,c,pos; }p[n]; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int cmp(data a,data b) { if (belong[a.x]==belong[b.x]&&belong[a.y]==belong[b.y]) return a.time=block) { ++cnt; for (int j=1;j<=size;j++) belong[st[top--]]=cnt; size=0; } } st[++top]=x; return size+1; } int lca(int x,int y) { if (deep[x]>i&1) x=fa[x][i]; if (x==y) return x; for (int i=17;i>=0;i--) if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; return fa[x][0]; } void reserve(int x) { if(!vis[x]) { vis[x]=1; num[c[x]]++; ans1+=v[c[x]]*w[num[c[x]]]; } else { vis[x]=0; ans1-=v[c[x]]*w[num[c[x]]]; num[c[x]]--; } } void solve (int x,int y) { while (x!=y) { if(deep[x]>deep[y]) { reserve(x); x=fa[x][0]; } else{ reserve(y); y=fa[y][0]; } } } void change(int x,int k) { if (vis[x]) { reserve(x); c[x]=k; reserve(x); } else c[x]=k; } int main() { scanf("%d%d%d",&n,&m,&k); for (int i=1;i<=m;i++) v[i]=read(); for (int i=1;i<=n;i++) w[i]=read(); for (int i=1;idfsn[y]) swap(q[num2].x,q[num2].y); } } sort(q+1,q+num2+1,cmp); for (int i=1;i<=q[1].time;i++) change(p[i].pos,p[i].c); solve(q[1].x,q[1].y); int t=lca(q[1].x,q[1].y); reserve(t); ans[q[1].id]=ans1; reserve(t); for (int i=2;i<=num2;i++) { for(int j=q[i-1].time+1;j<=q[i].time;j++) change(p[j].pos,p[j].c); for(int j=q[i-1].time;j>q[i].time;j--) change(p[j].pos,p[j].pre); solve(q[i-1].x,q[i].x); solve(q[i-1].y,q[i].y); int t=lca(q[i].x,q[i].y); reserve(t); ans[q[i].id]=ans1; reserve(t); } for (int i=1;i<=num2;i++) printf("%lld\n",ans[i]); }
上一篇: 意气用事,并不完美的关羽,为什么会受到后世的尊崇?
下一篇: asp 静态页面的另一种思路