BZOJ1058: [ZJOI2007]报表统计(set)
2018-06-17 20:53:35来源:未知 阅读 ()
Submit: 4190 Solved: 1420
[Submit][Status][Discuss]
Description
Input
Output
对于每一个“MIN_GAP”和“MIN_SORT_GAP”命令,输出一行答案即可。
Sample Input
5 3 1
INSERT 2 9
MIN_SORT_GAP
INSERT 2 6
MIN_GAP
MIN_SORT_GAP
Sample Output
2
1
HINT
N , M ≤500000 对于所有的数据,序列内的整数不超过5*10^8。
Source
时隔19260817年后再一次在BZOJ上A题&&1A
没有修改操作,这是本题最大的突破口
这样的话每个位置我们只需要维护原始的值和加入的最后一个值
相邻的差值用multiset维护
同时用一个set维护加入的数
再用一个set维护加入的数的差值
然后就可以搞了
插入的时候有很多细节要处理
#include<cstdio> #include<set> #include<algorithm> #define msit multiset<int>::iterator #define sit set<int>::iterator using namespace std; const int MAXN=1e6+10; multiset<int>sp;//相邻元素的差值 set<int>sv;//相近元素的差值 set<int>s;//维护已经加入的元素的值 struct node { int up,down; }a[MAXN]; int date[MAXN]; char opt[25]; int main() { #ifdef WIN32 freopen("a.in","r",stdin); #endif int N,M; scanf("%d%d",&N,&M); for(int i=1;i<=N;i++) scanf("%d",&a[i].up), date[i]=a[i].down=a[i].up, s.insert(a[i].up); for(int i=1;i<=N-1;i++) sp.insert(abs(a[i].up-a[i+1].up)); sort(date+1,date+N+1); for(int i=1;i<=N-1;i++) sv.insert(abs(date[i]-date[i+1])); while(M--) { scanf("%s",opt); if(opt[4]=='R')//insert { int pos,val; scanf("%d%d",&pos,&val); msit it=sp.find(abs(a[pos].down-a[pos+1].up)); if(it!=sp.end()) sp.erase(it); sp.insert(abs(val-a[pos].down)); sp.insert(abs(val-a[pos+1].up)); a[pos].down=val; sit st=s.lower_bound(val); if(st!=s.end()) sv.insert(abs(val-*st)); if(st!=s.begin()) --st, sv.insert(abs(val-*st)); s.insert(val); } else if(opt[4]=='S')//val min printf("%d\n",*sv.begin()); else if(opt[4]=='G')//neighbor min printf("%d\n",*sp.begin()); } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- BZOJ1093: [ZJOI2007]最大半连通子图(tarjan dp) 2018-09-01
- BZOJ1059: [ZJOI2007]矩阵游戏(二分图匹配) 2018-07-09
- 关于VS 2010 RDLC 报表的详细使用说明 2018-06-18
- Reporting Services 的一些问题 2018-06-18
- 浅谈ASP.NET报表控件 2018-06-18
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash