div4 971 G1. Yunli’s Subarray Queries (easy version)
q次询问,问区间[l,r]最少修改几个数使得区间[l,r]自然数连续(G1为简单版本,区间长度定为k)
首先有一个trick,要使得自然数连续,只要分别让他们减去i(i从1到n),如果数相等,则表示它们处于自然数连续的相应位置
==>
题目转化为求区间相等的数的个数最大值,再用k减去其即可
滑动窗口,需要始终维护区间相等的数的个数最大值这一信息
如何维护呢？
一开始想自定义优先队列，优先个数最大的放在队头，但是试验了好多次，包括之前有道题目也试验过，发现不可行，如果想要自定义优先队列的话，那么自定义比较的信息必须是不变的，一旦变动，输出的信息奇奇怪怪，摸不着规律，比如说自定义出现次数大的优先
struct cmp{bool operator()(int a,int b){return cnt[a]<cnt[b];} };那么cnt[a]和cnt[b]的值必须始终不变，这是通过多次试错发现的
维护信息的话有一个trick 首先每个数出现的次数肯定是需要的,即mp[a[i]]++ 然后我们反过来存一下,定义map<int,set<int>>cnt cnt[mp[a[i]].insert(a[i]) 也就是说对于出现的次数cnt,我们存了有哪些数出现的次数为cnt这样信息就很好维护了 比如说如果a[i]的次数变动了,比如说从2变为3,那么cnt[2].erase(a[i]),如果cnt[2].size()变为0了,说明次数为2的没有了 cnt[3].insert(a[i]),而次数为3的多了一个a[i] 另外,再用一个set专门存次数,并降序,那么很容易获取相等的个数最大值
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=2e5+10;
int a[N];
int ans[N];
int n,k,q;
void solve() {cin>>n>>k>>q;map<int,int>mp;map<int,set<int>>cnt;set<int,greater<int>>s;for(int i=1;i<=n;i++){cin>>a[i];a[i]-=i;}for(int i=1;i<=k;i++) mp[a[i]]++;for(auto v:mp){cnt[v.second].insert(v.first);s.insert(v.second);}ans[1]=*s.begin();for(int i=k+1;i<=n;i++){if(a[i]!=a[i-k]){//加上a[i]int tot=mp[a[i]];cnt[tot].erase(a[i]);if(!cnt[tot].size()) s.erase(tot);mp[a[i]]++;cnt[mp[a[i]]].insert(a[i]);s.insert(mp[a[i]]);//减去a[i-k]tot=mp[a[i-k]];cnt[tot].erase(a[i-k]);if(!cnt[tot].size()) s.erase(tot);mp[a[i-k]]--;cnt[mp[a[i-k]]].insert(a[i-k]);s.insert(mp[a[i-k]]);}ans[i-k+1]=*s.begin();}
// for(int i=1;i+k-1<=n;i++) cout<<ans[i]<<' ';
// cout<<endl;while(q--){int l,r;cin>>l>>r;cout<<k-ans[l]<<endl;}
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--) {solve();}return 0;
}