洛谷:ZJOJ 2007レポート統計

クリックすると屠龍宝刀が送られます
テーマはDescription Qのお母さんが出納していることを説明して、いつも統計報告書の仕事をしなければなりません.今日は母の誕生日で、Qさんは母の誕生日のプレゼントの一つとして、仕事を分担してほしいと思っています.よく観察した結果、小Qは、1枚のレポートを統計することは、実際には非負の整数数列を維持し、いくつかのクエリー操作を行うことであることを発見した.最初に、長さNの整数シーケンスがあり、次の3つの操作があります.
INSERT i k:元の列のi番目の要素の後ろに新しい要素kを追加します.元の列のi番目の要素にいくつかの要素が追加されている場合、これらの要素の最後に追加されます(次の例を参照).MIN_GAP:隣接する2つの要素間の差分値(絶対値)の最小値MIN_を問い合わせるSORT_GAP:全要素の中で最も近い2つの要素の差分値(絶対値)を問い合わせる.例えば、最初のシーケンスが5 3 1の場合、INSERT 2 9を実行すると、5 3 9 1の場合、MIN_GAPは2、MIN_SORT_GAPは2です.さらにINSERT 2 6を実行すると、5 3 9 6 1この時点で元のシーケンスの2番目の要素の後ろに9が追加されていることに注意し、この時点で追加された6は9の後ろに追加されるべきである.この時MIN_GAPは2、MIN_SORT_GAPは1です.そこでQさんはプログラムを書いて、プログラムが自動的にこれらの操作を完成させることができますが、彼はいくつかの大きなレポートに対して彼のプログラムが遅く実行されていることを発見しました.あなたは彼のプログラムを改善することができますか?入出力フォーマットInput/output入力フォーマット:最初の行は2つの整数N,Mを含み、それぞれ原数列の長さと操作回数を表す.第2の動作N個の整数は、初期シーケンスである.次のM行は、「INSERT i k」、「MIN_GAP」、「MIN_SORT_GAP」のいずれか(余分なスペースや空行がない)の行ごとに動作する.出力形式:「MIN_GAP」コマンドと「MIN_SORT_GAP」コマンドごとに、1行の答えを出力します.入出力サンプルSample input/output入力サンプル3 5 5 3 1 INSERT 2 9 MIN_SORT_GAP INSERT 2 6 MIN_GAP MIN_SORT_GAP出力サンプル2 2 1
この問題は気持ち悪い...最初のアイデアは、チェーンテーブル+セグメントツリーを永続化して差分値を維持し、setで差分値の最小値を維持することですが、セグメントツリーも永続化することができます.のコードの長さを考えると怖いです.のそこで脳洞はsetのi番目の項目にアクセスしようとしたが、明らかに科学的ではない.そしてまた,i番目の結果に大きなスタックでアクセスしようとしたが,この関数はなかった.最後に黄先輩のやり方を参考にして、小根の山と再集でstlで水を入れるのは本当によかったが、T Tは各位置に対して、最初と最後の要素を知るだけで、1つのsetで差の最小値を維持してグローバルに対してsetを再維持することができて、1つの要素を挿入してその前駆の後継の差を探して山に挿入することができます.

#include
#include
#include
#include
#include
#include
#include
#define inf 1000000000

using namespace std;

int n,m;
int st[500005],ed[500005];
multiset<int> a,b;
map<int,int> mp;
priority_queue<int,vector<int>,greater<int> > q;

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

void insert(int x)
{
    mp[x]++;
    if(mp[x]==1)a.insert(x);
}

void push(int x)
{
    int l=*--b.lower_bound(x),r=*b.lower_bound(x);
    q.push(min(x-l,r-x));
    b.insert(x);
}

int main()
{
    n=read();m=read();
    b.insert(inf);b.insert(-inf);
    for(int i=1;i<=n;i++)
    {
        int x=read();
        ed[i]=st[i]=x;
        push(x);
    }
    for(int i=2;i<=n;i++)insert(abs(st[i]-st[i-1]));
    char ch[12];int p,x,t;
    for(int i=1;i<=m;i++)
    {
        scanf("%s",ch);
        if(ch[0]=='I')
        {
            p=read();x=read();
            if(p!=n)
            {
                t=abs(ed[p]-st[p+1]);
                mp[t]--;
                if(!mp[t])a.erase(t);
            }
            insert(abs(ed[p]-x));
            insert(abs(x-st[p+1]));
            ed[p]=x;push(x);
        }
        else if(ch[4]=='S')printf("%d
",q.top());
        else printf("%d
",*a.begin());
    }
    return 0;
}

この山はTLEですが、どうやらA 5ポイント.