HDU 6319 Problem A. Ascending Rating 【单调队列】

发表于 | 更新于 | 分类于

题目大意：

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

解题思路：

求区间最大值，我首先想到的是很经典的滑动窗口求区间最大值问题。
对于这个问题，因为还要求最大值的变化次数，所以直接利用滑窗的话变化次数不好求。
于是就有题解上说的考虑按照 r 从 n 到 m 的顺序倒着求出每个区间的答案了。此时所维护的值是从大到小的顺序(因为倒着求的嘛)，而对应的变化次数就是队列中元素的个数。
考虑到直接上deque挺耗时的，所以直接通过数组模拟就OK了。

【注意】
完善a数组时要注意精度问题。

Mycode：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAX = 1e7+5;

int T, n, m, k, P, Q, R, M, t, a[MAX], q[MAX], head, tail;
long long A, B;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        A = B = 0;
        scanf("%d%d%d%d%d%d%d",&n,&m,&k,&P,&Q,&R,&M);
        for(int i = 1; i <= k; ++i)
            scanf("%d",&a[i]);
        for(int i = k + 1; i <= n; ++i)
            a[i] = (1ll * P * a[i-1] + 1ll * Q * i + R) % M;

        head = 1, tail = 0;
        for(int i = n; i > 0; --i)
        {
            while(tail >= head && a[q[tail]] <= a[i])
                --tail;
            q[++tail] = i;
            if(i + m - 1 <= n)
            {
                while(q[head] - i >= m)
                    ++head;
                A += a[q[head]] ^ i;
                B += tail - head + 1 ^ i;
            }
        }

        printf("%lld %lld\n", A, B);
    }
    return 0;
}
Donate comment here
0%