题意有点麻烦就懒得说了……简单来说,用单调队列维护出数字被删去的顺序就好了。

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e7+7;
long long A,B;
int a[maxn];
int maxrating[maxn],Count[maxn];
int Q[maxn],qtop,qtail;
int n,m,k,p,q,r,MOD;

int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d%d%d%d%d%d",&n,&m,&k,&p,&q,&r,&MOD);
		for(int i=1;i<=k;i++) scanf("%d",&a[i]);
		for(int i=k+1;i<=n;i++)a[i]=((long long)p*a[i-1]+(long long)q*i+r)%MOD;
		A=0,B=0;
		qtop=qtail=0;
		for (int i=n;i>n-m+1;i--) if (a[i])
		{
			while (qtop < qtail && a[Q[qtail-1]] <= a[i]) qtail--;
			Q[qtail++]=i;
		}
		for (int i=n-m+1;i>=1;i--)
		{
			if (Q[qtop] == i+m) qtop++;
			if (a[i])
			{
				while (qtop < qtail && a[Q[qtail-1]] <= a[i]) qtail--;
				Q[qtail++]=i;
			}
			maxrating[i]=a[Q[qtop]];
			Count[i]=qtail-qtop;
		}
		for (int i=1;i<=n-m+1;i++)
			A+=maxrating[i]^i,B+=Count[i]^i;
		printf("%lld %lld\n",A,B);
	}
	return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注