带修莫队
分块块值一定要写成n^(2/3)这样是最优时间复杂度,否则acwing可以过,洛谷过不了!!!
题目描述
墨墨购买了一套 N 支彩色画笔(其中有些颜色可能相同),摆成一排,你需要回答墨墨的提问。
墨墨会像你发布如下指令:
Q L R 代表询问你从第 L 支画笔到第 R 支画笔中共有几种不同颜色的画笔。
R P Col 把第 P 支画笔替换为颜色 Col。
为了满足墨墨的要求,你知道你需要干什么了吗?
输入格式
第 1 行两个整数 N,M,分别代表初始画笔的数量以及墨墨会做的事情的个数。
第 2 行 N 个整数,分别代表初始画笔排中第 i 支画笔的颜色。
第 3 行到第 2+M 行,每行分别代表墨墨会做的一件事情,格式见题干部分。
输出格式
对于每一个 Query 的询问,你需要在对应的行中给出一个数字,代表第 L 支画笔到第 R 支画笔中共有几种不同颜色的画笔。
数据范围
1≤N,M≤10000,
修改操作不多于 1000 次,
所有的输入数据中出现的所有整数均大于等于 1 且不超过 106。
样例
输入样例:
6 5
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6
输出样例:
4
4
3
4
算法1
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
int B;
int get(int x){return x/B;}
struct node{
int l,r,t,id;
bool operator<(const node &tt) const {
int a = get(l), b = get(tt.l);
if (a != b) return a < b;
a = get(r), b = get(tt.r);
if (a != b) return a < b;
return t < tt.t;
}
}que[N];
struct T{
int p,col;
}c[N];
int a[N];
int res;
int ans[N];
int cnt[N];
int l=1,r=0,t=0;
inline void add(int x){
if(++cnt[a[x]]==1)res++;
}
inline void del(int x){
if(--cnt[a[x]]==0)res--;
}
inline void gotime(int x){
if(c[x].p<=r&&c[x].p>=l){
if(--cnt[a[c[x].p]]==0)res--;
if(++cnt[c[x].col]==1)res++;
}
swap(a[c[x].p],c[x].col);
}
int main(){
int n,q;
scanf("%d%d",&n,&q);
B=pow(n,0.66666)+1;
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
int cnt1=0,cnt2=0;
for(int i=1;i<=q;i++){
char s[3];
scanf("%s",&s);
if(s[0]=='Q'){
int l,r;
scanf("%d%d",&l,&r);
que[++cnt1]={l,r,cnt2,cnt1};
}
else{
int p,col;
scanf("%d%d",&p,&col);
c[++cnt2]={p,col};
}
}
sort(que+1,que+1+cnt1);
for(int i=1;i<=cnt1;i++){
while(r<que[i].r)add(++r);
while(l>que[i].l)add(--l);
while(r>que[i].r)del(r--);
while(l<que[i].l)del(l++);
while(t<que[i].t)gotime(++t);
while(t>que[i].t)gotime(t--);
ans[que[i].id]=res;
}
for(int i=1;i<=cnt1;i++)printf("%d\n",ans[i]);
}