BZOJ 1058[ZJOI 2007]レポート統計

Qさんのお母さんは出納で、よく統計報告書の仕事をしなければなりません.今日は母の誕生日で、Qさんは母の誕生日のプレゼントの一つとして、仕事を分担してほしいと思っています.よく観察した結果、小Qは、1枚のレポートを統計することは、実際には非負の整数数列を維持し、いくつかのクエリー操作を行うことであることを発見した.最初はNの長さの整数シーケンスがあり、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さんはプログラムを書いて、プログラムが自動的にこれらの操作を完成させることができますが、彼はいくつかの大きなレポートに対して彼のプログラムが遅く実行されていることを発見しました.あなたは彼のプログラムを改善することができますか?
この問題は面倒くさいように見える.
理屈から言えば、高度なデータ構造の問題です.
でもSTL水で通されました.しかし、時間的に見るに耐えられず、16 s以上かかり、テーマの要求は15 sだったが、過ぎた.
まず、任意の要素間の差の絶対値について説明します.
いずれも1つのsetですべての数を格納し、ある数を挿入するたびに、2分で挿入位置を検索し、隣接する2つの数に影響を与えることができます.答えを更新してください.
もちろん境界問題に注意してください
次に、隣接する要素の差の絶対値です.
setとmapを使いました.
setは各種の差を格納し,mapは各差を格納する.
そして挿入するたびに、元の隣接する数が隣接していないことが変化し、挿入された数には2つの隣接する数があります.
mapとsetを更新すればいいです
もちろん、境界問題も重要です.例えば、最後の数の後ろに挿入されます.

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <map>
#include <set>
#define MAXN 500005
#define INF 1000000007
using namespace std;
int n, m;
set<int>s, ss;
map<int, int>mp;
vector<int>g[MAXN];
int a[MAXN], b[MAXN];
int main()
{
    scanf("%d%d", &n, &m);
    int mg = INF, ms = INF, pos, val;
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
        ss.insert(a[i]);
        b[i] = a[i];
        if(i)
        {
            int k = abs(a[i] - a[i - 1]);
            s.insert(k);
            mp[k]++;
        }
    }
    sort(b, b + n);
    for(int i = 1; i < n; i++)
        ms = min(ms, b[i] - b[i - 1]);
    mg = *s.begin();
    char op[33];
    while(m--)
    {
        scanf("%s", op);
        if(op[4] == 'R')
        {
            scanf("%d%d", &pos, &val);
            pos--;
            g[pos].push_back(val);
            if(ms)
            {set<int>::iterator it = ss.lower_bound(val);
             
            if(it != ss.begin())
            {
                if(it == ss.end())
                {
                    it--;
                    ms = min(ms, abs(val - *it));
                }
                else
                {
                    int x = *it;
                    it--;
                    int y = *it;
                    ms = min(ms, abs(x - val));
                    ms = min(ms, abs(y - val));
                }
            }
            else ms = min(ms, abs(val - *ss.begin()));
            }
            ss.insert(val);
            int x, y = INF;
            if(g[pos].size() == 1) x = a[pos];
            else x = g[pos][g[pos].size() - 2];
            if(pos + 1 < n)
            {
                y = a[pos + 1];
                int k = abs(x - y);
                mp[k]--;
                if(mp[k] == 0) s.erase(k);
                k = abs(x - val);
                s.insert(k);
                mp[k]++;
                k = abs(y - val);
                s.insert(k);
                mp[k]++;
                mg = *s.begin();
            }
            else
            {
                int k = abs(x - val);
                s.insert(k);
                mp[k]++;
                mg = *s.begin();
            }
        }
        else if(op[4] == 'G') printf("%d
", mg);
        else printf("%d
", ms);
    }
    return 0;
}