区间检测题解

记录 \(pre_i\) 为 \(a_i\) 上一次出现的位置。

每一次求 \([L,R]\) 范围内是否有相同的数即 \(pre_L\) 到 \(pre_R\) 中的最大值是否小于 \(L\)。

注意到 \(pre_1\) 到 \(pre_{L-1}\) 中最大数一定小于 \(L\)，所以求 \([L,R]\) 范围内是否有相同的数即\(pre_1\) 到 \(pre_R\) 中的最大值是否小于 \(L\)。

接下来考虑如何求 \(pre\)，将原数组排序后相同的数就会靠在一起，也就可以求 \(pre\) 了。

给出85ms代码：

#include<bits/stdc++.h>
using namespace std;
const int M=500005;
int n,m,A[M],pre[M],B[M];
void rd(int &res){
	char c;res=0;
	while(c=getchar_unlocked(),c<48);
	do res=(res<<3)+(res<<1)+(c^48);
	while(c=getchar_unlocked(),c>=48);
}
int main(){
	rd(n);rd(m);
	for(int i=1;i<=n;i++) rd(A[i]),B[i]=i;
	sort(B+1,B+n+1,[&](int i,int j){return A[i]<A[j]||(A[i]==A[j]&&i<j);});
	for(int i=2;i<=n;i++)
		if(A[B[i]]==A[B[i-1]]) pre[B[i]]=B[i-1];
	for(int i=2;i<=n;i++) 
		if(pre[i]<pre[i-1]) pre[i]=pre[i-1];
	int L,R;
	while(m--){
		rd(L);rd(R);
		putchar_unlocked((pre[R]<L)^48);
		putchar_unlocked('\n');
	} 
}

接下来考虑优化排序，因为每个32位整形都由2个16位二进制组成，所以可以类比基数排序写出更快的基数排序，先按低16位排序，再按高16位排序。

正解：

//std
#include<bits/stdc++.h>
using namespace std;
const int M=500005;
int n,m,A[M],pre[M],C[65536],B[M],D[M],P=65535;
inline void rd(int &res){
	char c;res=0;
	while(c=getchar_unlocked(),c<48);
	do res=(res<<3)+(res<<1)+(c^48);
	while(c=getchar_unlocked(),c>=48);
}
inline void Sort(){
	for(int i=1;i<=n;++i) C[A[i]&P]++;
	for(int i=1;i<=P;++i) C[i]+=C[i-1];
	for(int i=n;i>=1;--i) B[C[A[i]&P]--]=i;
	memset(C,0,sizeof C);
	for(int i=1;i<=n;++i) ++C[(A[B[i]]>>16)&P];
	for(int i=1;i<=P;++i) C[i]+=C[i-1];
	for(int i=n;i>=1;--i) D[C[(A[B[i]]>>16)&P]--]=B[i];
	for(int i=1;i<=n;++i) B[i]=D[i];
}
int main(){
	rd(n);rd(m);
	for(int i=1;i<=n;++i) rd(A[i]);
	Sort();
	for(int i=2;i<=n;++i)
		if(A[B[i]]==A[B[i-1]]) pre[B[i]]=B[i-1];
	for(int i=2;i<=n;++i) 
		if(pre[i]<pre[i-1]) pre[i]=pre[i-1];
	int L,R;
	while(m--){
		rd(L);rd(R);
		putchar_unlocked((pre[R]<L)^48);
		putchar_unlocked('\n');
	} 
}