2453: 维护队列
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 402 Solved: 170
[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
1
HINT
对于100%的数据，有1 ≤ N ≤ 10000, 1 ≤ M ≤ 10000，小朋友A不会修改超过1000次，所有颜色均用1到10^6的整数表示。
Source
题目同2120。。今天刚看到的双倍经验。
然而要交的时候才发现我这道题原来交的时候贴错代码了。。。把标程贴了上去
。。还满心欢喜以为自己过了。这几天精神真的不正常。。
。。还满心欢喜以为自己过了。这几天精神真的不正常。。
幸好我自己的程序也是对的否则真要*狗了。
最近刷的一波分块的第二道。。要求一段区间的颜色总数，并支持修改。
我们考虑一个点\(a\)，如果在区间\([x,y]\)中要被计算，那么就要满足\([x,a-1]\)中a的颜色没有出现过。我们可以计每一个点之前最近的与其颜色相同的点的位置，然后对区间中每个点，如果它的前驱不在区间中就将\(ans\)++。
我们可以用分块维护前驱的数组,从小到大排序，二分查找前驱不属于询问区间的位置个数。
修改：因为修改不超过1000个，所以可以暴力向后扫找到后继，然后进行修改。复杂度也是对的。注意考虑一下找不到的情况。
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000010;
int c[N],a[N],b[N],pos[N],last[N],n,m,Q,l,r,Pos,val,blk,cl;
char opt[5];
int read(){
int x = 0,f = 1,c = getchar();
while (c<'0' || c>'9') {if (c=='-') f = -1;c = getchar();}
while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
return x*f;
}
bool cmp(int a,int b){return a<b;}
void Getpre(){
for (int i=1;i<=n;i++){
a[i] = last[c[i]];last[c[i]] = i;
b[i] = a[i];
}
}
void reset(int x){
int l = (x-1)*blk+1,r = min(n,x*blk);
for (int i=l;i<=r;i++) b[i] = a[i];
sort(b+l,b+r+1,cmp);
}
int find(int x,int val){
int l = (x-1)*blk+1,r = x*blk,ans = 0;
while (l<=r){
int mid = (l+r)>>1;
if (b[mid]<val) {ans = mid-(x-1)*blk;l = mid+1;}
else r = mid-1;
}
return ans;
}
int Query(int l,int r){
int res = 0;
if (pos[l]==pos[r]) {for (int i=l;i<=r;i++) if (a[i]<l) res++;}
else {
for (int i=l;i<=min(n,pos[l]*blk);i++) if (a[i]<l) res++;
for (int i=(pos[r]-1)*blk+1;i<=r;i++) if (a[i]<l) res++;
}
for (int i=pos[l]+1;i<pos[r];i++) res+=find(i,l);
return res;
}
void change(int Pos,int val){
int P = -1;
for (int i=Pos+1;i<=n;i++) if (c[i]==c[Pos]) {P = i;break;}
if (P!=-1) {
a[P] = a[Pos];
reset(pos[P]);
}
else last[c[Pos]] = a[Pos];
P = -1;
for (int i=Pos+1;i<=n;i++) if (c[i]==val) {P = i;break;}
if (P!=-1){
a[Pos] = a[P];a[P] = Pos;
reset(pos[Pos]);reset(pos[P]);
}
else {
a[Pos] = last[val];
last[val] = Pos;
reset(pos[Pos]);
}
c[Pos] = val;
}
int main(){
n = read();Q = read();
blk = (int)sqrt(n);
for (int i=1;i<=n;i++) c[i] = read(),pos[i] = (i-1)/blk+1;
Getpre();
if (n%blk) m = n/blk+1;
else m = n/blk;
for (int i=1;i<=m;i++) reset(i);
for (int i=1;i<=Q;i++){
scanf("%s",opt);
if (opt[0]=='Q'){l = read();r = read();printf("%d\n",Query(l,r));}
else {
Pos = read();cl = read();
change(Pos,cl);
}
}
}
评论 (0)
