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

发布于 2019-07-19  134 次阅读


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. 

题意:在比赛开始之前 有n个队伍排队 从1到n 每个队伍都有对应的分数 有个人很无聊 想找一个长度为m的区间 初始值 max=-1 count=0 如果遇到比max更大的数字 更新 并且 count+1
并且输入和输出要遵循题中所说的规律
直接贴代码了 多写点注释

#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;
}

愿风指引你的道路,愿你的刀刃永远锋利。