BZOJ 2120[国家集训队]数颜色
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 Input6 5 1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6Sample Output
4
4
3
4
带修改的莫队。。同样是将询问通过排序来减少转移距离
但由于有修改,又要按询问排序,所以记一下每个询问之前有多少修改
如果当前比询问的修改多了就撤销,如果少了就继续修改
在排序时应该在区间转移尽量小的情况下,让重复修改次数尽量少
洛谷上的数据强度很大,需要一些排序技巧,比如说奇数左偶数右。。这个我还不知道原理
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#define ll long long
int c[6000000],n,m;
int block;
int l=0,r=-1;
struct anss{
int l,r,pos,bl,cn;
bool operator < (const anss m) const{
if(bl!=m.bl) return bl<m.bl;
if(r/block!=m.r/(block)){
if(bl&1)
return r/block<m.r/block;
return r/block>m.r/block;
}
return cn<m.cn;
}
}a[60000];
inline ll gcd(ll a,ll b){
//if(a<b) std::swap(a,b);
return b==0?a:gcd(b,a%b);
}
ll fm,fz,cnt[6000000],a1[60000],a2[60000];
inline int add(int x){
cnt[x]++;
if(cnt[x]==1) fz++;
}
inline int del(int x){
cnt[x]--;
if(cnt[x]==0) fz--;
}
int ch1[60000];
int ch2[60000];
inline int change(int x){
std::swap(c[ch1[x]],ch2[x]);
if(l<=ch1[x]&&ch1[x]<=r){//精髓
cnt[c[ch1[x]]]++;
cnt[ch2[x]]--;
if(cnt[c[ch1[x]]]==1) fz++;
if(cnt[ch2[x]]==0) fz--;
}
}
int cn=0,tot=0;
int main () {
scanf("%d %d",&n,&m);
block=pow(n,2.0/3);//块大小开根号2/3n
for(int i=1;i<=n;++i) scanf("%d",&c[i]);
for(int i=1;i<=m;++i){
char x;
scanf(" %c",&x);
if(x=='Q') {
++tot;
scanf("%d %d",&a[tot].l,&a[tot].r);
if(a[tot].l>a[tot].r)std::swap(a[tot].l,a[tot].r);
a[tot].pos=tot;a[tot].bl=(a[tot].l-1)/(block)+1;
a[tot].cn=cn;
}
if(x=='R'){
int xx,y;
scanf("%d %d",&xx,&y);
ch1[++cn]=xx,ch2[cn]=y;
}
}
cn=0;
std::sort(a+1,a+1+tot);
for(int i=1;i<=tot;++i){
while(cn>a[i].cn){//修改次数
change(cn);
cn--;
}
while(cn<a[i].cn){
cn++;
change(cn);
}
while(l<a[i].l){
del(c[l]);
l++;
}
while(l>a[i].l){
l--;
add(c[l]);
}
while(r<a[i].r){
r++;
add(c[r]);
}
while(a[i].r<r){
del(c[r]);
r--;
}
a1[a[i].pos]=fz;
}
for(int i=1;i<=tot;++i){
printf("%lld\n",a1[i]);
}
return 0;
}
0 条评论