要求一个区间内的最大值和每次数过去最大值更新的次数,然后求每次的这个值异或 i 的总和。
这个序列一共有n个数,前k个直接给出来,从k+1到n个数用公式计算出来。
因为要最大值,所以就要用到单调队列,然后从后往前扫一遍然后每次维护递减的单调队列。
先把从n-m+1以后开始的数放进单调队列,这时候先不操作,然后剩下的数就是要异或相加的数,然后每次的队首元素就是这个区间内的最大值,这个队列里的元素个数,其实就是更新到最大值的逆过程,也就是最大值需要更新的次数。
#include<map>
#include<set>
#include<ctime>
#include<cmath>
#include<stack>
#include<queue>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define lowbit(x) (x & (-x))typedef unsigned long long int ull;
typedef long long int ll;
const double pi = 4.0*atan(1.0);
const int inf = 0x3f3f3f3f;
const int maxn = ;
const int maxm = ;
using namespace std;int T, tol;
int n, m;
ll a[maxn];
int que[maxn];void init() {
memset(a, , sizeof a);
}int main() {
scanf("%d", &T);
while(T--) {
int k;
int p, q, r, mod;
scanf("%d%d%d%d%d%d%d", &n, &m, &k, &p, &q, &r, &mod);
for(int i=; i<=k; i++) scanf("%lld", &a[i]);
for(int i=k+; i<=n; i++) a[i] = (1ll*p*a[i-] + 1ll*q*i + r) % mod;
int head, tail;
head = tail = ;
for(int i=n; i>n-m+; i--) {
while(head != tail && a[i] >= a[que[tail-]]) tail--;
que[tail++] = i;
}
/*
for(int j=head; j<tail; j++) printf("%d %d %lld\n", i, que[j], a[que[j]]);
printf("\n");
*/
ll ans1 = ;
ll ans2 = ;
for(int i=n-m+; i>=; i--) {
while(head != tail && a[i] >= a[que[tail-]]) tail--;
que[tail++] = i;
while(i + m - < que[head]) head++;
/*
for(int j=head; j<tail; j++) printf("%d %d %lld\n", i, que[j], a[que[j]]);
printf("\n");
*/
ans1 += (a[que[head]] ^ i);
ans2 += ((tail - head) ^ i);
}
printf("%lld %lld\n", ans1, ans2);
}
return ;
}