首页 > 代码库 > bzoj1058题解
bzoj1058题解
【解题思路】
STL好题。维护两个set,一个存储数列里相邻元素差,另一个存储整个数列。
对于MIN_SORT_GAP操作,维护一个ans表示答案,每个INSERT操作时通过第二个set更新即可。
针对INSERT操作的特性,我们可以在原数列每个元素下挂一个链,对于INSERT i k,即在第i条链末端插入k。可以进一步发现在插入过程中每条链只有两端对数列中相邻元素差有贡献,可以进一步优化空间。
那么对于MIN_GAP操作,每个INSERT操作时,记新插入元素为x,其前驱后继分别为y,z(如果存在的话),在第一个set内弹出|y-z|并插入|x-y|和|x-z|。
这样复杂度O(mlog2(n+m))。
【参考程序】
1 #include <bits/stdc++.h> 2 #define range(i,c,o) for(register int i=(c);i<(o);++i) 3 #define dange(i,c,o) for(register int i=(c);i>(o);--i) 4 using namespace std; 5 6 //#define __debug 7 #ifdef __debug 8 #define Function(type) type 9 #define Procedure void10 #else11 #define Function(type) __attribute__((optimize("-O2"))) inline type12 #define Procedure __attribute__((optimize("-O2"))) inline void13 #endif14 15 static const int INF=0x7f7f7f7f;16 17 //quick_io BEGIN HERE18 Function(int) getint()19 {20 char c=getchar(); for(;!isdigit(c)&&c!=‘-‘;c=getchar());21 short s=1; for(;c==‘-‘;c=getchar()) s*=-1; int r=0;22 for(;isdigit(c);c=getchar()) r=(r<<3)+(r<<1)+c-‘0‘;23 return s*r;24 }25 //quick_io END HERE26 27 multiset<int> rec1,rec2;28 int top[500005],bot[500005];29 static int ans=INF,n=getint(),m=getint();30 #define PUSH(x) rec1.insert(x)31 #define POP(x) rec1.erase(rec1.find(x))32 Procedure INSERT1(const int&k,const int&x)33 {34 PUSH(abs(x-bot[k ]));35 if(k<n)36 {37 PUSH(abs(x-top[k+1]));38 POP(abs(bot[k]-top[k+1]));39 }40 }41 Procedure INSERT2(const int&x)42 {43 multiset<int>::iterator it=rec2.insert(x);44 if(it!=rec2.begin()) ans=min(ans,x-*--it),++it;45 if(++it!=rec2.end()) ans=min(ans,*it - x) ;46 }47 48 int main()49 {50 rec1.clear(),rec2.clear();51 range(i,1,n+1)52 {53 top[i]=bot[i]=getint();54 if(i>1) PUSH(abs(bot[i-1]-top[i]));55 INSERT2(top[i]);56 }57 while(m--)58 {59 char c; while(isspace(c=getchar()));60 if(c==‘I‘)61 {62 int k=getint(),x=getint();63 INSERT1(k,x),INSERT2(x),bot[k]=x;64 continue;65 }66 while(getchar()!=‘_‘); c=getchar();67 while(!isspace(getchar()));68 printf("%d\n",c==‘G‘?*rec1.begin():ans);69 }70 return 0;71 }
bzoj1058题解
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。