【单调栈】hdu 6319 杭电多校Problem A. Ascending Rating

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

从后往前更新,维护一个递减单调栈(队列)

最近很多题都是单调栈。。。

#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<algorithm>
#include<queue>
#include<iostream>
//#include<deque>
using namespace std;
const int maxn = 1e7 + ;
int n, m, k, P, Q, R, MOD,T;
int a[maxn];
#define rep(i,t,n) for(int i =(t);i<=(n);++i)
#define per(i,n,t) for(int i =(n);i>=(t);--i)
#define mmm(a,b) memset(a,b,sizeof(a)) int main() {
scanf("%d", &T);
while (T--) {
deque<int> que;
long long A = , B = ,cnt=,mx=-; scanf("%d%d%d%d%d%d%d", &n, &m, &k, &P, &Q, &R, &MOD);
rep(i,,k)scanf("%d", &a[i]);
rep(i,k+,n)a[i] = (1LL * P*a[i - ] + 1LL * Q*i + R) % MOD;
per(i, n,) {
while (!que.empty() && que.back() <= a[i])que.pop_back();
que.push_back(a[i]);
if (i <= n - m + ) {
if (a[i + m ] == que.front())que.pop_front();
A += i ^ que.front();
B += i ^ (que.size());
}
} printf("%lld %lld\n", A, B);
}
cin >> n;
}
上一篇:[原创]阿里云RocketMQ踩过的哪些坑


下一篇:《C++程序设计教程——给予Visual Studio 2008》读书笔记3章