BZOJ2120 数颜色 —— 待修改莫队

时间：2022-03-05 22:00:29

题目链接：https://vjudge.net/problem/HYSBZ-2120

2120: 数颜色

Time Limit: 6 Sec  Memory Limit: 259 MB
Submit: 6898  Solved: 2781
[Submit][Status][Discuss]

Description

墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会像你发布如下指令： 1、 Q L R代表询问你从第L支画笔到第R支画笔*有几种不同颜色的画笔。 2、 R P Col 把第P支画笔替换为颜色Col。为了满足墨墨的要求，你知道你需要干什么了吗？

Input

第1行两个整数N，M，分别代表初始画笔的数量以及墨墨会做的事情的个数。第2行N个整数，分别代表初始画笔排中第i支画笔的颜色。第3行到第2+M行，每行分别代表墨墨会做的一件事情，格式见题*分。

Output

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

Sample Input

6 5
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6

Sample Output

4
4
3
4

HINT

对于100%的数据，N≤10000，M≤10000，修改操作不多于1000次，所有的输入数据中出现的所有整数均大于等于1且不超过10^6。

2016.3.2新加数据两组by Nano_Ape

题意：

查询区间颜色种数，且带修改。

代码如下：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 #include <cmath>

 #include <queue>

 #include <stack>

 #include <map>

 #include <string>

 #include <set>

 using namespace std;

 typedef long long LL;

 const int INF = 2e9;

 const LL LNF = 9e18;

 const int MOD = 1e9+;

 const int MAXN = 1e6+;

 int val[MAXN], tmp[MAXN];

 int block, sum[MAXN], Ans[MAXN];

 int num1, num2;

 struct Node

 {

     //index记录查询的编号， t记录查询时执行了多少步修改

     int l, r, index, t;

     bool operator<(const Node&x) const{

         if(l/block!=x.l/block) return l/block<x.l/block;

         else if(r!=x.r) return r<x.r;

         else return  t<x.t;

     }

 }q[MAXN];

 struct

 {

     //preCol记录修改前pos位的颜色， nowCol记录修改后pos位的颜色

     int pos, nowCol, preCol;

 }op[MAXN];

 int L, R, T, ans;

 void modifyTime(int pos, int col)

 {

     if(L<=pos && pos<=R)

     {

         sum[val[pos]]--;

         if(sum[val[pos]]==) ans--;

         val[pos] = col;

         sum[val[pos]]++;

         if(sum[val[pos]]==) ans++;

     }

     else val[pos] = col;

 }

 void add(int pos)

 {

     sum[val[pos]]++;

     if(sum[val[pos]]==) ans++;

 }

 void del(int pos)

 {

     sum[val[pos]]--;

     if(sum[val[pos]]==) ans--;

 }

 void work()

 {

     L = , R = , T = , ans = ;

     memset(sum, , sizeof(sum));

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

     {

         while(T<q[i].t) T++, modifyTime(op[T].pos, op[T].nowCol);

         while(T>q[i].t) modifyTime(op[T].pos, op[T].preCol), T--;

         while(L<q[i].l) del(L), L++;

         while(L>q[i].l) L--, add(L);

         while(R<q[i].r) R++, add(R);

         while(R>q[i].r) del(R), R--;

         Ans[q[i].index] = ans;

     }

 }

 int main()

 {

     int n, m;

     while(scanf("%d%d", &n,&m)!=EOF)

     {

         block = sqrt(n);

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

         {

             scanf("%d", &val[i]);

             tmp[i] = val[i];

         }

         num1 = num2 = ;

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

         {

             char s[]; int x, y;

             scanf("%s%d%d", s, &x, &y);

             if(s[]=='Q')

             {

                 q[++num1].index = num1;

                 q[num1].t = num2;

                 q[num1].l = x;

                 q[num1].r = y;

             }

             else    //tmp用于记录动态修改时每个位置上的颜色

             {

                 op[++num2].pos = x;

                 op[num2].nowCol = y;

                 op[num2].preCol = tmp[x];

                 tmp[x] = y;

             }

         }

         sort(q+, q++num1);

         work();

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

             printf("%d\n", Ans[i]);

     }

 }

直接暴力也行：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 #include <cmath>

 #include <queue>

 #include <stack>

 #include <map>

 #include <string>

 #include <set>

 using namespace std;

 typedef long long LL;

 const int INF = 2e9;

 const LL LNF = 9e18;

 const int MOD = 1e9+;

 const int MAXN = 1e6+;

 int val[MAXN], tmp[MAXN];

 int block, sum[MAXN], Ans[MAXN];

 int num1, num2;

 struct Node

 {

     //index记录查询的编号， t记录查询时执行了多少步修改

     int l, r, index, t;

 }q[MAXN];

 struct

 {

     //preCol记录修改前pos位的颜色， nowCol记录修改后pos位的颜色

     int pos, nowCol, preCol;

 }op[MAXN];

 int L, R, T, ans;

 void modifyTime(int pos, int col)

 {

     if(L<=pos && pos<=R)

     {

         sum[val[pos]]--;

         if(sum[val[pos]]==) ans--;

         val[pos] = col;

         sum[val[pos]]++;

         if(sum[val[pos]]==) ans++;

     }

     else val[pos] = col;

 }

 void add(int pos)

 {

     sum[val[pos]]++;

     if(sum[val[pos]]==) ans++;

 }

 void del(int pos)

 {

     sum[val[pos]]--;

     if(sum[val[pos]]==) ans--;

 }

 void work()

 {

     L = , R = , T = , ans = ;

     memset(sum, , sizeof(sum));

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

     {

         while(T<q[i].t) T++, modifyTime(op[T].pos, op[T].nowCol);

         while(T>q[i].t) modifyTime(op[T].pos, op[T].preCol), T--;

         while(L<q[i].l) del(L), L++;

         while(L>q[i].l) L--, add(L);

         while(R<q[i].r) R++, add(R);

         while(R>q[i].r) del(R), R--;

         Ans[q[i].index] = ans;

     }

 }

 int main()

 {

     int n, m;

     while(scanf("%d%d", &n,&m)!=EOF)

     {

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

         {

             scanf("%d", &val[i]);

             tmp[i] = val[i];

         }

         num1 = num2 = ;

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

         {

             char s[]; int x, y;

             scanf("%s%d%d", s, &x, &y);

             if(s[]=='Q')

             {

                 q[++num1].index = num1;

                 q[num1].t = num2;

                 q[num1].l = x;

                 q[num1].r = y;

             }

             else    //tmp用于记录动态修改时每个位置上的颜色

             {

                 op[++num2].pos = x;

                 op[num2].nowCol = y;

                 op[num2].preCol = tmp[x];

                 tmp[x] = y;

             }

         }

         work();

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

             printf("%d\n", Ans[i]);

     }

 }

相关文章