题解：CF2009G1 Yunli's Subarray Queries (easy version)

题目要求 \(a_i=a_{i-1}+1\)，设 \(b_i=a_i-i\)，如果 \(b_i=b_j\)，那么 \(i\) 和 \(j\) 就在正确的相对位置上。这应该很好理解吧，\(a\) 是一个公差为 \(1\) 的等差数列，下标也是一个公差为 \(1\) 的等差数列，对应位置相减就相等了。

我们在输入 \(a_i\) 的时候减去 \(i\)，然后用滑动窗口维护每个区间内出现最多的元素次数即可。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,k,qq;
int a[N],f[N]; 
int l,r;
void solve(){
	memset(a,0,sizeof a);
	memset(f,0,sizeof f);
	cin>>n>>k>>qq;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	 	a[i]=a[i]-i;
	}
	multiset<int> q; 
	map<int,int> h;
	for(int i=1;i<=n;i++){
		int v=h[a[i]]++;
		if(q.find(v)!=q.end()){
			q.erase(q.find(v));
		}
		q.insert(v+1);
		if(i>=k){
			f[i]=*q.rbegin();
			int w=h[a[i-k+1]]--;
			q.insert(w-1);
			if(q.find(w)!=q.end()){
				q.erase(q.find(w));
			}
		}
	}
	while(qq--){
		cin>>l>>r;
		int ans=k-f[r];
		cout<<ans<<'\n';
	}
}
int main(){
	int t;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

也可以用莫队维护这个值：

#include<bits/stdc++.h>
using namespace std;
void solve(){
	int n,k,m;
	cin>>n>>k>>m;
	vector<int>a(n+1),bel(n+1);
	int tot=sqrt(n);
	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i]-=i;
		bel[i]=i/tot;
	}
	vector<vector<int>>q(m+1,vector<int>(3));
	for(int i=1;i<=m;i++){
		cin>>q[i][0]>>q[i][1];
		q[i][2]=i;
	}
	sort(q.begin()+1,q.end(),[&](auto &x,auto &y){
		if(bel[x[0]]!=bel[y[0]])return bel[x[0]]<bel[y[0]];
		if(bel[x[0]]&1) return x[1]<y[1];
		return x[1]>y[1];
	});
	vector<int> cnt(2*n+1,0);
	vector<int> sum(n+1,0);
	int mx=0;
	auto add=[&](int x){
		cnt[a[x]+n]++;
		sum[cnt[a[x]+n]]++;
		if(cnt[a[x]+n]>mx)mx=cnt[a[x]+n];
	};
	auto del=[&](int x){
		if(cnt[a[x]+n]==mx){
			if(sum[cnt[a[x]+n]]==1) mx--;
		}
		sum[cnt[a[x]+n]]--;
		cnt[a[x]+n]--;
	};
	vector<int>ans(m+1);
	int l=1,r=0;
	for(int i=1;i<=m;i++){
		while(q[i][0]<l) add(--l);
		while(q[i][1]>r) add(++r);
		while(q[i][0]>l) del(l++);
		while(q[i][1]<r) del(r--);
		ans[q[i][2]]=q[i][1]-q[i][0]+1-mx;
	}
	for(int i=1;i<=m;i++)cout<<ans[i]<<"\n";
}
int main(){
	int t;
	cin>>t;
	while(t--) solve();
	return 0;
}