哈哈set卡時過了。

set求前驅的方法：*--b.lower_bound(x) （想想寫了splay的肉老師就很愉悅啊）

弄兩個set，一個記錄的是位置的值，一個是差值，MIN_SORT_GAP就很簡單啊，插入的時候找前驅后繼，然后mmin代表當前最小值就可以了。

對于MIN_GAP要記錄當前位置的st，ed，因為插入時是往后疊加的，所以st就是一開始這個位置的值，ed就是最后一個插入在該位置的值，這樣一來當插入的時候，就可以方便的找到位置在前面和后面的值。

#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<set> #include<map> using namespace std;int st[510000],ed[510000]; multiset<int>a,b; map<int,int>mp; char ss[20]; int main() {int n,m,p,x,k,mmin=999999999;scanf("%d%d",&n,&m);b.insert((-5)*1e8-1);b.insert(5*1e8+1);for(int i=1;i<=n;i++){scanf("%d",&x);st[i]=ed[i]=x;int l=*--b.lower_bound(x),r=*b.lower_bound(x);mmin=min(mmin,min(x-l,r-x));b.insert(x);}for(int i=2;i<=n;i++){k=abs(st[i]-st[i-1]);mp[k]++;if(mp[k]==1)a.insert(k);}for(int i=1;i<=m;i++){scanf("%s",ss+1);if(ss[1]=='I'){scanf("%d%d",&p,&x);if(p!=n){k=abs(ed[p]-st[p+1]);mp[k]--;if(mp[k]==0)a.erase(k);}k=abs(ed[p]-x);mp[k]++;if(mp[k]==1)a.insert(k);k=abs(x-st[p+1]);mp[k]++;if(mp[k]==1)a.insert(k);ed[p]=x;int l=*--b.lower_bound(x),r=*b.lower_bound(x);mmin=min(mmin,min(x-l,r-x));b.insert(x);}else if(ss[5]=='S')printf("%d\n",mmin);else printf("%d\n",*a.begin());}return 0; }

?

轉載于:https://www.cnblogs.com/AKCqhzdy/p/8527765.html

總結

以上是生活随笔為你收集整理的bzoj1058: [ZJOI2007]报表统计的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。