前言

  只会做G1 ,但尽量做到最好，除了一开始的排序的O(nlogn)，后续处理都是O(n)。可能会对G2和G3有一点点用处。

翻译

原题链接CF2009G1

思路

  直接处理等差数列不方便，但这个等差数列性质特殊，即公差为1。所以在一个等差数列中，$a[i]-i$就成了常数列。为了避免出现负数，我们将$a[i]$更改为$a[i]+n-i$，然后问题转化为将这个长度为$k$的数列转变为常数列的最小操作次数，易知等价于 $k-$众数 的数量。

  我们使用滑动窗口，维护所有值的数量，数量的降序映射数组，和降序数组中数量相同的区间的左右边界。各种映射非常复杂，调了好久，下面举个例子：

  现在数组为$1,1,2,2,1,4,2$
  数量数组为$3,3,0,1$
  降序数组为$1,2,4,3$
  边界为：$[1,2],[3,3],[4,4]$

  要维护这么多东西的目的就是让窗口滑动时，新增数据和删除数据的维护代价为O(1)。这是因为每次改变时，一个值对应的数量只会$+1$或$-1$。假如数量由$3$变成了$4$，那么交换自己和$3$的左边界，然后调整一下$3$和$4$的边界即可。

  最后，每次的答案就是数量数组第一个中对应的值。

代码

  尽量注释了，真太难说清楚了。把我注释的调试代码复原更好理解。

#include<bits/stdc++.h>
#define N 200005
#define int long long
using namespace std;
int n, k, q, a[N];
// cnt[值] =  值的数量 
// id[i] = cnt中数量第i多的值 
// re_id[值] = 这个值是第几多的 
// l[数量], r[数量] = 同样数量在id中的边界 
int cnt[2*N], id[2*N], re_id[2*N], ans[N];
int l[2*N], r[2*N];   // 每一种数量在id中的左右边界 
bool cmp(int x, int y) {return cnt[x] > cnt[y];
}
signed main() {int t; cin>>t;while(t--) {cin>>n>>k>>q;for(int i=0;i<=2*n;i++) {cnt[i] = 0;id[i] = i;}for(int i=1;i<=n;i++) {cin>>a[i];a[i] = a[i] + n - i;}
//		cout<<"a: "; for(int j=1;j<=n;j++) cout<<a[j]<<' '; cout<<endl;for(int i=1;i<=k;i++) {     // 初始化数量数组 cnt[a[i]]++;}sort(id+1, id+2*n+1, cmp);  // 初始化有序化数组id for(int i=0;i<=2*n;i++) re_id[id[i]] = i;   // 初始化re_id ans[k] = cnt[id[1]];for(int i=0;i<=2*n;i++) l[i] = r[i] = -1;   // 初始化l, r for(int i=1;i<=2*n;i++) {    // 初始化边界维护数组 if(cnt[id[i]] != cnt[id[i-1]]) {l[cnt[id[i]]] = i;r[cnt[id[i]]] = i;} else {r[cnt[id[i]]] = i;}} for(int i=k+1;i<=n;i++) {
//			cout<<endl;
//			cout<<"a_now: "; for(int j=i-k;j<=i-1;j++) cout<<a[j]<<' '; cout<<endl;
//			cout<<"cnt: "; for(int j=1;j<=2*n;j++) cout<<cnt[j]<<' '; cout<<endl;
//			cout<<"id: "; for(int j=1;j<=2*n;j++) cout<<id[j]<<' '; cout<<endl;
//			cout<<"re_id: "; for(int j=1;j<=2*n;j++) cout<<re_id[j]<<' '; cout<<endl;
//			cout<<"cnt[id]: "; for(int j=1;j<=2*n;j++) cout<<cnt[id[j]]<<' '; cout<<endl;
//			cout<<"l: "; for(int j=0;j<=2*n;j++) cout<<l[j]<<' '; cout<<endl;
//			cout<<"r: "; for(int j=0;j<=2*n;j++) cout<<r[j]<<' '; cout<<endl;
//			cout<<"ans: "<<ans[i-1]<<endl;int now = a[i];   // 当前值 int cnt_now = cnt[now];    // 当前数量 int tl = l[cnt_now], id_tl = id[tl];  // 边界，边界对应的值swap(id[tl], id[re_id[now]]);re_id[id_tl] = re_id[now];re_id[now] = tl;if(l[cnt_now] == r[cnt_now]) {l[cnt_now] = r[cnt_now] = -1;} else {l[cnt_now] ++;}if(r[cnt_now+1] == -1) {l[cnt_now+1] = r[cnt_now+1] = tl;} else {r[cnt_now+1] ++;}cnt[now] ++;now = a[i-k];  cnt_now = cnt[now];int tr = r[cnt_now], id_tr = id[tr];swap(id[tr], id[re_id[now]]);re_id[id_tr] = re_id[now];re_id[now] = tr;if(l[cnt_now] == r[cnt_now]) {l[cnt_now] = r[cnt_now] = -1;} else {r[cnt_now] --;}if(l[cnt_now-1] == -1) {l[cnt_now-1] = r[cnt_now-1] = tr;} else {l[cnt_now-1] --;}cnt[now] --;ans[i] = cnt[id[1]];} 
//		cout<<endl;
//		cout<<"a_now: "; for(int j=n-k+1;j<=n;j++) cout<<a[j]<<' '; cout<<endl;
//		cout<<"cnt: "; for(int j=1;j<=2*n;j++) cout<<cnt[j]<<' '; cout<<endl;
//		cout<<"id: "; for(int j=1;j<=2*n;j++) cout<<id[j]<<' '; cout<<endl;
//		cout<<"re_id: "; for(int j=1;j<=2*n;j++) cout<<re_id[j]<<' '; cout<<endl;
//		cout<<"cnt[id]: "; for(int j=1;j<=2*n;j++) cout<<cnt[id[j]]<<' '; cout<<endl;
//		cout<<"l: "; for(int j=0;j<=2*n;j++) cout<<l[j]<<' '; cout<<endl;
//		cout<<"r: "; for(int j=0;j<=2*n;j++) cout<<r[j]<<' '; cout<<endl;
//		cout<<"ans: "<<ans[n]<<endl;for(int d=1;d<=q;d++){int L, R; cin>>L>>R;R = L+k-1;cout<<k - ans[R]<<endl;}}
}