本文最后更新于 2325 天前,其中的信息可能已经有所发展或是发生改变。
内容纲要
题意略
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";
}
}