bzoj2120

题解：

可修改莫队

我们加入一个时间T

然后在排序的时候考虑一下时间

在计算的时候也要考虑

代码：

#include<bits/stdc++.h>

using namespace std;

const int N=;

struct Query

{

    int l,r,Tim,id;

}q[N];

struct Change

{

    int pos,New,Old;

}c[N];

char sign[];

int n,m,s[N],color[N*],t,x,y,Time,now[N],unit,Be[N],ans[N],Ans,l=,r,T;

int cmp(Query a,Query b)

{

    if (Be[a.l]!=Be[b.l])return a.l<b.l;

    if (Be[a.r]!=Be[b.r])return a.r<b.r;

    return a.Tim<b.Tim;

}

void revise(int x,int d)

{

    color[x]+=d;

    if (d>)Ans+=color[x]==;

    if (d<)Ans-=color[x]==;

}

void doit(int x,int d)

{

    if (l<=x&&x<=r)

     {

         revise(d,);

         revise(s[x],-);

     }

    s[x]=d;

}

int main()

{

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

    int unit=pow(n,0.666666);

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

     {

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

         now[i]=s[i];

         Be[i]=i/unit+;

     }

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

     {

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

         if (sign[]=='Q')q[++t]=(Query){x,y,Time,t};

         if (sign[]=='R')c[++Time]=(Change){x,y,now[x]},now[x]=y;

     }

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

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

     {

         while (T<q[i].Tim)doit(c[T+].pos,c[T+].New),T++;

         while (T>q[i].Tim)doit(c[T].pos,c[T].Old),T--;

        while (l<q[i].l)revise(s[l],-),l++;

        while (l>q[i].l)revise(s[l-],),l--;

        while (r<q[i].r)revise(s[r+],),r++;

        while (r>q[i].r)revise(s[r],-),r--;

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

     }

    for (int i=;i<=t;i++)printf("%d\n",ans[i]);

}