2019.01.17 bzoj2333: [SCOI2011]棘手的操作(启发式合并)
2024-10-14 09:49:29
传送门
启发式合并菜题。
题意:支持与连通块有关的几种操作。
要求支持连边,单点修改,连通块修改,全局修改和单点查值,连通块查最大值和全局最大值。
我们对每个连通块和答案用可删堆维护最大值,然后用启发式合并来解决连边的问题。
关键在于连通块修改,这个可以给每个连通块维护一个标记,然后在合并的时候每个数记得修改值就行了。
代码
#include<bits/stdc++.h>
#define ri register int
using namespace std;
inline int read(){
int ans=0,w=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans*w;
}
const int N=3e5+5;
struct IN_OUT_priority_queue{
priority_queue<int>a,b;
inline void push(const int&x){a.push(x);}
inline void del(const int&x){b.push(x);}
inline int top(){while(b.size()&&a.top()==b.top())a.pop(),b.pop();return a.top();}
inline int size(){return a.size()-b.size();}
}ans,S[N];
int n,fa[N],det[N],val[N],all=0;
vector<int>id[N];
inline int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
inline void solve1(){
int x=find(read()),y=find(read());
if(x==y)return;
if(id[x].size()<id[y].size())swap(x,y);
fa[y]=x,ans.del(S[x].top()+det[x]),ans.del(S[y].top()+det[y]);
for(ri i=0;i<id[y].size();++i)id[x].push_back(id[y][i]),val[id[y][i]]+=det[y]-det[x],S[x].push(val[id[y][i]]);
ans.push(S[x].top()+det[x]);
}
inline void solve2(){
int x=read(),fx=find(x),y=read();
ans.del(S[fx].top()+det[fx]);
S[fx].del(val[x]),S[fx].push(val[x]+=y);
ans.push(S[fx].top()+det[fx]);
}
inline void solve3(){int x=find(read()),v=read();ans.del(S[x].top()+det[x]),det[x]+=v,ans.push(S[x].top()+det[x]);}
inline void solve4(){all+=read();}
inline void solve5(){int x=read();cout<<val[x]+det[find(x)]+all<<'\n';}
inline void solve6(){int x=find(read());cout<<S[x].top()+det[x]+all<<'\n';}
inline void solve7(){cout<<ans.top()+all<<'\n';}
int main(){
n=read();
for(ri i=1;i<=n;++i)id[i].push_back(i),fa[i]=i,S[i].push(val[i]=read()),ans.push(val[i]);
for(ri tt=read(),a,b,op;tt;--tt){
string s;
cin>>s;
if(s=="U")solve1();
if(s=="A1")solve2();
if(s=="A2")solve3();
if(s=="A3")solve4();
if(s=="F1")solve5();
if(s=="F2")solve6();
if(s=="F3")solve7();
}
return 0;
}
最新文章
- 2_MVC+EF+Autofac(dbfirst)轻型项目框架_用户权限验证
- Git tag 给当前分支打标签
- python 深入模块和包
- Android自定义控件之轮播图控件
- 将P2P虚拟货币(比特币、莱特币....)的算力用于公共的分布式计算的猜想
- Android百度地图的简单实现
- windows下oracle数据库定时备份与压缩批处理脚本(win7/win2008亲测通过)
- Elasticsearch重要配置
- TortoiseGit- 创建本地新分支,提交推送到远程,本地新分支合并到工作分支,提交到远程工作分支等。
- 201621123062《Java程序设计》第一周学习总结
- LeetCode算法题-Merge Two Binary Trees(Java实现)
- Azure VMSS (3) 修改VM Template并创建VMSS
- Java内存区域划分、内存分配原理(转)
- CentOS6.8下安装Redis
- NGUI的数据绑定
- bzoj 1171 并查集优化顺序枚举 | 线段树套单调队列
- hdu 4090
- bzoj3473: 字符串 &;&; bzoj3277串
- UNIX环境高级编程 第1章 UNIX基础知识
- libcurl使用心得-包括下载文件不存在处理相关(转)
热门文章
- linux之基本命令讲解
- 《纪念碑谷》(Monument Valley) 系列游戏的空间结构是如何设计的?
- [LeetCode_105]Construct Binary Tree from Preorder and Inorder Traversal
- Mac 动态库加载不上
- f5 2017.09.03故障
- c#: 打开文件夹并选中文件
- String.format的用法
- 用js写已知abc+cba = 1333,其中a、b、c均为一位数,编程求出满足条件的a、b、c所有组合。
- springmvc中的拦截器interceptor用法
- java中钩子方法的概念