前言
这是一篇分块题解，大概的思路洛谷的题解里的巨佬讲的很清楚（我的思路其实和大佬的差不多），可以去看看qaq。
因为苯人为了卡常魔改代码，所以在本题解的中间具体步骤展示部分仅展示魔改前的代码（也就是被卡常但是好看一点的代码），魔改后的代码（100pts）在文章最末展示。
题意
有一个长度为\(n\)数列，第\(i\)个数的颜色为\(a_i\)，有\(m\)次询问，询问区间\([l,r]\)有多少种不同的颜色。
前置芝士
1.分块
2.卡常（拨珠这种代码十分丑陋的蒟蒻被疯狂卡常了）
思路
看到这个题是区间查询的那一刻博主就手痒想写分块。虽然博主菜的要死每次写分块都要调好久。
- 关于整块：
1.预处理出每一块的颜色种类数量，记为\(f_{i,i}\)，其中\(i\)代表第\(i\)块，则\(f_{i,i}\)表示第\(i\)块的颜色种数（这一步主要是为第2步服务）
2.预处理出第\(i\)块到第\(j\)块的颜色种类数量，记为\(f_{i,j}\)
3.在讯问时，整块部分直接加上预处理好的数就可以了 - 关于散块：
直接暴力搞，就这个暴力爽
具体实现
1.输入时：记录每个数左边和右边最接近的同颜色点的编号，可以用一个\(ne\)（new）数组表示某个颜色最新的点的编号来辅助记录。
代码
for(register int i=1;i<=n;i++){
a[i]=read();
le[i]=last[a[i]];
last[a[i]]=i;
ri[i]=n+1;
ri[le[i]]=i;//block为块长，即sqrt(n)
bel[i]=(i-1)/block+1;//bel数组表示属于哪个块
}
2.预处理：预处理的作用就是可以减少询问时的时间复杂度。具体操作如下：
- 计算\(f_{i,i}\)的方式：枚举\(1\thicksim\sqrt{n}\)的块，当前为第\(i\)块，第\(j\)个数，用一个\(vis\)数组记录第\(j\)个数的颜色有没有在块\(i\)中出现过，如果没有，则\(f_{i,i}\)加一。
代码
for(register int i=1;i<=bel[n];i++){
vis.reset();
for(int j=(i-1)*block+1;j<=min(n,i*block);j++){
f[i][i]+=(!vis[a[j]]);
vis[a[j]]=1;
}
}
- 计算\(f_{i,j}\)的方式：枚举块\(i\)和\(j\)，\(f_{i,j}\)为\(f_{i,j-1}\)加上在块\(j\)中出现了，但是在\(i\thicksim j\)中没有出现的颜色总数
代码
for(register int i=1;i<=bel[n];i++){//bel[i]代表点i在哪个块
for(int j=i+1;j<=bel[n];j++){
f[i][j]=f[i][j-1];
for(int k=(j-1)*block+1;k<=min(j*block,n);k++){
if(bel[le[k]]<i){//block代表块长，即sqrt(n)
f[i][j]++;
}
}
}
}
3.询问：
- 当\(l,r\)的差小于等于1时特判，并暴力计算个数。
- 其他的时候，整块的值为预处理中的\(f\)数组，散块暴力枚举（具体看代码注释）
代码
int query(int l,int r){
int ret=0;
if(bel[r]-bel[l]<=1){
vis.reset();
for(register int i=l;i<=r;i++){
ret+=(!vis[a[i]]);
vis[a[i]]=1;
}
return ret;
}
if(bel[r]-bel[l]>=2){
ret+=f[bel[l]+1][bel[r]-1];
}
for(register int i=l;i<=min(r,block*bel[l]);i++){
if(bel[ri[i]]>=bel[r]){//中间的整块没有出现过这个颜色
ret++;
}
}
for(register int i=(bel[r]-1)*block+1;i<=r;i++){
if(le[i]<l){//中间的整块和左边的散块都没有出现过这个颜色
ret++;
}
}
return ret;
}
tips：
1.分块真的好难调啊啊啊，一定要注意边界啊啊
2.注意第i个点的颜色和第i个点的编号的区别
3.要注意的地方都是大部分分块题要注意的地方，如果实在找不出来问题重构也很好（我重构了114514次/fad
卡常
1.vis数组使用\(bitset\)
2.快读快写，我还用的是getchar_unlocked()（类目）
3.手写\(max\)和\(min\)
4.unsigned int和register int
5.++i屁用没有
6.换行用puts("")
7.i=1改为i(1)
被魔改得面目全非的代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int MAXN=1e6+5;
const int MAXM=1e3+5;
unsigned int a[MAXN],le[MAXN],ri[MAXN],last[MAXN],bel[MAXN];
bitset<MAXN>vis;
unsigned int block;
unsigned int f[MAXM][MAXM];
inline int max(int x,int y){
return (x>y)?x:y;
}
inline int min(int x,int y){
return (x<y)?x:y;
}
int query(int l,int r){
int ret=0;
if(bel[r]-bel[l]<=1){
vis.reset();
for(register int i(l);i<=r;i++){
ret+=(!vis[a[i]]);
vis[a[i]]=1;
}
return ret;
}
if(bel[r]-bel[l]>=2){
ret+=f[bel[l]+1][bel[r]-1];
}
for(register int i(l);i<=min(r,block*bel[l]);i++){
ret+=(bel[ri[i]]>=bel[r]);
}
if(bel[l]!=bel[r]){
for(register int i((bel[r]-1)*block+1);i<=r;i++){
ret+=(le[i]<l);
}
}
return ret;
}
inline int read(){
int x=0,f=1;
char ch=getchar_unlocked();
while(ch<'0' || ch>'9'){
if(ch=='-'){
f=-1;
}
ch=getchar_unlocked();
}
while(ch<='9' && ch>='0'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar_unlocked();
}
return x*f;
}
void print(int x)
{
if (!x) return ;
if (x < 0) putchar('-'),x = -x;
print(x / 10);
putchar(x % 10 + '0');
}
int main(){
n=read();
block=sqrt(n);
for(register int i(1);i<=n;i++){
a[i]=read();
le[i]=last[a[i]];
last[a[i]]=i;
ri[i]=n+1;
ri[le[i]]=i;
bel[i]=(i-1)/block+1;
}
bel[n+1]=bel[n]+1;
for(register int i(1);i<=bel[n];i++){
vis.reset();
for(register int j((i-1)*block+1);j<=min(n,i*block);j++){
f[i][i]+=(!vis[a[j]]);
vis[a[j]]=1;
}
}
// cout<<ri[3]<<endl;
for(register int i(1);i<=bel[n];i++){
for(register int j(i+1);j<=bel[n];j++){
f[i][j]=f[i][j-1];
for(register int k((j-1)*block+1);k<=min(j*block,n);k++){
f[i][j]+=(bel[le[k]]<i);
}
}
}
m=read();
for(register int i(1);i<=m;i++){
int a,b;
a=read(),b=read();
print(query(a,b));
puts("");
}
}
结语
呃呃呃呃分块真的好难调，调了一个晚上半个上午，我太菜了。
真的写不动题了（躺）。每天水水题解一天就过去了。
求壶关qwq，有问题的话欢迎指出
洛谷账号