这个题不是待修莫队$O(n^{\frac{5}{3}})$次方都能过的吗/fad
by bovine__kebi @ 2020-05-22 14:41:46
常数大吸个氧气就好了
by bovine__kebi @ 2020-05-22 14:42:17
开头加上[这个](https://www.luogu.com.cn/paste/3kzuillr)
by bovine__kebi @ 2020-05-22 14:43:21
@[LiM_817](/user/56724)
by bovine__kebi @ 2020-05-22 14:43:33
@[LiM_817](/user/56724) 我这边线段树套 splay 都没事啊……您换成 splay 试试？
by _5011_ @ 2020-05-22 14:56:22
@[Zephyr_](/user/91127) 话说您有没有发现我给的氧气头是您某篇题解里边的（
by bovine__kebi @ 2020-05-22 15:11:59
@[LiM_817](/user/56724) 待修莫队可能好一些（？）
莫队常数没那么珂怕，另外只要 $O(N^{\frac{5}{3}})$ 吸氧过
我代码吸氧的，鬼畜卡点
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, m;
int add[N], cnt[N];
int block, finalans, counts, courts;
int answers[N];
int belong[N];
struct Queries {
int left, right, _time;
int id;
} qwq[N];
struct Crayon {
int colour;
int Position;
int lastPosition;
} cr[N];
inline void input (int &ret) {
ret = 0; char ch = getchar ();
while (!isdigit (ch)) ch = getchar ();
while (isdigit (ch)) {
ret = (ret << 1) + (ret << 3) + (ch ^ '0');
ch = getchar ();
}
return;
}
inline bool sortfunction (Queries kkksc03, Queries chen_zhe) {
int l = kkksc03.left; int r = kkksc03.right; int t = kkksc03._time;
int left = chen_zhe.left; int right = chen_zhe.right; int _time = chen_zhe._time;
return ((belong[l] ^ belong[left]) ? belong[l] < belong[left] : ((belong[r] ^ belong[right]) ? belong[r] < belong[right] : belong[t] < belong[_time]));
}
int main () {
input (n); input (m);
int block = pow (n, 1.0 * 2 / 3);
int blockednumber = ceil ((double) (n / block));
for (register int i = 1; i <= blockednumber; ++ i) {
for (register int j = (i - 1) * block + 1; j <= i * block; ++ j) belong[j] = i;
}
for (register int i = 1; i <= n; ++ i) input (add[i]);
for (register int i = 1; i <= m; ++ i) {
char buf[10]; scanf ("%s", buf);
if (buf[0] == 'Q') {
input (qwq[++ counts].left);
input (qwq[counts].right);
qwq[counts]._time = courts;
qwq[counts].id = counts;
} else {
input (cr[++ courts].Position);
input (cr[courts].colour);
}
}
sort (qwq + 1, qwq + 1 + counts, sortfunction);
int l = 1;
int r = 0;
int tim = 0;
for (register int i = 1; i <= counts; ++ i) {
int left = qwq[i].left;
int right = qwq[i].right;
int _time = qwq[i]._time;
while (l < left) finalans -= !-- cnt[add[l ++]];
while (l > left) finalans += !cnt[add[-- l]] ++;
while (r < right) finalans += !cnt[add[++ r]] ++;
while (r > right) finalans -= !-- cnt[add[r --]];
while (tim < _time) {
++ tim;
if (left <= cr[tim].Position && cr[tim].Position <= right) finalans -= !-- cnt[add[cr[tim].Position]] - !cnt[cr[tim].colour] ++;
swap (add[cr[tim].Position], cr[tim].colour);
}
while (tim > _time) {
if (left <= cr[tim].Position && cr[tim].Position <= right) finalans -= !-- cnt[add[cr[tim].Position]] - !cnt[cr[tim].colour] ++;
swap (add[cr[tim].Position], cr[tim].colour);
-- tim;
}
answers[qwq[i].id] = finalans;
}
for (register int i = 1; i <= counts; ++ i) printf ("%d\n", answers[i]);
return 0;
}
```
by MistZero @ 2020-05-22 16:42:06