Loj 3094 删数

Posted on | Edited on | Views:

线段树.

考虑对于给定的数列,如何计算最小修改次数.

若当前数列长度为 $x$ ,则操作一次后会转移到 $x-cnt(x)$ ,其中 $cnt(x)$ 表示数列中有几个 $x$ .

想让数列长度变为 $0​$ ,这相当于每个长度都要被删去一次,而 $x​$ 可以让 $[x-cnt(x)+1,x]​$ 这些长度都被删一次.

于是 $[1,n]$ 内每种数字 $x$ 可以覆盖一段区间 $[x-cnt(x)+1,x]$ ,询问 $[1,n]$ 内有几个位置没被覆盖即为答案.

可以用线段树维护每个位置被覆盖的次数,询问最小值以及最小值出现的次数即可得到答案.

现在考虑如何支持修改,单点修改可以直接删掉原来的线段,加上新的线段.

整体 $+1,-1$ 可以直接对全局维护偏移量标记 $\Delta$ ,询问 $[1,n]$ 时改为询问 $[1-\Delta,n-\Delta]$ 即可.

注意整体 $+1,-1$ 时,可能会导致 $n$ 与 $n+1$ 交换,此时需要修改它们的贡献.

时间复杂度 $O(n\log n)$ .

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
void print(int x)
{
	if (x >= 10)
		print(x / 10);
	putchar('0' + x % 10);
}
void write(int x, char c)
{
	if (x < 0)
		putchar('-'), x = -x;
	print(x);
	putchar(c);
}
const int N = 4.5e5 + 10, inf = 1e9;
int n, m, mx, a[N], cnt[N], delta;
int calc(int x)
{
	return x - delta + m;
}
struct node
{
	int mi, cnt, tag;
} Tree[N << 2];
#define root Tree[x]
#define lson Tree[x << 1]
#define rson Tree[x << 1 | 1]
void BuildTree(int x, int l, int r)
{
	root.mi = root.tag = 0, root.cnt = r - l + 1;
	if (l == r)
		return;
	int mid = (l + r) >> 1;
	BuildTree(x << 1, l, mid);
	BuildTree(x << 1 | 1, mid + 1, r);
}
void pushup(int x)
{
	root.mi = min(lson.mi, rson.mi), root.cnt = 0;
	if (lson.mi == root.mi)
		root.cnt += lson.cnt;
	if (rson.mi == root.mi)
		root.cnt += rson.cnt;
}
void modify(int x, int c)
{
	root.mi += c;
	root.tag += c;
}
void pushdown(int x)
{
	if (root.tag)
	{
		modify(x << 1, root.tag);
		modify(x << 1 | 1, root.tag);
		root.tag = 0;
	}
}
void upd(int x, int l, int r, int L, int R, int c)
{
	if (l > R || L > r)
		return;
	if (L <= l && r <= R)
		return modify(x, c);
	int mid = (l + r) >> 1;
	pushdown(x);
	if (L <= mid)
		upd(x << 1, l, mid, L, R, c);
	if (R > mid)
		upd(x << 1 | 1, mid + 1, r, L, R, c);
	pushup(x);
}
void query(int &mi, int &cnt, int x, int l, int r, int L, int R)
{
	if (root.mi > mi)
		return;
	if (L <= l && r <= R)
	{
		if (root.mi < mi)
			mi = root.mi, cnt = root.cnt;
		else if (root.mi == mi)
			cnt += root.cnt;
		return;
	}
	int mid = (l + r) >> 1;
	pushdown(x);
	if (L <= mid)
		query(mi, cnt, x << 1, l, mid, L, R);
	if (R > mid)
		query(mi, cnt, x << 1 | 1, mid + 1, r, L, R);
}
void Modify(int p, int x)
{
	if (x == 1)
	{
		if (cnt[calc(n)])
			upd(1, 1, mx, calc(n) - cnt[calc(n)] + 1, calc(n), -1);
	}
	else
	{
		if (cnt[calc(n + 1)])
			upd(1, 1, mx, calc(n + 1) - cnt[calc(n + 1)] + 1, calc(n + 1), 1);
	}
	delta += x;
}
void Add(int p, int x)
{
	if (a[p] <= calc(n))
		upd(1, 1, mx, a[p] - cnt[a[p]] + 1, a[p] - cnt[a[p]] + 1, -1);
	cnt[a[p]]--;
	a[p] = x - delta + m;
	cnt[a[p]]++;
	if (a[p] <= calc(n))
		upd(1, 1, mx, a[p] - cnt[a[p]] + 1, a[p] - cnt[a[p]] + 1, 1);
}
int main()
{
	n = read(), m = read();
	mx = n + 2 * m;
	BuildTree(1, 1, mx);
	for (int i = 1; i <= n; ++i)
	{
		a[i] = read() + m;
		upd(1, 1, mx, a[i] - cnt[a[i]], a[i] - cnt[a[i]], 1);
		++cnt[a[i]];
	}
	for (int i = 1; i <= m; ++i)
	{
		int p = read(), x = read();
		if (p == 0)
			Modify(p, x);
		else
			Add(p, x);
        int mi = 1, cnt = 0;
		query(mi, cnt, 1, 1, mx, calc(1), calc(n));
		write(mi ? 0 : cnt, '\n');
	}
	return 0;
}