首页 > > 程序设计 > C/C++ >

P1903 【模板】分块/带修改莫队（数颜色）

2018-06-17 22:14:31来源：未知阅读 ()

题目描述

墨墨购买了一套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≤10000，M≤10000，修改操作不多于1000次，所有的输入数据中出现的所有整数均大于等于1且不超过10^6。

来源：bzoj2120

本题数据为洛谷自造数据，使用CYaRon耗时5分钟完成数据制作。

裸的带修改的莫队

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<algorithm>
  6 #include<cstdlib>
  7 #include<ctime>
  8 using namespace std;
  9 const int MAXN=10001;
 10 static void read(int &n)
 11 {
 12     char c='+';int x=0;bool flag=0;
 13     while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
 14     while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c-48);c=getchar();}
 15     flag==1?n=-x:n=x;
 16 }
 17 int n,m;
 18 int a[MAXN];
 19 struct CX
 20 {
 21     int l,r,id,tm;// tm上一次的更改操作 
 22 }cx[MAXN];
 23 int cxnum;
 24 struct GG
 25 {
 26     int pos,val,pre;
 27 }gg[MAXN];
 28 int ggnum;
 29 int head[MAXN];
 30 int where[MAXN];
 31 int base;
 32 int vis[MAXN];// 是否有更改操作 
 33 int color[MAXN];
 34 int ans=0;
 35 int out[MAXN];
 36 int comp(const CX &a,const CX &b)
 37 {
 38     if(where[a.l]==where[b.l])
 39         return a.r<b.r;
 40     else 
 41         return where[a.l]<where[b.l];
 42 }
 43 int calc(int x)
 44 {
 45     if(vis[x])
 46     {
 47         if(--color[a[x]]==0)
 48             ans--;
 49     }
 50     else 
 51     {
 52         if(++color[a[x]]==1)
 53             ans++;
 54     }    
 55     vis[x]=!vis[x];
 56 }
 57 void change(int p,int v)
 58 {
 59     if(vis[p])
 60     {
 61         calc(p);
 62         a[p]=v;
 63         calc(p);
 64     }
 65     else
 66     a[p]=v;
 67 }
 68 
 69 int main()
 70 {
 71     read(n);read(m);
 72     for(int i=1;i<=n;i++)
 73         read(a[i]),head[i]=a[i];
 74     base=sqrt(n);
 75     for(int i=1;i<=n;i++)
 76         where[i]=(i-1)/base+1;
 77     for(int i=1;i<=m;i++)
 78     {
 79         char c;
 80         int x,y;
 81         cin>>c;
 82         read(x);read(y);
 83         if(c=='Q')// 查询 
 84         {
 85             cxnum++;
 86             cx[cxnum].l=x;
 87             cx[cxnum].r=y;
 88             cx[cxnum].id=cxnum;
 89             cx[cxnum].tm=ggnum;
 90         }
 91         else
 92         {
 93             ggnum++;
 94             gg[ggnum].pos=x;
 95             gg[ggnum].val=y;
 96             gg[ggnum].pre=head[x];
 97             head[x]=y;
 98         }
 99     }
100     sort(cx+1,cx+cxnum+1,comp);
101     int l=1,r=0;
102     for(int i=1;i<=cxnum;i++)
103     {
104         for(int j=cx[i-1].tm+1;j<=cx[i].tm;j++)
105             change(gg[j].pos,gg[j].val);
106         for(int j=cx[i-1].tm;j>=cx[i].tm+1;j--)
107             change(gg[j].pos,gg[j].pre);// 此处是pre，不是val！！！ 
108         for(;l<cx[i].l;l++)
109             calc(l);
110         for(;l>cx[i].l;l--)
111             calc(l-1);
112         for(;r<cx[i].r;r++)
113             calc(r+1);
114         for(;r>cx[i].r;r--)
115             calc(r);
116         out[cx[i].id]=ans;
117     }
118     for(int i=1;i<=cxnum;i++)
119         printf("%d\n",out[i]);
120     return 0;
121 }