P1903 [国家集训队]数颜色 / 维护队列（带修莫队）

题目描述：

墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会向你发布如下指令：

1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。

2、 R P Col 把第P支画笔替换为颜色Col。

为了满足墨墨的要求，你知道你需要干什么了吗？

输入输出格式

输入格式：

第1行两个整数N，M，分别代表初始画笔的数量以及墨墨会做的事情的个数。

第2行N个整数，分别代表初始画笔排中第i支画笔的颜色。

第3行到第2+M行，每行分别代表墨墨会做的一件事情，格式见题干部分。

输出格式：

对于每一个Query的询问，你需要在对应的行中给出一个数字，代表第L支画笔到第R支画笔中共有几种不同颜色的画笔。

输入输出样例

输入样例#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：

说明

对于100%的数据，N≤50000，M≤50000，所有的输入数据中出现的所有整数均大于等于1且不超过10^6。

本题可能轻微卡常数

思路：

本题为带修莫队模板题，在普通莫队的基础上引入时间维度，可以支持时间推移和时间倒流。跑主算法时定义当前时间戳为t， $t$

$t$

代码:：

  1 #include <iostream>
  2 #include <cmath>
  3 #include <algorithm>
  4 #define max_n 50005
  5 using namespace std;
  6 int n,m;
  7 int a[max_n];
  8 int belong[max_n*2];
  9 int ans[max_n];
 10 int cnt[1000005];
 11 
 12 struct query
 13 {
 14     int l;
 15     int r;
 16     int id;
 17     int t;
 18 }q[max_n];
 19 struct modify
 20 {
 21     int pos;
 22     int col;
 23     int last;
 24 }c[max_n];
 25 int size;
 26 int bulk;
 27 int cntq = 0;
 28 int cntc = 0;
 29 int cmp(query a,query b)
 30 {
 31     return (belong[a.l]^belong[b.l])? belong[a.l]<belong[b.l]:((belong[a.r]^belong[b.r])?belong[a.r]<belong[b.r]:a.t<b.t);
 32 }
 33 int main()
 34 {
 35     cin >> n >> m;
 36     size = pow(n,2.0/3.0);
 37     bulk = ceil((double)n/size);
 38     for(int i = 1;i<=bulk;i++)
 39     {
 40         for(int j = (i-1)*size+1;j<=i*size;j++)
 41         {
 42             belong[j] = i;
 43         }
 44     }
 45     for(int i = 1;i<=n;i++)
 46     {
 47         cin >> a[i];
 48     }
 49     char opt;
 50     for(int i = 1;i<=m;i++)
 51     {
 52         cin >> opt;
 53         switch(opt)
 54         {
 55         case 'Q':
 56             cin >> q[++cntq].l;
 57             cin >> q[cntq].r;
 58             q[cntq].t = cntc;
 59             q[cntq].id= cntq;
 60             break;
 61         case 'R':
 62             cin >> c[++cntc].pos;
 63             cin >> c[cntc].col;
 64         }
 65     }
 66     sort(q+1,q+cntq+1,cmp);
 67     int l = 1;
 68     int r = 0;
 69     int time = 0;
 70     int now = 0;
 71     for(int i = 1;i<=cntq;i++)
 72     {
 73         int ql = q[i].l;
 74         int qr = q[i].r;
 75         int qt = q[i].t;
 76         while(l<ql) now -= !--cnt[a[l++]];
 77         while(l>ql) now += !cnt[a[--l]]++;
 78         while(r>qr) now -= !--cnt[a[r--]];
 79         while(r<qr) now += !cnt[a[++r]]++;
 80         while(time<qt)
 81         {
 82             ++time;//时间向后推移
 83             if(ql<=c[time].pos&&c[time].pos<=qr)//如果当前（time时）位置与查询区间重合，说明time时已经统计过c[time].pos处的元素，并且是以旧的时间的未修改的这个元素完成统计的
 84             {//压缩的运算表达式
 85                 now -= !--cnt[a[c[time].pos]]-!cnt[c[time].col]++;
 86                 //now是存的答案，c[time].pos是在time时修改的位置，a[c[time].pos]是在该位置原来的元素，注意now后是-=
 87                 //这句含义是1.如果在time时刻修改的位置（因为现在是时间还在往前走）上的元素的个数减少到零，now就减少一（因为这个元素已成为历史）
 88                 //c[time].col是在time时刻修改后的颜色
 89                 //2.如果对于在time时刻修改过的元素，它的个数为0，就将元素个数自增，然后now在加一（因为随着时间推移，发现了新的元素种类）
 90             }
 91             swap(a[c[time].pos],c[time].col);
 92             //让这个新元素（c[time].col）成为历史，用a[c[time].pos]暂时存储，
 93             //而c[time].col里是暂存原来被修改掉的元素
 94         }
 95         while(qt<time)
 96         {
 97             if(ql<=c[time].pos&&c[time].pos<=qr)
 98             {
 99                 now -= !--cnt[a[c[time].pos]]-!cnt[c[time].col]++;
100                 //同上
101             }
102             swap(a[c[time].pos],c[time].col);
103             //同上
104             --time;
105         }
106         ans[q[i].id] = now;
107     }
108     for(int i = 1;i<=cntq;i++)
109     {
110         cout << ans[i] << endl;
111     }
112     return 0;
113 }