M_sea

洛谷1110 [ZJOI2007]报表统计
LuoguBZOJ分析用两个$\texttt{multiset}$来维护所有元素与所有相邻元素的差值。然后用$st...
扫描右侧二维码阅读全文
26
2019/01

洛谷1110 [ZJOI2007]报表统计

Luogu

BZOJ

分析

用两个$\texttt{multiset}$来维护所有元素与所有相邻元素的差值。

然后用$st[i]$表示第$i$段的开头的元素,$ed[i]$表示第$i$段结尾的元素。

修改时,元素直接插入,顺便更新一下MIN_SORT_GAP;差值的$\texttt{multiset}$直接删除再插入就行了。

细节和具体实现见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=500000+10;
const int INF=0x3f3f3f3f;

int n,m,ans;
multiset<int> S,dlt;
multiset<int>::iterator it;
int st[N],ed[N];

inline void update1(int& ans,int x) {
    it=S.lower_bound(x); int A=*it-x;
    --it; int B=x-*it;
    S.insert(x),ans=min(ans,min(A,B));
}

inline void update2(int x,int k) {
    if (x!=n) {
        dlt.erase(dlt.find(abs(st[x+1]-ed[x])));
        dlt.insert(abs(st[x+1]-k));
    }
    dlt.insert(abs(k-ed[x])),ed[x]=k;
}

int main() {
    n=read(),m=read(),ans=INF;
    for (re int i=1;i<=n;++i) st[i]=ed[i]=read();
    S.insert(-INF),S.insert(INF);
    for (re int i=1;i<n;++i) dlt.insert(abs(st[i+1]-ed[i]));
    for (re int i=1;i<=n;++i) update1(ans,st[i]);
    for (re int i=1;i<=m;++i) {
        char s[20]; scanf("%s",s);
        if (s[0]=='I') {
            int x=read(),k=read();
            update1(ans,k); update2(x,k);
        }
        else if (s[4]=='G') printf("%d\n",*dlt.begin());
        else printf("%d\n",ans);
    }
    return 0;
}
最后修改:2019 年 01 月 26 日 04 : 43 PM

6 条评论

  1. Ivystorm

    STL dalao %%%

  2. smy

    我写setT了qwq

    1. M_sea
      @smy

      要$\texttt{multiset}$啊qwq

      还有您需要$\texttt{wys}$优化

      1. smy
        @M_sea

        muitiset快?

        1. M_sea
          @smy

          您常数太大了吧qwq

          1. smy
            @M_sea

            qwq

发表评论