题解：CF2009G1 Yunlis 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;
}