HDU6319 2018HDU多校第三场 1001 Problem A. Ascending Rating

题意略

coding出来其实很简单，按照题目要求填写数组，然后倒着搜维护一个单调队列就可以了，维护单调队列的时候要注意单调队列中元素数量等价于目标区间$$count_i$$的值，即$$count_i = q.size()$$
AC代码：

#include <iostream>
#include <queue>
#include <algorithm>
#include <array>

using namespace std;
using ll = long long;
const int maxn = 1e7 + 1e2;
array<int, maxn> a;
int n, m, k, P, Q, R, mod;
ll A, B;
deque<int> q;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        q.clear();
        cin >> n >> m >> k >> P >> Q >> R >> mod;
        for (int i = 1; i <= k; ++i)cin >> a[i];
        for (int i = k + 1; i <= n; ++i) {
            a[i] = (1ll * P * a[i - 1] + 1ll * Q * i + R) % mod;
        }
        A = B = 0;
        for (int i = n; i; --i) {
            while (!q.empty() && a[q.back()] <= a[i])q.pop_back();//维护单调队列
            q.push_back(i);//注意，这个队列是保证队尾元素最小的 所以要插入的值若比队尾元素大
                           //一定要去除对答案没有贡献的元素 这个是关键
            if (i + m - 1 <= n) {//当区间大小满足题意要求
                while (q.front() >= i + m) q.pop_front();//这里清除的是不满足当前所取区间范围的值
                A += i ^ a[q.front()];
                B += i ^ q.size();
            }
        }
        cout << A << " " << B << "\n";
    }
}