【题目描述】

墨墨购买了一套N支彩色画笔(其中有些颜色可能相同),摆成一排,你需要回答墨墨的提问。墨墨会像你发布如下指令:

  • 1.Q L R代表询问你从第$L$支画笔到第$R$支画笔中共有几种不同颜色的画笔。

  • 2.R P Col 把第$P$支画笔替换为颜色$Col$。为了满足墨墨的要求,你知道你需要干什么了吗?

【输入格式】

第$1$行两个整数$N,M$,分别代表初始画笔的数量以及墨墨会做的事情的个数。

第$2$行$N$个整数,分别代表初始画笔排中第$i$支画笔的颜色。

第$3$行到第$2+M$行,每行分别代表墨墨会做的一件事情,格式见题干部分。

【输出格式】

对于每一个Query的询问,你需要在对应的行中给出一个数字,代表第$L$支画笔到第$R$支画笔中共有几种不同颜色的画笔。

题解

来补一道带修莫队的模板题

什么情况下用带修莫队?

当询问是询问一段区间,并且修改操作可以$O(1)$进行并更新答案时

带修莫队相当于是在基本莫队上加了个时间维度$t$,表示这次询问之前一共有$t$次修改。

在转移询问区间的时候,$t$也一样从上一个询问的$t$向下一个询问的$t$进行/撤回修改。

带修莫队的块大小就不是取$\sqrt{n}$了,而是取$n^{\frac{2}{3}}$,也就是$\sqrt[3]{n^2}$

我们把每个询问表示成这种形式${l,r,t}$,其中$l,r$是询问区间,$t$表示这次询问之前一共有$t$次修改。

然后按照先比$l$再比$r$最后比$t$的顺序来进行排序(当然是比较所在的块)

然后暴力转移修改 可以证明这样做的时间复杂度约为$O(n^{\frac{5}{3}})$,跑$50000\sim 100000$应该问题不大

对$l,r$的修改就和普通莫队一样,$t$的修改则有些不同:

如果某次要进行/撤销的修改操作对当前区间$[l,r]$有影响,就需要更新答案,否则只需要改动原数组的元素

总之也很容易写就是了

这题具体怎么写就不用多说了吧。。。

吐槽一下 洛谷上面这题太卡常了 2s时限卡了半天勉强过了

代码

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

inline int read() {
int x = 0, f = 1; char ch = getchar();
for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1;
for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0');
return x * f;
}

inline void write(int x) {
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}

int n, m, a[140005], b[140005], sz, tot, tme, nowans, ans[140005], cnt[1000005];
int nowl, nowr, nowt;
char s[5];

struct query{
int l, r, t, id;
friend bool operator < (query x, query y) {
if (x.l / sz == y.l / sz) {
if (x.r / sz == y.r / sz) return x.t < y.t;
else return x.r / sz < y.r / sz;
} else return x.l / sz < y.l / sz;
}
} q[140005];

struct modify{
int p, x, y;
} q2[140005];

inline void upd(int x, int v) {
cnt[x] += v;
if (cnt[x] == 0 && v == -1) nowans--;
if (cnt[x] == 1 && v == 1) nowans++;
}

inline void updtime(int t, int v) {
if (v == 1) {
if (nowl <= q2[t].p && q2[t].p <= nowr) {
upd(q2[t].x, -1); upd(q2[t].y, 1);
}
a[q2[t].p] = q2[t].y;
} else {
if (nowl <= q2[t].p && q2[t].p <= nowr) {
upd(q2[t].y, -1); upd(q2[t].x, 1);
}
a[q2[t].p] = q2[t].x;
}
}

int main() {
n = read(), m = read();
sz = pow(n, 2.0 / 3);
for (int i = 1; i <= n; i++) {
a[i] = b[i] = read();
}
for (int i = 1, x, y; i <= m; i++) {
scanf("%s", s);
x = read(), y = read();
if (s[0] == 'Q') {
q[++tot] = {x, y, tme, tot};
} else {
q2[++tme] = {x, b[x], y};
b[x] = y;
}
}
sort(q + 1, q + tot + 1);
nowl = 1, nowr = nowt = 0;
for (int i = 1; i <= tot; i++) {
while (nowt < q[i].t) updtime(++nowt, 1);
while (nowt > q[i].t) updtime(nowt--, -1);
while (nowl < q[i].l) upd(a[nowl++], -1);
while (nowl > q[i].l) upd(a[--nowl], 1);
while (nowr < q[i].r) upd(a[++nowr], 1);
while (nowr > q[i].r) upd(a[nowr--], -1);
ans[q[i].id] = nowans;
}
for (int i = 1; i <= tot; i++) {
write(ans[i]);
puts("");
}
return 0;
}

评论