[ZJOI2007] 报表统计 题解 FHQ-Treap 堆 pb_ds

[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 命令，输出一行答案即可。

样例 #1

样例输入 #1

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

样例输出 #1

2
2
1

提示

样例输入输出 1 解释

一开始的序列为 { 5 , 3 , 1 } \{5,3,1\} {5,3,1}。

执行操作 INSERT 2 9 将得到 { 5 , 3 , 9 , 1 } \{5,3,9,1\} {5,3,9,1}，此时 MIN_GAP 为 $2$，MIN_SORT_GAP 为 $2$。

再执行操作 INSERT 2 6 将得到： { 5 , 3 , 9 , 6 , 1 } \{5,3, 9, 6, 1\} {5,3,9,6,1}。

注意这个时候原序列的第 $2$ 个元素后面已经添加了一个 $9$，此时添加的 $6$ 应加在 $9$ 的后面。这个时候 MIN_GAP 为 $2$，MIN_SORT_GAP 为 $1$。

数据规模与约定

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

注明

$以上来自洛谷。$
什么（）（）平衡树啊。
同机房的大佬 @_Sunmoon 用 set${}^{[1]}$ 过了，牛牛牛。

解题思路

前置知识

• Treap${}^{[2]}$
• FHQ_Treap${}^{[3]}$
• pb_ds${}^{[4]}$

正文

操作 $1$ 和操作 $3$ 为平衡树模版（可以用 pb_ds 实现），即每插入一个数 $x$ 都查询 $x$ 前驱和后继与 $x$ 的差值，并更新当前 $MIN\_SORT\_GAP$ 的值。
现在考虑 $2$。由于插入一个数只对它相邻的数的差值有变化，所以可以用一个堆来维护当前序列所有差值，每插入一个数，消失的差值存在另外一个堆里，如果两个堆的堆顶相同，说明当前的 $MIN\_GAP$ 已经失效，要弹出两堆对顶相同的部分。

AC Code

#include<bits/stdc++.h>
#include<ext/pb_ds/priority_queue.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define int long long
mt19937 rng(233);
int n, m, a[1000005];
__gnu_pbds::priority_queue<int, greater<int>, pairing_heap_tag> Input, Output;
vector<int> g[500005];//维护操作INSERT
unordered_map<int, int> U_Map;//维护每个数出现次数
struct node {
	int l, r, val, key;
} FHQ[1000005];
int Length, Root, X, Y, Z, MIN_GAP = INT_MAX, MIN_SORT_GAP = INT_MAX;
int Answer;
inline int New(int val) {
	FHQ[++Length] = {0, 0, val, rng()};
	return Length;
}
inline void Split(int now, int val, int &X, int &Y) {
	if (!now) X = Y = 0;
	else if (FHQ[now].val <= val) X = now, Split(FHQ[now].r, val, FHQ[now].r, Y);
	else Y = now, Split(FHQ[now].l, val, X, FHQ[now].l);
}
inline int Merge(int X, int Y) {
	if (!X || !Y) return X | Y;
	if (FHQ[X].key > FHQ[Y].key) {
		FHQ[X].r = Merge(FHQ[X].r, Y);
		return X;
	} else {
		FHQ[Y].l = Merge(X, FHQ[Y].l);
		return Y;
	}
}
inline int Get_Pre(int val) {
	Split(Root, val - 1, X, Y);
	int now = X;
	while (FHQ[now].r)now = FHQ[now].r;
	Root = Merge(X, Y);
	return FHQ[now].val;
}
inline int Get_Next(int val) {
	Split(Root, val, X, Y);
	int now = Y;
	while (FHQ[now].l)now = FHQ[now].l;
	Root = Merge(X, Y);
	return FHQ[now].val;
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0), cin >> n >> m;
	for (register int i = 1, x; i <= n; ++i) cin >> x, a[i] = x, ++U_Map[x], Split(Root, x, X, Y), Root = Merge(Merge(X, New(x)), Y), g[i].push_back(x);
	for (register int i = 2; i <= n; ++i) Input.push(abs(a[i] - a[i - 1]));
	MIN_GAP = Input.top(), sort(a + 1, a + n + 1);
	for (register int i = 2; i <= n; ++i) MIN_SORT_GAP = min(MIN_SORT_GAP, abs(a[i] - a[i - 1]));
	g[n + 1].push_back(INT_MAX), Split(Root, INT_MAX, X, Y), Root = Merge(Merge(X, New(INT_MAX)), Y), Split(Root, -INT_MAX, X, Y), Root = Merge(Merge(X, New(-INT_MAX)), Y);
	string opt;
	int i, k, pre;
	while (m--) {
		cin >> opt;
		if (opt == "INSERT") {
			cin >> i >> k, ++U_Map[k];
			if (U_Map[k] > 1) MIN_SORT_GAP = 0;
			pre = g[i][g[i].size() - 1], Output.push(abs(pre - g[i + 1][0])), Input.push(abs(k - pre)), Input.push(abs(k - g[i + 1][0])); //插入元素相邻差值处理
			while (!Output.empty() && Input.top() == Output.top())Input.pop(), Output.pop();
			g[i].push_back(k), MIN_GAP = Input.top();//找MIN_GAP
			if (!MIN_SORT_GAP) continue;//有两个相同元素接下来MIN_SORT_GAP永远为0
			Split(Root, k, X, Y), Root = Merge(Merge(X, New(k)), Y), MIN_SORT_GAP = min(MIN_SORT_GAP, min(abs(Get_Pre(k) - k), abs(Get_Next(k) - k)));
		} else if (opt == "MIN_GAP") cout << MIN_GAP << endl;
		else cout << MIN_SORT_GAP << endl;
	}
	return 0;
}

资料来源注明

[1] OI-WIki；
[2] 博客园：TimelessWelkin；
[3] OI-Wiki；
[4] OI-WIki。