【bzoj1058】[ZJOI2007]报表统计

2015.05.28 16:39 Thu | 18次阅读 | 旧日oi | 固定链接 | 源码

题目大意:维护一个序列,支持三种操作:1.在某个初始位置后加入一个数,如果这个位置加入过数,则加到这个数的后面。2.查询相邻两数的差的最小值3.查询所有数差的最小值。
题解:set水过,本机测200+s,注意是s!!!bz上14秒就过了……细节的部分还挺多,比如边界什么的……

我的程序

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<set>
using namespace std;
#define N 500005
#define inf 2147483647
multiset<int> s1,s2;
int n,m,x,y,ans=inf;
char s[20];
int a[N],now[N];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);now[i]=a[i];
        if(s2.count(a[i])) ans=0,s2.insert(a[i]);
        else
        {
            int t1=inf,t2=inf;
            if(s2.size()&&a[i]<(*s2.rbegin())) t1=*s2.lower_bound(a[i]);
            if(s2.size()&&a[i]>*s2.begin()) t2=*(--s2.lower_bound(a[i]));
            ans=min(ans,min(abs(t1-a[i]),abs(a[i]-t2)));
            s2.insert(a[i]);
        }
        if(i>1) s1.insert(abs(a[i]-a[i-1]));
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%s",s);
        if(s[0]=='I')
        {
            scanf("%d%d",&x,&y);
            s1.erase(s1.find(abs(a[x+1]-now[x])));
            s1.insert(abs(y-now[x]));s1.insert(abs(a[x+1]-y));
            if(s2.count(y)) ans=0,s2.insert(y);
            else
            {
                int t1=inf,t2=inf;
                if(y<(*s2.rbegin())) t1=*s2.lower_bound(y);
                if(y>*s2.begin()) t2=*(--s2.lower_bound(y));
                ans=min(ans,min(abs(t1-y),abs(y-t2)));
                s2.insert(y);
            }
            now[x]=y;
        }
        else if(s[4]=='G') printf("%d\n",*s1.begin());
        else printf("%d\n",ans);
    }
}```