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支畫筆中共有幾種不同顏色的畫筆。

輸入輸出樣例

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

4
4
3
4

說明

對於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 }