P1903 [国家集训队]数颜色 / 维护队列（莫队区间询问+单点修改）

题目链接:https://www.luogu.org/problemnew/show/P1903

题目大意：中文题目

具体思路：莫队单点修改+区间询问模板题，在原来的区间询问的基础上，我们要记录当前这次操作之前单点修改的操作都有哪些，如果有多余的操作，就先消除这些操作：如果操作数还不够，就在加上这些操作就可以了，这个题会卡常数，注意block的赋值。

block的赋值 = ceil(exp((log(n)+log(num1))/3));这里的num1指的是操作数，n代表点的个数。

然后我们可以对比一下我写的这篇文章，

P1494 [国家集训队]小Z的袜子（莫队）

，在每一次指针的移动的时候，这个题需要把先前的影响给去掉，又因为每一次值的个数需要平方，所以需要先把原来的影响给去掉再去加上新的影响。而这个题我们是只需要判断当前的点是1还是0就可以了。

 

AC代码：

 #include<iostream>

 #include<cmath>

 #include<stdio.h>

 #include<algorithm>

 #include<string>

 #include<cstring>

 using namespace std;

 # define ll long long

 const int maxn = 2e6+;

 int a[maxn],block;

 struct node1

 {

     int l,r,pos,id,num;

     bool friend operator < (node1 t1,node1 t2)

     {

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

         if(t1.r/block!=t2.r/block)return t1.r/block<t2.r/block;

         return t1.num<t2.num;

     }

 } q1[maxn];

 struct node2

 {

     int pos,val;

 } q2[maxn];

 int tot,vis[maxn],ans[maxn];

 void update(int id,int pos)

 {

     if(q2[pos].pos>=q1[id].l&&q2[pos].pos<=q1[id].r)

     {

     if(--vis[a[q2[pos].pos]]==)

         tot--;

     if(++vis[q2[pos].val]==)

         tot++;

     }

     swap(a[q2[pos].pos],q2[pos].val);

 }

 inline int read()

 {

     char c=getchar();int x=,f=;

     while(c<''||c>''){if(c=='-')f=-;c=getchar();}

     while(c>=''&&c<=''){x=x*+c-'',c=getchar();}

     return x*f;

 }

 void solve(int num1)

 {

     int num=,l=,r=;

     tot=;

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

     {

         while(l<q1[i].l)if(--vis[a[l++]]==)tot--;

         while(l>q1[i].l)if(++vis[a[--l]]==)tot++;

         while(r<q1[i].r)if(++vis[a[++r]]==)tot++;

         while(r>q1[i].r)if(--vis[a[r--]]==)tot--;

         while(num<q1[i].num){

             num++;

             update(i,num);

         }

         while(num>q1[i].num)

         {

             update(i,num);

             num--;

         }

         ans[q1[i].id]=tot;

     }

     return ;

 }

 int main()

 {

    // cout<<pow(50000,5.0/3.0)<<endl;

    // memset(vis,0,sizeof(vis));

    // freopen("hqx.in","r",stdin);

     int n,m;

     n=read();

     m=read();

     //scanf("%d %d",&n,&m);

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

     {

         a[i]=read();

     }

     char str[];

     int st,ed;

     int num1=,num2=;

     while(m--)

     {

         scanf("%s",str);

         st=read();

         ed=read();

         if(str[]=='Q')

         {

             q1[++num1].l=st;

             q1[num1].r=ed;

             q1[num1].num=num2;

             q1[num1].id=num1;

         }

         else if(str[]=='R')

         {

             q2[++num2].pos=st;

             q2[num2].val=ed;

         }

     }

     block=ceil(exp((log(n)+log(num1))/));

     sort(q1+,q1+num1+);

     solve(num1);

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

     {

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

     }

 //    for(int i=1;i<=5;i++){

 //    cout<<i<<" "<<vis[i]<<endl;

 //    }

     return ;

 }