题解
练习一下带修改莫队
先按照左端点的块排序，再按照右端点的块排序，然后按照时间排序
每个修改操作存一下修改前这个位置的值就可以逆序操作了
代码
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define pdi pair<db,int>
#define mp make_pair
#define pb push_back
#define enter putchar('\n')
#define space putchar(' ')
#define eps 1e-8
#define mo 974711
#define MAXN 10005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
res = 0;char c = getchar();T f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
int N,M,S;
int c[1000005],res,ans[MAXN],op[MAXN],col[2][MAXN],tot,id[MAXN],a[MAXN],tmp[MAXN];
int p,q,x;
struct qry_node {
int id,l,r,bl,br;
friend bool operator < (const qry_node &a,const qry_node &b) {
if(a.bl != b.bl) return a.bl < b.bl;
if(a.br != b.br) return a.br < b.br;
return a.id < b.id;
}
}qry[MAXN];
void update_pos(int pos,int v) {
if(c[pos] == 0 && c[pos] + v == 1) ++res;
else if(c[pos] == 1 && c[pos] + v == 0) --res;
c[pos] += v;
}
void Change(int t) {
if(t > x) {
for(int i = x + 1 ; i <= t ; ++i) {
if(op[i]) {
if(op[i] <= q && op[i] >= p) {
update_pos(a[op[i]],-1);
update_pos(col[1][i],1);
}
a[op[i]] = col[1][i];
}
}
}
else {
for(int i = x ; i > t ; --i) {
if(op[i]) {
if(op[i] <= q && op[i] >= p) {
update_pos(a[op[i]],-1);
update_pos(col[0][i],1);
}
a[op[i]] = col[0][i];
}
}
}
x = t;
}
void Move(int l,int r) {
while(q < r) {update_pos(a[++q],1);}
while(p > l) {update_pos(a[--p],1);}
while(q > r) {update_pos(a[q--],-1);}
while(p < l) {update_pos(a[p++],-1);}
}
void Solve() {
read(N);read(M);
S = pow(N,2.0 / 3.0);
int h = 0;
for(int i = 1 ; i <= N ; ++i) {read(a[i]);tmp[i] = a[i];}
for(int i = 1 ; i <= N ; i += S) {
int r = min(i + S - 1,N);
++h;
for(int j = i ; j <= r ; ++j) {
id[j] = h;
}
}
char s[5];
int l,r;
for(int i = 1 ; i <= M ; ++i) {
scanf("%s",s + 1);
read(l);read(r);
if(s[1] == 'Q') {
qry[++tot] = (qry_node){i,l,r,id[l],id[r]};
}
else {
op[i] = l;col[1][i] = r;col[0][i] = tmp[l];
tmp[l] = r;
}
}
sort(qry + 1,qry + tot + 1);
x = 0,p = 1,q = 0;
for(int i = 1 ; i <= tot ; ++i) {
Change(qry[i].id);
Move(qry[i].l,qry[i].r);
ans[qry[i].id] = res;
}
for(int i = 1 ; i <= M ; ++i) {
if(!op[i]) {
out(ans[i]);enter;
}
}
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
return 0;
}