「Bzoj 1058」「ZJOI2007」报表统计 (Set)

发表于 | 分类于 | | + s

Bzoj 1058
题意：有一个长度为$N$的整数序列，并且有以下三种操作：
INSERT i k：在原数列的第$i$个元素后面添加一个新元素$k$；如果原数列的第ii个元素已经添加了若干元素，则添加在这些元素的最后（见下面的例子）
MIN_GAP：查询相邻两个元素的之间差值（绝对值）的最小值
MIN_SORT_GAP：查询所有元素中最接近的两个元素的差值（绝对值）

本题如果原数列的第$i$个元素已经添加了若干元素，则添加在这些元素的最后非常关键，因为这样我们就可以每个位置维护一个数组，然后对每个位置处理即可。
对于MIN_SORT_GAP，就是bzoj1588 & 1208，直接开个 set 维护
对于MIN_GAP，我们每个位置维护$\min(a_i-a_{i-1})$, $a[1,g]$是每个位置维护的数组
然后再将后面的一个位置的第一个数的值和这个位置维护的数组的最后一个值的最小值更新
然后将这些位置的值都插进一个multiset里面维护最小值即可。

知识点：
这种操作读文字的字符串大小数好，开够数组

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 500000 + 5, INF = 2000000000;

    int n, q, a[MAXN], now[MAXN], qc[MAXN];
    vector<int > pos[MAXN];
    int MIN_SORT_GAP;

    set<int > s;
    multiset<int > mind;

    int abss(int x) {return x > 0 ? x : -x;}
    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 clean() {
        MIN_SORT_GAP = INF;
    }
    int solve() {

        clean();
        scanf("%d%d", &n, &q);
        s.insert(-INF), s.insert(INF);
        for (int i = 1; i <= n; ++i) {

            a[i] = read(), pos[i].push_back(a[i]);

            set<int >::iterator it = s.lower_bound(a[i]);
            if (*it != INF) MIN_SORT_GAP = min(MIN_SORT_GAP, abss(a[i] - *it));
            --it;
            if (*it != -INF) MIN_SORT_GAP = min(MIN_SORT_GAP, abss(a[i] - *it));
            s.insert(a[i]);

            qc[i] = INF;

        }
        for (int i = 1; i < n; ++i) mind.insert(now[i] = abss(a[i + 1] - a[i]));
        mind.insert(INF), qc[n] = now[n] = INF;

        char ch[20];
        while (q--) {
            scanf("%s", ch);
            if (ch[0] == 'I') {

                int i, k; i = read(), k = read();

                set<int >::iterator it = s.lower_bound(k);
                if (*it != INF) MIN_SORT_GAP = min(MIN_SORT_GAP, abss(k - *it));
                --it;
                if (*it != -INF) MIN_SORT_GAP = min(MIN_SORT_GAP, abss(k - *it));
                s.insert(k);

                mind.erase(mind.find(now[i]));
                qc[i] = min(qc[i], abss(k - pos[i].back()));
                now[i] = min(qc[i], abss(a[i + 1] - k));
                mind.insert(now[i]);
                pos[i].push_back(k);

            } else if (ch[4] == 'G') {
                printf("%d\n", *mind.begin());
            } else if (ch[4] == 'S') {
                printf("%d\n", MIN_SORT_GAP);
            }
        }

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
/*
2 1000
10 800
*/
------ 本文结束 ------