洛谷P1110 [ZJOI2007] 报表统计题解

题目链接：P1110 [ZJOI2007] 报表统计

题意：

小 Q 的妈妈是一个出纳，经常需要做一些统计报表的工作。今天是妈妈的生日，小 Q 希望可以帮妈妈分担一些工作，作为她的生日礼物之一。

经过仔细观察，小 Q 发现统计一张报表实际上是维护一个非负整数数列，并且进行一些查询操作。

在最开始的时候，有一个长度为 $n$ 的整数序列 $a$ ，并且有以下三种操作：

INSERT i k：在原数列的第 $i$ 个元素后面添加一个新元素 $k$；如果原数列的第 $i$ 个元素已经添加了若干元素，则添加在这些元素的最后（见样例说明）。

MIN_GAP：查询相邻两个元素的之间差值（绝对值）的最小值。

MIN_SORT_GAP：查询所有元素中最接近的两个元素的差值（绝对值）。

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

输入格式：

第一行包含两个整数，分别表示原数列的长度 $n$ 以及操作的次数 $m$。

第二行为 $n$ 个整数，为初始序列，第 $i$ 个整数表示 $a_i$。

接下来的 $m$ 行，每行一个操作，即INSERT i k，MIN_GAP，MIN_SORT_GAP 中的一种（无多余空格或者空行）。

输出格式：

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

数据范围：

对于全部的测试点，保证 $2 \le n, m \le 5\times10^5$，$1 \leq i \leq n$，$0 \leq a_i, k \leq 5 \times 10^8$。

题目要求我们维护 $n$ 个序列，每个序列初始只有一个元素

看上去需要一些很高级的数据结构，实际上并没有这么复杂。

考察一个新的数的加入对询问的影响。如果我们想知道两个元素之间的最小差值，

那么我们需要知道和这个数最接近的两个数（前驱和后继）。然而这题不仅仅要问最小的差值。

这要求我们维护两个元素可重的有序数据结构，分别表示出现过的数值和差值，这可以用 multiset 做到。

不妨记这两个 multiset 为 $U$ 和 $\Delta$ ，那么对于每个修改，我们向 $U$ 中插入 $x$ ，

并将 $x$ 的前驱和后继与其差值的最小值去更新最小差值 $\mathrm{Ans}$ 。

同时因为 $x$ 的加入，插入位置原本相邻的两个数的差值将不再产生贡献，而 $x$ 将与相邻的数产生贡献。

这个实际上只需要用数组维护一下每个序列的开始和末尾是什么元素，然后在 $\Delta$ 中进行一些插入和删除即可。

时间复杂度 $\mathcal{O}(n \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(5e5 + 15))

multiset<int> delta, full;
int n, m, ans = INF, st[N], ed[N]; char s[15];
void insert(int x)
{
    auto it = full.lower_bound(x);
    int nw = *it - x; --it;
    down(nw, x - *it); down(ans, nw); full.insert(x);
}
void update(int pos, int x)
{
    delta.insert(abs(x - ed[pos]));
    if(pos != n) {
        delta.erase(delta.find(abs(st[pos + 1] - ed[pos])));
        delta.insert(abs(st[pos + 1] - x));
    }
    ed[pos] = x;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i = 1; i <= n; i++) { cin >> st[i], ed[i] = st[i]; }
    full.insert(INF); full.insert(-INF);
    for(int i = 1; i < n; i++) delta.insert(abs(st[i + 1] - ed[i]));
    for(int i = 1; i <= n; i++) insert(st[i]);
    for(int i = 1, pos, x; i <= m; i++)
    {
        cin >> (s + 1);
        if(s[1] == 'I')
        {
            cin >> pos >> x; insert(x); update(pos, x);
        }else if(s[5] == 'S') cout << ans << '\n';
        else cout << *delta.begin() << '\n';
    }
    return 0;
}