P1903 [国家集训队] 数颜色 / 维护队列题解-526互联

一、题目描述：

　　给你一个长度为 $n$ 的序列 $a$ , 你需要进行 $m$ 次操作。

　　$类型\ 1\ : 将第\ x\ 个元素的值修改为\ v\ 。$

　　$类型\ 2\ : 求区间\ l\ 到\ r\ 中有多少种数字。$

　　数据范围：$1 \le n,m \le 1333333,所有数字 \le 1\times 10^6$

二、解题思路：

　　带修莫队：(思路当然也不是我想出来的$qwq$)

　　加一维时间轴，感觉有点抽象，但还是可以理解。

　　当块长取 $n^{\frac{2}{3}}$ 时时间复杂度最优，$OI\ WiKi$ 上有详细的解释。

　　时间复杂度 $n^{\frac{5}{3}}$。轻微卡常

三、完整代码：

 1 #include<cmath>
 2 #include<iostream>
 3 #include<algorithm>
 4 #define N 150000
 5 #define K 1000010
 6 using namespace std;
 7 char opt;
 8 int cnt1,cnt2;
 9 int n,m,l=1,r,M,sum;
10 int c[N],ans[N],cnt[K];
11 struct Query{
12     int L,R,T,id;
13     bool operator < (const Query &t)const{
14         if(L/M!=t.L/M)    return L<t.L;
15         if(R/M!=t.R/M)    return R<t.R;
16         return T<t.T;
17     }
18 }a[N];
19 struct Modify{
20     int p,val;
21 }b[N];
22 void upt(int v,int f)
23 {
24     cnt[v]+=f;
25     if(f>0&&cnt[v]==1)    sum++;
26     if(f<0&&cnt[v]==0)    sum--;
27 }
28 void Change(int t)
29 {
30     if(l<=b[t].p&&b[t].p<=r)
31         upt(b[t].val,1),upt(c[b[t].p],-1);
32     swap(b[t].val,c[b[t].p]);
33 }
34 int main()
35 {
36     ios::sync_with_stdio(false);
37     cin.tie(0);cout.tie(0);
38     cin>>n>>m;
39     M=pow(n,2.0/3.0);
40     for(int i=1;i<=n;i++)
41         cin>>c[i];
42     for(int i=1;i<=m;i++)
43     {
44         cin>>opt;
45         if(opt=='Q')
46         {
47             cnt1++;
48             cin>>a[cnt1].L>>a[cnt1].R;
49             a[cnt1].id=cnt1,a[cnt1].T=cnt2;
50         }
51         if(opt=='R')
52             cnt2++,cin>>b[cnt2].p>>b[cnt2].val;
53     }
54     sort(a+1,a+1+cnt1);
55     for(int i=1,t=0;i<=cnt1;i++)
56     {
57         while(t<a[i].T)    Change(++t);
58         while(t>a[i].T)    Change(t--);
59         while(l>a[i].L)    upt(c[--l],1);
60         while(r<a[i].R)    upt(c[++r],1);
61         while(l<a[i].L)    upt(c[l++],-1);
62         while(r>a[i].R)    upt(c[r--],-1);
63         ans[a[i].id]=sum;
64     }
65     for(int i=1;i<=cnt1;i++)
66         cout<<ans[i]<<'\n';
67     return 0;
68 }