BZOJ-1058: [ZJOI2007]报表统计（multis

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1058

弱弱地用STL直接水过了,这道题本来是要BST或是BIT的吧。。。

代码：

a8ec8a13632762d038cecab1a2ec08fa503dc6c8.jpg.png

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>
#include <cmath>
 
using namespace std;
 
#define MAXN 500010
#define inf 1000000000
 
multiset<int>S,s;
int n,m,a[MAXN],b[MAXN],ans=inf;
 
int main() {
        S.clear(),s.clear();
        s.insert(-inf),s.insert(inf);
        scanf("%d%d",&n,&m);
        a[n+1]=inf;
        for (int i=0;i++<n;) {
               scanf("%d",&a[i]);
               b[i]=a[i];
               int x=*s.lower_bound(a[i]),y=*(--s.lower_bound(a[i]));
               ans=min(ans,min(x-a[i],a[i]-y));
               s.insert(a[i]);
        }
        for (int i=0;i++<n;) S.insert(abs(a[i+1]-a[i]));
        while (m--) {
               char ss[20];
               scanf("%s",ss);
               if (ss[0]=='I') {
                       int x,y;
                       scanf("%d%d",&x,&y);
                       S.erase(S.find(abs(a[x+1]-b[x])));
                       S.insert(abs(y-b[x])),S.insert(abs(a[x+1]-y));
                       b[x]=y;
                       int l=*s.lower_bound(y),r=*(--s.lower_bound(y));
                       ans=min(ans,min(l-y,y-r));
                       s.insert(y);
               } else if (ss[4]=='S') printf("%d\n",ans); else printf("%d\n",*S.begin());
        }
        return 0;
}