Description

小 Q 的妈妈是一个出纳, 经常需要做一些统计报表的工作. 今天是妈妈的生日, 小 Q 希望可以 帮妈妈分担一些工作, 作为她的生日礼物之一. 经过仔细观察, 小 Q 发现统计一张报表实际上是维护一个可能为负数的整数数列, 并且进行一些查询操作. 在最开始的时候, 有一个长度为 \(n\) 的整数序列, 并且有以下三种操作:

  1. INSERT i k 在原数列的第 \(i\) 个元素后面添加一个新元素 \(k\); 如果原数列的 第 \(i\) 个元素已经添加了若干元素, 则添加在这些元素的最后 (见下面的例子)
  2. MIN_GAP 查询相邻两个元素的之间差值 (绝对值) 的最小值
  3. MIN_SORT_GAP 查询所有元素中最接近的两个元素的差值 (绝对值)

例如一开始的序列为 5 3 1:

  1. 执行操作 INSERT 2 9 将得到:5 3 9 1. 此时 MIN_GAP 为 \(2\),MIN_SORT_GAP 为 \(2\).
  2. 再执行操作 INSERT 2 6 将得到:5 3 9 6 1. 注意这个时候原序列的第 \(2\) 个元素后面已经添加了一个 \(9\), 此时添加的 \(6\) 应加在 \(9\) 的后面. 这个时候 MIN_GAP 为 \(2\),MIN_SORT_GAP 为 \(1\).

于是小 Q 写了一个程序, 使得程序可以自动完成这些操作, 但是他发现对于一些大的报表他 的程序运行得很慢, 你能帮助他改进程序么?

Input

第一行包含两个整数 \(n, m\), 分别表示原数列的长度以及操作的次数. 第二行为 \(n\) 个整数, 为初始序列. 接下来的 \(m\) 行每行一个操作, 即 INSERT i k,MIN_GAP,MIN_SORT_GAP 中的一种 (无多余空格或者空行).

Output

对于每一个 MIN_GAP 和 MIN_SORT_GAP 命令, 输出一行答案即可.

Sample Input

3 5
5 3 1
INSERT 2 9
MIN_SORT_GAP
INSERT 2 6
MIN_GAP
MIN_SORT_GAP

Sample Output

2
2
1

Data Range

对于所有的数据,\(n, m \leq 500000\), 且序列内的整数不超过 \(5 \times 10^8\).

Explanation

一看就可以用 STL map, set 来水的一道题 (但是如果你看错那就是你的问题了)

一开始还认为是在整个序列里进行插入, 然后果断写了个 Splay. 发现调了好久都是 WA 之后突然惊呆地看了一下题面, 发现是原来的序列中的位置...... 结果为了防止 Splay 浪费 掉又加了好多特判来维护 Splay...... 终于把答案搞正确以后交上去居然 TLE (TAT)

所以就只能膜了~ 最后写了个 STL 直接水, 没有 Splay 什么事. 事实上可能如果用 Splay 来代替 STL 红黑树会更快一些, 但是我没测.

附带一发 TLE (也有可能 WA) 的 Splay 代码:


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <map>
#include <set>
#include <algorithm>

#define min_3(__x,__y,__z) min(min(__x,__y),__z)
using namespace std;
typedef long long lli;
const int maxn = 1001000;
const int infinit = 1000000000;

class SplayTree
{
public:
    int n, root, ncnt;
    int ch[maxn][2], par[maxn];
    int val[maxn], size[maxn];
    #define lc(__x) ch[__x][0]
    #define rc(__x) ch[__x][1]
    int make_node(int v)
    {
        int p = ++ncnt;
        val[p] = v;
        lc(p) = rc(p) = par[p] = 0;
        size[p] = 1;
        return p;
    }
    void rotate(int p)
    {
        int q = par[p], g = par[q];
        int x = p == rc(q), y = q == rc(g);
        ch[q][x] = ch[p][!x]; if (ch[q][x]) par[ch[q][x]] = q;
        ch[p][!x] = q; par[q] = p;
        if (g) ch[g][y] = p; par[p] = g;
        // Updating data
        size[q] = size[lc(q)] + size[rc(q)] + 1;
        size[p] = size[lc(p)] + size[rc(p)] + 1;
        return ;
    }
    void splay(int p, int t)
    {
        for (int q = 0; (q = par[p]) && q != t; rotate(p))
            if (par[q] && par[q] != t)
                rotate((p == lc(q)) == (q == lc(par[q])) ? q : p);
        if (t == 0) root = p;
        return ;
    }
    int suc(int p)
    {
        if (!rc(p)) { while (p && p == rc(par[p])) p = par[p]; p = par[p]; }
        else { p = rc(p); while (p && lc(p)) p = lc(p); }
        return p;
    }
    int pre(int p)
    {
        if (!lc(p)) { while (p && p == lc(par[p])) p = par[p]; p = par[p]; }
        else { p = lc(p); while (p && rc(p)) p = rc(p); }
        return p;
    }
    int find(int sz)
    {
        sz += 1; // Hot-fix.
        int p = root;
        while (p != 0) {
            if (sz <= size[lc(p)]) {
                p = lc(p);
                continue;
            } sz -= size[lc(p)];
            if (sz <= 1) return p;
            sz -= 1; p = rc(p);
        }
        splay(p, 0);
        return p;
    }
    void insert(int lp, int rp, int v)
    {
        splay(lp, 0);
        splay(rp, root);
        // Lazy insertion
        int q = make_node(v);
        par[q] = rp;
        lc(rp) = q;
        size[lp]++, size[rp]++;
        splay(q, 0);
        return ;
    }
    void insert(int pos, int v)
    {
        int lp = find(pos),
            rp = suc(lp);
        insert(lp, rp, v);
        return ;
    }
    void init(void)
    {
        root = make_node(-infinit);
        rc(root) = make_node(infinit);
        par[rc(root)] = root;
        size[root] = 2;
        return ;
    }
} st;

