# [单调队列]hdu-6319-Ascending Rating

http://acm.hdu.edu.cn/showproblem.php?pid=6319

Before the start of contest, there are n ICPC contestants waiting in a long queue. They are labeled by 1 to n from left to right. It can be easily found that the i-th contestant's QodeForces rating is ai.
Little Q, the coach of Quailty Normal University, is bored to just watch them waiting in the queue. He starts to compare the rating of the contestants. He will pick a continous interval with length m, say [l,l+m−1], and then inspect each contestant from left to right. Initially, he will write down two numbers maxrating=−1 and count=0. Everytime he meets a contestant k with strictly higher rating than maxrating, he will change gmaxrating to ak and count to count+1.
Little T is also a coach waiting for the contest. He knows Little Q is not good at counting, so he is wondering what are the correct final value of maxrating and count. Please write a program to figure out the answer.

#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<ctime>
#include<map>
#include<stack>
#include<set>
#include<cstring>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 1e7 + 7;
const int eps = 1e-7;

int arr[maxn];//存原始数据
int qe[maxn];//模拟队列

int main()
{
ios::sync_with_stdio(0);
int t, n, m, k, p, q, r, mod;
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", &arr[i]);
}
for (int i = k + 1; i <= n; i++) {
arr[i] = (1ll * p * arr[i - 1] + 1ll * q * i + r) % mod;//k-n之间的数字用题中给的公式推出（不是重点
}
int s = 0, t = 0;//头尾
ll ansa = 0, ansb = 0;
for (int i = n; i >= 1; i--) {
while (s < t && arr[qe[t - 1]] <= arr[i]) t--;//队列不为空 且 当前元素大于队尾元素 弹出元素
qe[t++] = i;//该元素标号入队
if (i <= n - m + 1) {
ansa += (i ^ arr[qe[s]]);//队头元素最大 维护一个单调递减队列
ansb += (i ^ (t - s));//count
if (qe[s] == i + m - 1) {//队列长度等于m时
s++;//队首元素出队
}
}
}
printf("%lld %lld\n", ansa, ansb);
}
return 0;
}