【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，那么就会有个块。且假设n,m同阶。

当这次询问与上次询问的l在同一块内，l移动次数为，在不同块内，次数也为。l移动次数为。

当l在同一块中,r的移动和l同理，移动次数为。
当l跨过了一块，r的移动次数为，由于l最多跨过块，移动次数为。
所以r的移动次数为

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

整个算法复杂度。
当时，复杂度变成了

 #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 ;

 }

巴特西

bzoj2120 数颜色莫队带修改

【bzoj2120】数颜色

Description

Input

Output

Sample Input

Sample Output

HINT

最新文章

热门文章

巴特西

bzoj2120 数颜色 莫队 带修改

【bzoj2120】数颜色

Description

Input

Output

Sample Input

Sample Output

HINT

最新文章

热门文章

bzoj2120 数颜色莫队带修改