Bzoj 2453: 维护队列 && Bzoj 2120: 数颜色分块,bitset

2453: 维护队列

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 578 Solved: 247
[Submit][Status][Discuss]

Description

你小时候玩过弹珠吗？

小朋友A有一些弹珠，A喜欢把它们排成队列，从左到右编号为1到N。为了整个队列鲜艳美观，小朋友想知道某一段连续弹珠中，不同颜色的弹珠有多少。当然，A有时候会依据个人喜好，替换队列中某个弹珠的颜色。但是A还没有学过编程，且觉得头脑风暴太浪费脑力了，所以向你来寻求帮助。

Input

输入文件第一行包含两个整数N和M。

第二行N个整数，表示初始队列中弹珠的颜色。

接下来M行，每行的形式为“Q L R”或“R x c”，“Q L R”表示A想知道从队列第L个弹珠到第R个弹珠中，一共有多少不同颜色的弹珠，“R x c”表示A把x位置上的弹珠换成了c颜色。

Output

对于每个Q操作，输出一行表示询问结果。

Sample Input

2 3
1 2
Q 1 2
R 1 2
Q 1 2

Sample Output

2
1

HINT

对于100%的数据，有1 ≤ N ≤ 10000, 1 ≤ M ≤ 10000，小朋友A不会修改超过1000次，所有颜色均用1到10^6的整数表示。

Source

2011福建集训

 #include<bits/stdc++.h>

 using namespace std;

 #define MAXN 10010

 #define MAXM 1000010

 int n,a[MAXN],last[MAXN],pre[MAXM],block,pos[MAXN],h[MAXN];

 int read()

 {

     int s=,fh=;char ch=getchar();

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

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

     return s*fh;

 }

 void cl(int k)

 {

     int l=(k-)*block+,r=min(n,k*block),i;

     for(i=l;i<=r;i++)a[i]=last[i];

     sort(a+l,a+r+);

 }

 void Change(int x,int c)

 {

     int i,t;

     for(i=;i<=n;i++)pre[h[i]]=;

     h[x]=c;

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

     {

         t=last[i];

         last[i]=pre[h[i]];

         if(t!=last[i])cl(pos[i]);

         pre[h[i]]=i;

     }

 }

 int Find(int k,int ll)

 {

     int l=(k-)*block+,r=min(k*block,n),mid,t=;

     while(l<=r)

     {

         mid=(l+r)/;

         if(a[mid]>=ll)r=mid-;

         else if(a[mid]<ll)t=mid,l=mid+;

     }

     if(t==)return ;

     else return t-((k-)*block+)+;

 }

 int Query(int l,int r)

 {

     int ans=,i;

     if(pos[l]==pos[r])

     {

         for(i=l;i<=r;i++)if(last[i]<l)ans++;

     }

     else

     {

         for(i=l;i<=pos[l]*block;i++)if(last[i]<l)ans++;

         for(i=(pos[r]-)*block+;i<=r;i++)if(last[i]<l)ans++;

         for(i=pos[l]+;i<=pos[r]-;i++)ans+=Find(i,l);

     }

     return ans;

 }

 int main()

 {

     int M,i,m,s1,s2;

     char fh[];

     n=read();M=read();

     block=(int)sqrt(n);

     memset(last,,sizeof(last));

     memset(pre,,sizeof(pre));

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

     {

         h[i]=read();

         last[i]=pre[h[i]];

         pre[h[i]]=i;

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

     }

     if(block*block==n)m=n/block;

     else m=n/block+;

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

     for(i=;i<=M;i++)

     {

         scanf("\n%s",fh);s1=read();s2=read();

         if(fh[]=='Q')

         {

             printf("%d\n",Query(s1,s2));

         }

         else Change(s1,s2);

     }

     return ;

 }

 #include<bits/stdc++.h>

 using namespace std;

 int a[];

 bitset<> vis;

 int main()

 {

     int n,m,i,l,r,sum,j;

     char fh;

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

     for(i=;i<=n;i++)scanf("%d",&a[i]);

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

     {

         scanf("\n%c %d %d",&fh,&l,&r);

         if(fh=='Q')

         {

             vis.reset();

             sum=;

             for(j=l;j<=r;j++)if(vis[a[j]]==){sum++;vis[a[j]]=;}

             printf("%d\n",sum);

         }

         else

         {

             a[l]=r;

         }

     }

     return ;

 }

巴特西

Bzoj 2453: 维护队列 && Bzoj 2120: 数颜色分块,bitset

2453: 维护队列

Description

Input

Output

Sample Input

Sample Output

HINT

Source

最新文章

热门文章

巴特西

Bzoj 2453: 维护队列 && Bzoj 2120: 数颜色 分块,bitset

2453: 维护队列

Description

Input

Output

Sample Input

Sample Output

HINT

Source

最新文章

热门文章

Bzoj 2453: 维护队列 && Bzoj 2120: 数颜色分块,bitset