题目描述
墨墨购买了一套 \(N\) 支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会向你发布如下指令：
-
\(Q\ L\ R\) 代表询问你从第 \(L\) 支画笔到第 \(R\) 支画笔中共有几种不同颜色的画笔。
-
\(R\ P\ C\) 把第 \(P\) 支画笔替换为颜色 \(C\)。
为了满足墨墨的要求，你知道你需要干什么了吗？
输入格式
第 \(1\) 行两个整数 \(N\)，\(M\)，分别代表初始画笔的数量以及墨墨会做的事情的个数。
第 \(2\) 行 \(N\) 个整数，分别代表初始画笔排中第 \(i\) 支画笔的颜色。
第 \(3\) 行到第 \(2+M\) 行，每行分别代表墨墨会做的一件事情，格式见题干部分。
输出格式
对于每一个 Query 的询问，你需要在对应的行中给出一个数字，代表第 \(L\) 支画笔到第 \(R\) 支画笔中共有几种不同颜色的画笔。
输入输出样例 #1
输入 #1
6 5
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6
输出 #1
4
4
3
4
说明/提示
对于30%的数据，\(n,m \leq 10000\)
对于60%的数据，\(n,m \leq 50000\)
对于所有数据，\(n,m \leq 133333\)
所有的输入数据中出现的所有整数均大于等于 \(1\) 且不超过 \(10^6\)。
本题可能轻微卡常数
来源：bzoj2120
本题数据为洛谷自造数据，使用 CYaRon 耗时5分钟完成数据制作。
题解
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
const int MAXV = 1e6+10;typedef long long ll;
int n,m;
struct Node
{ll l,r,i,t;
}q[N];struct Upd
{int pos,val;
}upd[N];ll cnt[MAXV];
ll cl=1,cr=0,ct=0;
ll kind = 0;
ll a[N];
int blen;
int bi[N];
ll ans[N];int cntq,cntu;bool cmp(Node a,Node b)
{if(bi[a.l]!=bi[b.l])return bi[a.l]<bi[b.l];if(bi[a.r]!=bi[b.r])return bi[a.r]<bi[b.r];return a.t<b.t;
}void build()
{blen = max(1,(int)pow(n,2.0/3));for(int i=1;i<=n;i++){bi[i] = (i-1)/blen +1;}sort(q+1,q+1+cntq,cmp);}void add(int x)
{if(++cnt[x]==1)kind++;
}void sub(int x)
{if(--cnt[x]==0)kind--;
}void moveT(int jobl,int jobr,int tim)
{int pos = upd[tim].pos;int val = upd[tim].val;if(jobl<=pos&&pos<=jobr){sub(a[pos]);add(val);}int tmp = a[pos];a[pos] = val;upd[tim].val = tmp;
}void solve()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=m;i++){char op;int l,r,v,pos;cin>>op;if(op=='Q'){cin>>l>>r;cntq++;q[cntq].l = l;q[cntq].r = r;q[cntq].t = cntu;q[cntq].i = cntq;}else{cin>>pos>>v;cntu++;upd[cntu].pos = pos;upd[cntu].val = v;}}build();for(int i=1;i<=cntq;i++){int l = q[i].l;int r = q[i].r;int id = q[i].i;int tt = q[i].t;while(cl>l){add(a[--cl]);}while(cr<r){add(a[++cr]);}while(cl<l){sub(a[cl++]);}while(cr>r){sub(a[cr--]);}while(ct<tt){moveT(l,r,++ct);}while(ct>tt){moveT(l,r,ct--);}ans[id] = kind; }for(int i=1;i<=cntq;i++){cout<<ans[i]<<'\n';}}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;// cin>>t;while(t--){solve();}return 0;
}