STL大法好啊

题意

给定一个长度为$N$的序列$A$，对于每个$1\leq i\leq N-M+1$，求出以$i$为起点的连续$M$个数中最小的$K$个数的和。

思路

连续的两次询问中，只有删除一个数，添加一个数的区别，我们可不可以用这个特性来节省时间呢？

考虑开一个multiset，每次添加进来一个新的数，将他的位置与原先第$K$个数的位置比较，若新的数小，则替换原先的末尾，再检查即将删去的数的位置是否比第$K$个数小，再更新答案即可。

AC代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int n,m,k,ans,a[N];
multiset<int>s;
signed main()
{
	scanf("%lld%lld%lld",&n,&m,&k);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	for(int i=1;i<=m;i++)s.insert(a[i]);
	auto id=s.begin();
	for(int i=1;i<=k;i++,id++)ans+=*id;
	printf("%lld ",ans);id--;
	for(int i=m+1;i<=n;i++)
	{
		s.insert(a[i]);
		if(a[i]<*id)
		{
			ans+=a[i]-*id;
			id--;
		}
		if(a[i-m]<=*id)ans+=*(++id)-a[i-m];
		s.erase(a[i-m]);
		printf("%lld ",ans);
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int n,m,k,ans,a[N];
multiset<int> ms;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=m;i++)
		ms.insert(a[i]);
	multiset<int>::iterator it=ms.begin();
	for(int i=1;i<=k;i++,it++)
		ans+=*it;
	cout<<ans<<' ';
	it--;
	for(int i=m+1;i<=n;i++){
		ms.insert(a[i]);
		if(a[i]<*it){
			ans+=a[i]-*it;
			it--;
		}
		if(a[i-m]<=*it)
			ans=ans-a[i-m]+*(++it);
		ms.erase(a[i-m]);
		cout<<ans<<' ';
	}
	return 0;
}