【XSY3330】地中海气候（思维）

题目让我们动态维护一个堆，有两种操作：加入一个数、询问并取出最大值。

比较巧妙的地方是这两种操作是轮流进行的。我们可以用桶来维护这个堆，顺便记录一下当前桶内的最大值。

然后加入一个数时，若它比桶内最大值大，那么它在下一次询问的答案必然是它，那么我们就无需加入桶内，直接记录一下即可。否则它比桶内最大值小，那么就把它加入桶内。

于是你发现桶的最大值是不会增大的，于是总时间复杂度为 \(O(nk)\)。

#include<bits/stdc++.h>

#define N 100010
#define ll long long

using namespace std;

inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^'0');
		ch=getchar();
	}
	return x*f;
}

int n,q,a[N];
int buc[N];

int main()
{
	n=read(),q=read();
	for(int i=1;i<=n;i++) a[i]=read();
	while(q--)
	{
		int p=read();
		int maxn=n;
		for(int i=1;i<=p;i++) buc[a[i]]++;
		ll sum[2]={0,0};
		bool now=0;
		int lst=0;
		for(int i=p+1;i<=n;i++)
		{
			if(lst) sum[now]+=lst;
			else
			{
				while(!buc[maxn]) maxn--;
				sum[now]+=maxn;
				buc[maxn]--;
			}
			if(a[i]>maxn) lst=a[i];
			else buc[a[i]]++,lst=0;
			now^=1;
		}
		for(int i=1;i<=p;i++)
		{
			if(lst) sum[now]+=lst;
			else
			{
				while(!buc[maxn]) maxn--;
				sum[now]+=maxn;
				buc[maxn]--;
			}
			lst=0;
			now^=1;
		}
		printf("%lld\n",sum[0]-sum[1]);
	}
	return 0;
}
/*
5 2
2 4 2 3 5
4 3
*/