char str[100];
int n, m;
int arr[maxn];
map<int, int> mg; // MIN_GAP
set<int> msgi; // MIN_SORT_GAP index
int msg; // MIN_SORT_GAP value, only decreases (PROVEN)

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    st.init();
    msgi.insert(-infinit);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &arr[i]);
        st.insert(i - 1, arr[i]);
        // Update MIN_GAP
        if (i > 1) mg[abs(arr[i] - arr[i - 1])]++;
        // Update MIN_SORT_GAP
        msgi.insert(arr[i]);
    }
    st.insert(n, infinit);
    // st.insert(n, 0); // Don't know why.
    // mg[abs(arr[1] - 0)]++;
    // mg[abs(0 - arr[n])]++;
    // Initializing msgi.
    sort(arr + 1, arr + 1 + n);
    msg = infinit;
    for (int i = 2; i <= n; i++)
        msg = min(msg, arr[i] - arr[i - 1]);
    // Preparing queries
    for (int i = 1; i <= m; i++) {
        scanf("%s", str + 1);
        if (str[1] == 'I') { // INSERT
            int pos, val;
            scanf("%d%d", &pos, &val);
            // Removing from MIN_GAP
            // YOU GOT IT WRONG!
            // int lp = st.val[st.find(pos)],
            //     rp = st.val[st.find(pos + 1)];
            int rp_p = pos+1 + 2, rp = st.val[rp_p],
                lp_p = st.pre(rp_p), lp = st.val[lp_p];
            mg[abs(rp - lp)]--;
            if (!mg[abs(rp - lp)])
                mg.erase(mg.find(abs(rp - lp)));
            // Adding into MIN_GAP
            mg[abs(rp - val)]++;
            mg[abs(val - lp)]++;
            // Modifying MIN_SORT_GAP
            lp = *--msgi.upper_bound(val),
            rp = *msgi.upper_bound(val);
            // printf("%d %d %d\n", val, lp, rp);
            msg = min_3(msg, abs(val - lp), abs(rp - val));
            msgi.insert(val);
            // Inserting into splay tree
            // st.insert(pos, val);
            st.insert(lp_p, rp_p, val);
        } else if (str[1] == 'M' && str[5] == 'G') { // MIN_GAP
            printf("%d\n", mg.begin()->first);
        } else if (str[1] == 'M' && str[5] == 'S') { // MIN_SORT_GAP
            printf("%d\n", msg);
        }
    }
    return 0;
}

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <set>
#include <map>
#include <queue>

using namespace std;
typedef long long lli;
const int maxn = 500100;
const int infinit = 600000000;

int n, m;
int begin[maxn], end[maxn]; // Array begin & ends
char str[64];

map<int, int> mg_idx; // MIN_GAP indexer
multiset<int> msg_srt; // MIN_GAP sorter, MIN_SORT_GAP sorter
priority_queue<int, vector<int>, greater<int> > msg_res; // MIN_SORT_GAP data retriever

void insert_min_sort_gap(int v)
{
    int l = *--msg_srt.lower_bound(v),
        r = *msg_srt.lower_bound(v);
    msg_res.push(min(abs(r - v), abs(v - l)));
    msg_srt.insert(v);
    return ;
}

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    msg_srt.insert(-infinit);
    msg_srt.insert(infinit);
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        // Updating array data
        begin[i] = end[i] = x;
        // Updating MIN_SORT_GAP data
        insert_min_sort_gap(x);
        // Updating MIN_GAP data
        if (i >= 2)
            mg_idx[abs(begin[i] - begin[i - 1])]++;
    }
    for (int i = 1; i <= m; i++) {
        scanf("%s", str + 1);
        if (str[1] == 'I') { // INSERT
            int pos, val;
            scanf("%d%d", &pos, &val);
            if (pos != n) {
                int dist = abs(begin[pos + 1] - end[pos]);
                mg_idx[dist]--;
                if (!mg_idx[dist])
                    mg_idx.erase(mg_idx.find(dist));
            }
            mg_idx[abs(val - end[pos])]++;
            mg_idx[abs(begin[pos + 1] - val)]++;
            end[pos] = val;
            insert_min_sort_gap(val);
        } else if (str[1] == 'M' && str[5] == 'G') { // MIN_GAP
            printf("%d\n", mg_idx.begin()->first);
        } else if (str[1] == 'M' && str[5] == 'S') { // MIN_SORT_GAP
            printf("%d\n", msg_res.top());
        }
    }
    return 0;
}