【题解】CF2009G1

前言

  只会做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;
		}
	}
}