bzoj2120 数颜色莫队带修改

2021-11-02 11:16:19

【bzoj2120】数颜色

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。

其实还是可以用莫队的。只要记录下每组询问是多少次修改之后得到的，在每次做询问前，把现在少改的修改改上，多改的改回来。具体实现呢——暴力for循环。其他都一样。

由于每次都要暴力修改，要保证复杂度，排序方式应不一样。

这样排序，修改的的复杂度可能还是很高。所以还要调整块的大小。

设块大小为S，那么就会有 bzoj2120 数颜色莫队带修改个块。且假设n,m同阶。

当这次询问与上次询问的l在同一块内，l移动次数为 bzoj2120 数颜色莫队带修改，在不同块内，次数也为。l移动次数为。

当l在同一块中,r的移动和l同理，移动次数为 bzoj2120 数颜色莫队带修改。
当l跨过了一块，r的移动次数为，由于l最多跨过块，移动次数为。
所以r的移动次数为

再考虑修改的总复杂度。由于l,r在同一块中时，按修改次数单调递增排序，所以这是修改次数是O(n)的。
又因为l,r的不同的块共有 bzoj2120 数颜色莫队带修改种，所以总复杂度是

整个算法复杂度 bzoj2120 数颜色莫队带修改。
当时，复杂度变成了

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 #include<iostream>

 #include<cstdio>

 #define ll long long

 using namespace std;

 inline int read()

 {

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

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

     while(ch<=''&&ch>=''){x=(x<<)+(x<<)+ch-'';ch=getchar();}

     return x*f;

 }

 char st[];

 int c[],a[],cnt[],pos[],Ans[];

 int L,R,ans,Now;

 struct query{

     int l,r,pre,id;

 }Q[];

 struct modify{

     int x,pre,now;

 }M[];

 bool cmp(query x,query y)

 {

     if (pos[x.l]!=pos[y.l]) return pos[x.l]<pos[y.l];

     if (pos[x.r]!=pos[y.r]) return pos[x.r]<pos[y.r];

     else return x.pre<y.pre;

 }

 void modify(int pos,int key)

 {

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

     {

         cnt[a[pos]]--;

         if (!cnt[a[pos]]) ans--;

         cnt[key]++;

         if (cnt[key]==) ans++;

     }

     a[pos]=key;

 }

 inline void add(int x)

 {

     cnt[a[x]]++;

     if (cnt[a[x]]==) ans++;

 }

 inline void del(int x)

 {

     cnt[a[x]]--;

     if (cnt[a[x]]==) ans--;

 }

 int main()

 {

     int n,m;

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

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

         scanf("%d",&a[i]),c[i]=a[i];

     int x,key,l,r,cq=,cm=;

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

     {

         scanf("%s",st);

         if (st[]=='Q')

         {

             scanf("%d%d",&l,&r);

             Q[++cq].l=l,Q[cq].r=r,Q[cq].pre=cm,Q[cq].id=cq;

         }

         else

         {

             scanf("%d%d",&x,&key);

             M[++cm].x=x,M[cm].pre=c[x],M[cm].now=key,c[x]=key;

         }

     }

     int X=pow(n,0.67);

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

         pos[i]=(i-)/X+;

     sort(Q+,Q++cq,cmp);

     L=,R=;

     Now=ans=;

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

     {

         for (int j=Now+;j<=Q[i].pre;j++)

             modify(M[j].x,M[j].now);

         for (int j=Now;j>Q[i].pre;j--)

             modify(M[j].x,M[j].pre);

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

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

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

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

         Now=Q[i].pre;

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

     }

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

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

     return ;

 }

码农公寓