BZOJ 3460 Jc的宿舍
2024-10-14 00:43:39
题目链接:http://www.lydsy.com:808/JudgeOnline/problem.php?id=3460
题意:一棵树。每个节点住一个人,这个人打水的时间为Ti。每次查询一个路径。这个路径上的人都去一个水管前打水。总的最小等待时间。
思路:在树的DFS序中分块。
const int N=200005; struct node { int x,y,lca,flag,id; int t; }; vector<node> b; vector<int> g[N]; vector<pair<int,int> > Q[N]; int n,m,key,d[N]; int S[N],id; int mp[N],pos[N][2]; int get(int x) { if(S[x]!=x) S[x]=get(S[x]); return S[x]; } int visit[N]; void dfs(int u,int pre) { pos[u][0]=++id; mp[id]=u; int i; for(i=0;i<SZ(g[u]);i++) { int v=g[u][i]; if(v==pre) continue; dfs(v,u); S[v]=u; } pos[u][1]=++id; mp[id]=u; visit[u]=1; for(i=0;i<SZ(Q[u]);i++) { int v=Q[u][i].first; int id=Q[u][i].second; if(visit[v]) b[id].lca=get(v); } } i64 ans[N][2]; int M; int MM; int cmp(node a,node b) { if(a.x/MM!=b.x/MM) return a.x<b.x; if((a.x/MM)&1) return a.y>b.y; return a.y<b.y; } int dp[N]; i64 A[N],B[N]; i64 suma(int x) { i64 ans=0; while(x<N) ans+=A[x],x+=x&-x; return ans; } i64 sumb(int x) { i64 ans=0; while(x) ans+=B[x],x-=x&-x; return ans; } i64 Ans; int qp[N]; void add(int x) { int j; for(j=d[mp[x]];j;j-=j&-j) A[j]+=qp[mp[x]]; if(qp[mp[x]]==-1) Ans-=sumb(d[mp[x]]); for(j=d[mp[x]];j<=n;j+=j&-j) B[j]+=(i64)dp[d[mp[x]]]*qp[mp[x]]; Ans+=suma(d[mp[x]]+1)*dp[d[mp[x]]]*qp[mp[x]]; if(qp[mp[x]]==1) Ans+=sumb(d[mp[x]]); qp[mp[x]]*=-1; } void deal() { MM=sqrt(2*n); sort(b.begin(),b.end(),cmp); int L=1,R=0; int i; for(i=0;i<N;i++) qp[i]=1; for(i=0;i<SZ(b);i++) { int ll=b[i].x; int rr=b[i].y; int id=b[i].id; int t=b[i].t; while(R<rr) add(++R); while(R>rr) add(R--); while(L<ll) add(L++); while(L>ll) add(--L); if(b[i].flag) add(pos[b[i].lca][0]); ans[id][t]=Ans; if(b[i].flag) add(pos[b[i].lca][0]); } } int main() { n=getInt(); m=getInt(); key=getInt(); int i; for(i=1;i<=n;i++) d[i]=getInt(),dp[i]=d[i]; sort(dp+1,dp+n+1); M=unique(dp+1,dp+n+1)-(dp+1); for(i=1;i<=n;i++) d[i]=lower_bound(dp+1,dp+M+1,d[i])-dp; int root; for(i=1;i<=n;i++) { int x=getInt(); if(!x) root=i; else g[x].pb(i),g[i].pb(x); } int cnt=0; for(i=1;i<=m;i++) { char op[5]; scanf("%s",op); if(op[0]=='C') root=getInt(); else { int x=getInt(); node a; a.x=x%n+1; a.y=root; a.id=i; a.t=0; b.pb(a); Q[a.x].pb(MP(a.y,cnt)),Q[a.y].pb(MP(a.x,cnt)); cnt++; a.x=(x+key)%n+1; a.y=root; a.id=i; a.t=1; b.pb(a); Q[a.x].pb(MP(a.y,cnt)),Q[a.y].pb(MP(a.x,cnt)); cnt++; } } for(i=1;i<=n;i++) S[i]=i; dfs(1,0); for(i=0;i<SZ(b);i++) { if(b[i].y==b[i].lca) swap(b[i].x,b[i].y); if(b[i].x==b[i].lca) { b[i].flag=0; b[i].x=pos[b[i].x][0]; b[i].y=pos[b[i].y][0]; continue; } if(pos[b[i].x][1]>pos[b[i].y][0]) swap(b[i].x,b[i].y); b[i].x=pos[b[i].x][1]; b[i].y=pos[b[i].y][0]; b[i].flag=1; } clr(ans,-1); deal(); int last=0; for(i=1;i<=m;i++) if(ans[i][0]!=-1||ans[i][1]!=-1) { printf("%lld\n",ans[i][last&1]); last=ans[i][last&1]; } }
最新文章
- HttpClient_002_中文乱码、HttpClient中文乱码透析、总结
- fedora环境安装webkit支持作爬虫下载解析JS
- javascript splice
- 设置VS2010中自带的ActiveX控件测试容器TstCon
- SharePoint咨询师之路:备份和恢复系列二 - 备份服务器场
- 对jquery的 attr()和prop()理解
- C++中const修饰基本数据类型、指针、引用、对象
- 【Uva11212】 Editing a Book(IDA*)
- SICP 阅读笔记(二)
- 基于stm32f103zet6的FAT16文件系统学习1(初识FAT16)
- HDU 5805 - NanoApe Loves Sequence (BestCoder Round #86)
- js的搜索遍历精讲
- NOIP模拟:能源(二分答案)
- Java实现二叉树的创建和遍历操作(有更新)
- python 数据可视化 -- 真实数据的噪声平滑处理
- golang esl api
- Android Dialog.dismiss()与Activity.finish()顺序
- [eetcode 10]Regular Expression Matching
- [开发笔记]-ASP.NET项目在IIS上使用虚拟目录
- Software Scalability with MapReduce