2453: 维护队列
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 521 Solved: 222
[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
我们首先定义一个pre数组，pre[i]表示i之前与i颜色相同的最近的点编号。
那么对于询问（x,y）只要计算x~y的pre中小于x的个数，就是答案。至于计算，我们可以分块来解决。
对于修改，直接暴力修改，能水过的。
代码：
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,len,num,L,R,ans,x,y;
char opt[10];
int a[10010],b[10010],pre[10010],last[1000010],l[110],r[110],flag[110];
int ask(int l,int r)
{
int ans=0;
for (int i=l;i<=r;i++) if (b[i]<x) ans++;
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
for (int i=1;i<=n;i++)
{
pre[i]=b[i]=last[a[i]];
last[a[i]]=i;
}
len=(int)sqrt(n);
if (n%len==0) num=n/len;else num=n/len+1;
for (int i=1;i<=num;i++)
{
l[i]=(i-1)*len+1;r[i]=min(i*len,n);
sort(pre+l[i],pre+r[i]+1);
}
while (m--)
{
scanf("%s%d%d",&opt,&x,&y);
if (opt[0]=='Q')
{
L=x/len;
if (x>r[L]) L++;
R=y/len;
if (y>r[R]) R++;
if (L==R){printf("%d\n",ask(x,y));continue;}
ans=ask(x,r[L])+ask(l[R],y);
for (int i=L+1;i<R;i++)
ans+=lower_bound(pre+l[i],pre+r[i]+1,x)-pre-l[i];
printf("%d\n",ans);
}else
{
for (int i=1;i<=n;i++) last[a[i]]=0;
a[x]=y;
for (int i=1;i<=num;i++) flag[i]=0;
for (int i=1;i<=n;i++)
{
if (b[i]!=last[a[i]]) flag[(i-1)/len+1]=1;
b[i]=last[a[i]];
last[a[i]]=i;
}
for (int i=1;i<=num;i++)
if (flag[i])
{
for (int j=l[i];j<=r[i];j++)
pre[j]=b[j];
sort(pre+l[i],pre+r[i]+1);
}
}
}
}
评论 (0)
