bzoj1058: [ZJOI2007]报表统计-白红宇

bzoj1058: [ZJOI2007]报表统计

阅读量：4308 次

发布时间：2019-06-06

本文共 1320 字，大约阅读时间需要 4 分钟。

哈哈set卡时过了。

set求前驱的方法：*--b.lower_bound(x) （想想写了splay的肉老师就很愉悦啊）

弄两个set，一个记录的是位置的值，一个是差值，MIN_SORT_GAP就很简单啊，插入的时候找前驱后继，然后mmin代表当前最小值就可以了。

对于MIN_GAP要记录当前位置的st，ed，因为插入时是往后叠加的，所以st就是一开始这个位置的值，ed就是最后一个插入在该位置的值，这样一来当插入的时候，就可以方便的找到位置在前面和后面的值。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            using namespace std;int st[510000],ed[510000];multiset
             
              a,b;map
              
               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

你可能感兴趣的文章