「Luogu P1903」「国家集训队」数颜色/维护队列

Description

给定 $n$ 个数,$m$ 次操作,操作分两种:

Q L R:询问区间 $[L,R]$ 中有多少个不同的数;

R P Col:把第 $P$ 个数替换为 $Col$ 。

$(1 \leq n,m \leq 5 \times 10^4$,数的大小均大于等于 $1$ 且不超过 $10^6)$

Source

[Luogu]P1903

Solution

看到这道题的询问,就很容易想到 莫队 。可是还有修改操作,普通的莫队不支持,怎么办呢?带修莫队 应运而生。

带修莫队,字面意思即是带修改的莫队。它与普通莫队不同的是,多了一个 时间戳,用来记录到当前这个询问时已经进行了多少次修改操作。

我们把询问和修改分别存下来。对于每一个询问,我们不仅要做到左右端点与当前询问一致,还要使修改次数与当前询问相同。如果我们修改得过多,那么应该删去多余的修改,修改过少则反之。

普通莫队写法:

1
2
3
4
for (; l > ql; add(col[--l]));
for (; r < qr; add(col[++r]));
for (; l < ql; del(col[l++]));
for (; r > qr; del(col[r--]));

带修莫队新增的两句话:

1
2
for (; t < qt; upd(++t, i));
for (; t > qt; upd(t--, i));

其中 $qt$ 表示这个询问已修改的次数,$t$ 表示当前已修改的次数,$i$ 表示排序后是第 $i$ 个询问。

upd 操作:

1
2
3
4
5
6
7
8
9
inline void upd(int x, int i) {//在第 i 个询问进行第 x 次修改
if (u[x].pos >= q[i].l && u[x].pos <= q[i].r) {//修改的位置在询问区间内才会产生影响
del(col[u[x].pos]);//删掉第 pos 位上的数
add(u[x].k);//增加修改完的数
}
swap(col[u[x].pos], u[x].k);
//如果我们这一次修改把 x 变成了 y,下次如果要改回来就不是把 x 变成 y 了,
//而是应当把 y 变成 x,所以我们修改完后我们要把 x 和 y 交换
}

至于排序,和普通莫队大致相同。

普通排序:

1
2
3
if (x.l / blockSize != y.l / blockSize) return x.l < y.l;
else if (x.r / blockSize != y.r / blockSize) return x.r < y.r;
return x.t < y.t;

若左端点不在同一块,则按左端点排序;若左端点在同一块,右端点不在同一块,则按右端点排序;若都在同一块,则按修改次数排序。

奇偶性排序:

1
2
3
4
if (x.l / blockSize != y.l / blockSize) return x.l < y.l;
else if (x.r / blockSize != y.r / blockSize)
return ((x.l / blockSize) & 1) ? x.r < y.r : x.r > y.r;
return x.t < y.t;

若左端点在同一块,右端点不在同一块,则根据左端点所在块编号的奇偶性对右端点排序。其它与普通排序相同。

在带修莫队中,块的大小($blockSize$)设 $n^{\frac{2}{3}}$ 比较快。此时的时间复杂度约为 $O(n^{\frac{5}{3}})$,证明有些麻烦,这里暂不给出。

Code

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
x = 0;
char c = getchar();
bool f = 0;
for (; !isdigit(c); c = getchar()) f ^= c == '-';
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
x = f ? -x : x;
}

inline void readChar(char &c) {
for (c = getchar(); c != 'Q' && c != 'R'; c = getchar());
}

template <class T>
inline void write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
T y = 1;
int len = 1;
for (; y <= x / 10; y *= 10) ++len;
for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 5e4, MAXM = 1e6;
int n, m, cntQ, cntR, res, blockSize, ans[MAXN + 5], col[MAXN + 5], cnt[MAXM + 5];
struct Query {
int l, r, t, id;
//l = 左端点,r = 右端点,t = 已修改次数(时间戳),id = 询问编号
inline friend bool operator<(Query x, Query y) {
if (x.l / blockSize != y.l / blockSize) return x.l < y.l;
else if (x.r / blockSize != y.r / blockSize)
return ((x.l / blockSize) & 1) ? x.r < y.r : x.r > y.r;
return x.t < y.t;
}
} q[MAXN + 5];
struct Update {
int pos, k;//把第 pos 个数变为 k
} u[MAXN + 5];

inline void add(int x) {
res += !cnt[x];
++cnt[x];
}

inline void del(int x) {
--cnt[x];
res -= !cnt[x];
}

inline void upd(int x, int i) {//在第 i 个询问进行第 x 次修改
if (u[x].pos >= q[i].l && u[x].pos <= q[i].r) {//修改的位置在询问区间内才会产生影响
del(col[u[x].pos]);//删掉第 pos 位上的数
add(u[x].k);//增加修改完的数
}
swap(col[u[x].pos], u[x].k);
//如果我们这一次修改把 x 变成了 y,下次如果要改回来就不是把 x 变成 y 了,
//而是应当把 y 变成 x,所以我们修改完后我们要把 x 和 y 交换
}

inline void mo() {
sort(q + 1, q + cntQ + 1);
int l = 1, r = 0, t = 0;//初始左端点为 1,右端点为 0,进行了 0 次修改
for (int i = 1; i <= cntQ; ++i) {
int ql = q[i].l, qr = q[i].r, qt = q[i].t;
for (; l > ql; add(col[--l]));
for (; r < qr; add(col[++r]));
for (; l < ql; del(col[l++]));
for (; r > qr; del(col[r--]));
for (; t < qt; upd(++t, i));
for (; t > qt; upd(t--, i));
ans[q[i].id] = res;
}
}

int main() {
read(n), read(m);
blockSize = pow(n, 2.0 / 3);
for (int i = 1; i <= n; ++i) read(col[i]);//初始颜色
for (int i = 1; i <= m; ++i) {
char opt;
readChar(opt);
if (opt == 'Q') {//记录共 cntQ 个修改
read(q[++cntQ].l), read(q[cntQ].r);
q[cntQ].t = cntR, q[cntQ].id = cntQ;
} else read(u[++cntR].pos), read(u[cntR].k);//记录共 cntR 个修改
}
mo();
for (int i = 1; i <= cntQ; ++i) {
write(ans[i]);
putchar('\n');
}
return 0;
}

本文标题:「Luogu P1903」「国家集训队」数颜色/维护队列

文章作者:Heartlessly

发布时间:2019年05月07日 - 07:25:23

最后更新:2019年05月07日 - 09:06:09

原始链接:https://heartlessly.github.io/problems/luogu-p1903/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%