待修莫队。（用奇偶优化真的能快300ms！）
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<stack>
#include<vector>
#include<queue>
#include<set>
#include<bitset>
#include<map>
//#include<regex>
#include<cstdio>
#include <iomanip>
#pragma GCC optimize(2)
#define up(i,a,b) for(int i=a;i<b;i++)
#define dw(i,a,b) for(int i=a;i>b;i--)
#define upd(i,a,b) for(int i=a;i<=b;i++)
#define dwd(i,a,b) for(int i=a;i>=b;i--)
//#define local
typedef long long ll;
typedef unsigned long long ull;
const double esp = 1e-6;
const double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int inf = 1e9;
using namespace std;
ll read()
{
char ch = getchar(); ll x = 0, f = 1;
while (ch<‘0‘ || ch>‘9‘) { if (ch == ‘-‘)f = -1; ch = getchar(); }
while (ch >= ‘0‘ && ch <= ‘9‘) { x = x * 10 + ch - ‘0‘; ch = getchar(); }
return x * f;
}
typedef pair<int, int> pir;
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define lrt root<<1
#define rrt root<<1|1
const int N = 5e4 + 10;
const int node_N = 1e6 + 10;
int n, m, block;
int a[N];
int mp[node_N], belong[node_N];
struct node {
int l, r, time, id;
bool operator<(const node temp)const {
if (belong[l] == belong[temp.l])
{
if (belong[r] == belong[temp.r])
return time < temp.time;
else return r < temp.r;
}
else if (belong[l] & 1)return r < temp.r;
else return r > temp.r;
}
}qr[N];
struct node2 {
int pos, x, time;
}mk[N];
int qr_cnt, mk_cnt;
int L = 1, R, T, ans;
void add(int x)
{
mp[x]++;
if (mp[x] == 1)ans++;
}
void del(int x)
{
if (mp[x] == 1)ans--;
mp[x]--;
}
void update(int t)
{
int pos = mk[t].pos; int x = mk[t].x;
if (pos >= L && pos <= R)
{
del(a[pos]);
add(x);
}
swap(a[pos], mk[t].x);
}
int main()
{
n = read(), m = read();
block = pow(n, 0.666666);
upd(i, 1, n)
{
a[i] = read();
belong[i] = (i - 1) / block + 1;
}
char op[2]; int l, r;
upd(i, 1, m)
{
scanf("%s", op); l = read(), r = read();
if (op[0] == ‘Q‘)
{
qr[++qr_cnt].id = qr_cnt; qr[qr_cnt].l = l + 1; qr[qr_cnt].r = r; qr[qr_cnt].time = mk_cnt;
}
else
{
mk[++mk_cnt].pos = l + 1; mk[mk_cnt].x = r;
}
}
sort(qr + 1, qr + qr_cnt + 1);
int qr_ans[N];
upd(i, 1, qr_cnt)
{
while (T > qr[i].time)update(T--);
while (T < qr[i].time)update(++T);
while (L < qr[i].l)del(a[L++]);
while (L > qr[i].l)add(a[--L]);
while (R < qr[i].r)add(a[++R]);
while (R > qr[i].r)del(a[R--]);
qr_ans[qr[i].id] = ans;
}
upd(i, 1, qr_cnt)
printf("%d\n", qr_ans[i]);
return 0;
}
L - Dynamic len(set(a[L:R])) UVA - 12345
原文：https://www.cnblogs.com/LORDXX/p/12591663.html