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（时间），按着l到r再到t的顺序排，分块大小应为n^(2/3)，在最后for循环的while中加入两个关于时间的while来调整当前时间与查询时间的关系。

因为移完t t做完一处修改后，有可能要改回来，所以我们还要把原值存好备用。但其实我们也可以不存，只要在修改后把修改操作的值和原值swap一下，那么改回来时也只要swap一下，swap两次相当于没搞，就改回来了。

代码:：

 #include <iostream>

 #include <cmath>

 #include <algorithm>

 #define max_n 50005

 using namespace std;

 int n,m;

 int a[max_n];

 int belong[max_n*];

 int ans[max_n];

 int cnt[];

 struct query

 {

     int l;

     int r;

     int id;

     int t;

 }q[max_n];

 struct modify

 {

     int pos;

     int col;

     int last;

 }c[max_n];

 int size;

 int bulk;

 int cntq = ;

 int cntc = ;

 int cmp(query a,query b)

 {

     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);

 }

 int main()

 {

     cin >> n >> m;

     size = pow(n,2.0/3.0);

     bulk = ceil((double)n/size);

     for(int i = ;i<=bulk;i++)

     {

         for(int j = (i-)*size+;j<=i*size;j++)

         {

             belong[j] = i;

         }

     }

     for(int i = ;i<=n;i++)

     {

         cin >> a[i];

     }

     char opt;

     for(int i = ;i<=m;i++)

     {

         cin >> opt;

         switch(opt)

         {

         case 'Q':

             cin >> q[++cntq].l;

             cin >> q[cntq].r;

             q[cntq].t = cntc;

             q[cntq].id= cntq;

             break;

         case 'R':

             cin >> c[++cntc].pos;

             cin >> c[cntc].col;

         }

     }

     sort(q+,q+cntq+,cmp);

     int l = ;

     int r = ;

     int time = ;

     int now = ;

     for(int i = ;i<=cntq;i++)

     {

         int ql = q[i].l;

         int qr = q[i].r;

         int qt = q[i].t;

         while(l<ql) now -= !--cnt[a[l++]];

         while(l>ql) now += !cnt[a[--l]]++;

         while(r>qr) now -= !--cnt[a[r--]];

         while(r<qr) now += !cnt[a[++r]]++;

         while(time<qt)

         {

             ++time;//时间向后推移

             if(ql<=c[time].pos&&c[time].pos<=qr)//如果当前（time时）位置与查询区间重合，说明time时已经统计过c[time].pos处的元素，并且是以旧的时间的未修改的这个元素完成统计的

             {//压缩的运算表达式

                 now -= !--cnt[a[c[time].pos]]-!cnt[c[time].col]++;

                 //now是存的答案，c[time].pos是在time时修改的位置，a[c[time].pos]是在该位置原来的元素，注意now后是-=

                 //这句含义是1.如果在time时刻修改的位置（因为现在是时间还在往前走）上的元素的个数减少到零，now就减少一（因为这个元素已成为历史）

                 //c[time].col是在time时刻修改后的颜色

                 //2.如果对于在time时刻修改过的元素，它的个数为0，就将元素个数自增，然后now在加一（因为随着时间推移，发现了新的元素种类）

             }

             swap(a[c[time].pos],c[time].col);

             //让这个新元素（c[time].col）成为历史，用a[c[time].pos]暂时存储，

             //而c[time].col里是暂存原来被修改掉的元素

         }

         while(qt<time)

         {

             if(ql<=c[time].pos&&c[time].pos<=qr)

             {

                 now -= !--cnt[a[c[time].pos]]-!cnt[c[time].col]++;

                 //同上

             }

             swap(a[c[time].pos],c[time].col);

             //同上

             --time;

         }

         ans[q[i].id] = now;

     }

     for(int i = ;i<=cntq;i++)

     {

         cout << ans[i] << endl;

     }

     return ;

 }

巴特西

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

题目描述：

输入输出格式

输入输出样例

说明

思路：

最新文章

热门文章