hdu6319---2018 Multi-University Training Contest 3 ---Problem A. Ascending Rating【单调队列】

题意：

给定一个序列a[1.....n]，对于每个长度为m的子区间，求出区间a的最大值以及从左往右扫描该区间时a的最大值变化次数。

思路：

按照平从m到n的顺序用个单调队列就可以算出子区间的最大值，

但是按照r从m到n的顺序很难求出变化次数，不如我们反着顺序过来求，按照递增，来写单调队列，队列中元素的个数就是最大值的变化次数。

队列中存的元素是以数组下标来进行存的。

#include<bits/stdc++.h>
#define maxn 70000005
#define ll long long
using namespace std;
int que[maxn],head, rear, maxx[maxn], sum[maxn];
int arr[maxn];
int n, m, k, p, q, r, mod;

void getmax(int a, int b) {//求最大值 
	rear = 1, head = 1;
	for(int i = 1; i <= a; i++) {
		while(head < rear &&arr[que[rear-1]] <= arr[i]) {
			rear--;
		}
		que[rear++] = i;
		if(i < b){
			continue;
		}
		while(que[head] < i-b+1){
			head++;
		}
		maxx[i] = arr[que[head]];
//		printf("%d\n",maxx[i]);
	}

}

void getsum(int a, int b) {//求变化次数 
	rear = 1, head = 1;
	for(int i = a; i >= 1; i--){
		while(rear > head && arr[que[rear-1]] <= arr[i]){
			rear--;
		}
		que[rear++] = i;
		if(i > a-b+1){
			continue;
		}
		while(que[head] > i+b-1){
			head++;
		}
		sum[i] = rear-head;
	}
}


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", &arr[i]);
		}
		for(int i = k+1; i <= n; i++) {
			arr[i] = ((ll)p%mod*arr[i-1]%mod+(ll)q%mod*i%mod+r%mod)%mod;
//这里的取模要小心，p和arr[i]即便模过，再相乘也可能会爆int，所以要先把p变为ll类型 
		}
		getmax(n, m);
		getsum(n, m);
		ll a = 0, b = 0;
		for(int i = 1; i <= n-m+1; i++){
			b = b +(sum[i]^i);
			a = a + (maxx[i+m-1]^i);
//			printf("%d\n",maxx[i+m-1]^i);
		}
		printf("%lld %lld\n",a,b);
	}
	return 0;
}