[ZJOI2007]报表统计

前言

题面传送门: Luogu-P1110.

本文中使用的是set && multiset, 并非平衡树.

洛咕题解第一篇和我的思路撞到一起了.

但好歹是我自己想出来的比较玄学的做法 写写题解记录记录2333

题目描述

给你一个长度为 $n$ 的非负整数序列.

总共有以下三种操作:

  1. INSERT i k: 在原数列的第 $i$ 个元素后添加一个新元素 $k$.
  2. MIN_GAP: 查询相邻两元素之间差值(绝对值)的最小值.
  3. MIN_SORT_GAP: 查询所有元素中数值大小最接近的两个元素的差值(绝对值).

共 $m$ 次操作, $n,m \le 500000$.

题目分析

初步思路

首先要注意到INSERT操作是在原数列的元素后插入.

举个例子:

原数列为: $\lbrace 5,3,1 \rbrace$

现在INSERT 2 9 对应结果: $\lbrace 5,3,9,1 \rbrace$

INSERT 2 4 对应结果: $\lbrace 5,3,9,4,1 \rbrace$

相当于原数列的每个数挂了条链表.

3操作倒是很好搞, 跟这道题差不多, 搞一个set, 每次插入数的时候用其与前驱和后继的差值更新答案即可.

重点在1,2操作.

暴力优先

考虑暴力一点的做法:

设原数列每个元素为 $a_{1 \cdots n}$.

先把所有的 $|a_i-a_{i+1}|$ 丢到multiset里面.

INSERT操作的时候, 对于给出的 $i$, 把 $|lsta_i-a_{i+1}|$ 删掉

(其中 $lsta_i$ 表示 $a_i$ 所挂的链的最后一个数)

加入 $|k-lsta_i|,|k-a_{i+1}|$

每次查询输出*multiset.begin().

在这个思想的基础上, 原本麻烦的INSERT操作也免了

因为在 $a_i$ 挂上的一条链中, 我们只需要用到 $lsta_i$

直接用另一个数组维护一下就可以了.

复杂度

这是不是太暴力了?

思考一下时间复杂度.

$m$ 次操作, 每次操作均摊下来是 $O(logn)$.

总时间复杂度即 $O(mlogn)$, 可以通过本题.

实现细节

  • 注意set的边界问题. 实在不想处理可以一开始就插入INF && -INF.
  • 注意维护 $lsta_i$ 的数组的初值赋为 $a_i$.
  • 当 $i=n$, $a_{i+1}$ 是不存在的.
  • (可能只有我一个人犯的错误) 用fread用惯之后在这个题写了个字符串读入, 然后写挂了, 交上去全TLE… 搞得我怀疑了半天人生 最后只好用getchar读优 然而不开O2最后一个点好像死活过不去… 可能我的常数不够优秀吧
  • 若使用multiset.erase(val), 则multiset会删除键值等于val的所有元素.所以需要multiset.erase(multiset.find(val))来删除单个的迭代器.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/**********************************************************
* Author : EndSaH
* Email : hjxhb1@gmail.com
* Created Time : 2018-11-26 19:10
* FileName : wib.cpp
* Website : endsah.cf
* *******************************************************/

#include <cstdio>
#include <set>

template<typename _Tp>
inline bool chkmin(_Tp& x, const _Tp& y)
{ return x > y ? (x = y, true) : false; }

template<typename _Tp>
inline _Tp abs(const _Tp& x)
{ return x < 0 ? -x : x; }

const int maxN = 5e5 + 2;
const int INF = 0x7FFFFFFF;

int n, m, sort_ans = INF, ans = INF, temp, last;
int a[2][maxN];
std::set<int> SET1;
std::multiset<int> SET2;
std::set<int>::iterator it;
char opt[15];

inline void Check(int val)
{
if(!SET1.empty())
{
it = SET1.lower_bound(val);
if(it != SET1.end())
{
chkmin(sort_ans, *it - val);
if(it != SET1.begin())
chkmin(sort_ans, val - *--it);
}
else
chkmin(sort_ans, val - *--it);
}
SET1.insert(val);
}

inline void Insert(int pos, int val)
{
SET2.insert(abs(val - a[1][pos]));
if(pos != n)
{
SET2.insert(abs(val - a[0][pos + 1]));
SET2.erase(SET2.find(abs(a[1][pos] - a[0][pos + 1])));
}
a[1][pos] = val;
}

int main()
{
scanf("%d%d", &n, &m);
for(register int i = 1; i <= n; ++i)
{
scanf("%d", &temp);
Check(temp);
if(i != 1)
SET2.insert(abs(temp - last));
a[0][i] = a[1][i] = last = temp;
}
while(m--)
{
scanf("%s", opt);
switch(opt[4])
{
case 'R' :
scanf("%d%d", &temp, &last);
Insert(temp, last);
Check(last);
break;
case 'S' :
printf("%d\n", sort_ans);
break;
case 'G' :
printf("%d\n", *SET2.begin());
break;
}
}

return 0;
}