2453: 维护队列
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1079 Solved: 503
[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
1 2
Q 1 2
R 1 2
Q 1 2
Sample Output
2
1
1
HINT
对于100%的数据，有1 ≤ N ≤ 10000, 1 ≤ M ≤ 10000，小朋友A不会修改超过1000次，所有颜色均用1到10^6的整数表示。
Source
带修莫队
#include<cmath>
#include<cstdio>
#include<algorithm>
#define N 10001
#define M 1000001
using namespace std;
int n,m,col[M],sum[M],ans[N];
int tot,now,siz,tmp;
struct Query
{
int l,r,bl,id,tim;
bool operator < (Query p) const
{
if(bl!=p.bl) return bl<p.bl;
if(r!=p.r) return r<p.r;
return tim<p.tim;
}
}e[N];
struct Change
{
int be,af,pos;
}g[];
void update(int p,int w)
{
sum[p]+=w;
if(sum[p]== && w==) tmp++;
if(!sum[p] && w==-) tmp--;
}
int main()
{
scanf("%d%d",&n,&m);
siz=sqrt(n);
for(int i=;i<=n;i++) scanf("%d",&col[i]);
char s[]; int l,r;
while(m--)
{
scanf("%s%d%d",s,&l,&r);
if(s[]=='Q')
{
e[++tot].l=l; e[tot].r=r; e[tot].bl=(l-)/siz; e[tot].tim=now;
e[tot].id=tot;
}
else
{
g[++now].pos=l; g[now].af=r;
}
}
sort(e+,e+tot+);
int L=,R=; now=;
for(int i=;i<=tot;i++)
{
while(now<e[i].tim)
{
now++;
g[now].be=col[g[now].pos];
if(g[now].pos>=L&&g[now].pos<=R)
{
update(g[now].be,-);
update(g[now].af,);
}
col[g[now].pos]=g[now].af;
}
while(now>e[i].tim)
{
if(g[now].pos>=L&&g[now].pos<=R)
{
update(g[now].af,-);
update(g[now].be,);
}
col[g[now].pos]=g[now].be;
now--;
}
while(e[i].l<L) update(col[--L],);
while(e[i].l>L) update(col[L++],-);
while(e[i].r>R) update(col[++R],);
while(e[i].r<R) update(col[R--],-);
ans[e[i].id]=tmp;
}
for(int i=;i<=tot;i++) printf("%d\n",ans[i]);
}
优化后：
读入优化、1，-1改成 true，false
优化一半
#include<cmath>
#include<cstdio>
#include<algorithm>
#define N 10001
#define M 1000001
using namespace std;
int n,m,col[M],sum[M],ans[N];
int tot,now,siz,tmp;
struct Query
{
int l,r,bl,id,tim;
bool operator < (Query p) const
{
if(bl!=p.bl) return bl<p.bl;
if(r!=p.r) return r<p.r;
return tim<p.tim;
}
}e[N];
struct Change
{
int be,af,pos;
}g[];
void update(int p,bool w)
{
if(w)
{
sum[p]++;
if(sum[p]==) tmp++;
}
else
{
sum[p]--;
if(!sum[p]) tmp--;
}
}
void read(int &x)
{
x=; char c=getchar();
while(c<''||c>'') c=getchar();
while(c>=''&&c<='') { x=x*+c-''; c=getchar(); }
}
int main()
{
read(n); read(m);
siz=sqrt(n);
for(int i=;i<=n;i++) read(col[i]);
char s[]; int l,r;
while(m--)
{
scanf("%s",s);
read(l); read(r);
if(s[]=='Q')
{
e[++tot].l=l; e[tot].r=r; e[tot].bl=(l-)/siz; e[tot].tim=now;
e[tot].id=tot;
}
else
{
g[++now].pos=l; g[now].af=r;
}
}
sort(e+,e+tot+);
int L=,R=; now=;
for(int i=;i<=tot;i++)
{
while(now<e[i].tim)
{
now++;
g[now].be=col[g[now].pos];
if(g[now].pos>=L&&g[now].pos<=R)
{
update(g[now].be,false);
update(g[now].af,true);
}
col[g[now].pos]=g[now].af;
}
while(now>e[i].tim)
{
if(g[now].pos>=L&&g[now].pos<=R)
{
update(g[now].af,false);
update(g[now].be,true);
}
col[g[now].pos]=g[now].be;
now--;
}
while(e[i].l<L) update(col[--L],true);
while(e[i].l>L) update(col[L++],false);
while(e[i].r>R) update(col[++R],true);
while(e[i].r<R) update(col[R--],false);
ans[e[i].id]=tmp;
}
for(int i=;i<=tot;i++) printf("%d\n",ans[i]);
}