[2019宁夏网络赛-A] Maximum Element In A Stack

发表于 | 更新于 | 分类于 ，
本文字数： 17k

链接

\(\text{2019宁夏网络赛-A.Maximum Element In A Stack}\)

题意

  给你一个空的\(\text{stack}\)，你有两种操作，入栈一个数以及将栈顶数出栈，每次入栈操作后或者出栈操作后，你需要输出当前栈中的最大值，如果栈为空而当前操作为出栈，那么应该输出0。

  输入规格即数据范围：第一行一个\(\text{T(T<50)}\)，下面每行一组测试样例，包含七个整数\(n(1\leq n \leq 5\times\ 10^{6}),p,q,m(1\leq p,q,m\leq 10^{9}),SA,SB,SC(10^{4}\leq SA,SB,SC\leq 10^{6})\)，其中\(n\)是操作的数量，其中关于入栈出栈操作部分代码已给出，如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int n, p, q, m;
unsigned int SA, SB, SC;
unsigned int  rng61() {
    SA ^= SA << 16;
    SA ^= SA >> 5;
    SA ^= SA << 1;
    unsigned int t = SA; SA = SB;
    SB = SC;
    SC ^= t ^ SA;
    return SC;
}
void gen(){
    scanf("%d%d%d%d%u%u%u", &n, &p, &q, &m, &SA, &SB, &SC);
    for(int i = 1; i <= n; i++) {
        if(rng61() % (p + q) < p){
            PUSH(rng61() % m + 1);
        }
        else
            POP();
    }
}

  对于每个测试样例，输出一行Case #x: y，x代表第x个测试样例，y等于\(\oplus^n_{i=1} (i \cdot a_i)\)，\(a_i​\)是第\(i\)次操作后的最大值。

分析

  关键目标是求出，每次出栈入栈之后的最大值，如果没有出栈操作，仅仅只有入栈操作，那么我们需要一个res以及一个栈s1，在每次入栈元素x之后，使用它更新一下最大值res，但是这里出现了出栈的操作；

  那么考虑一个出栈操作前后的最大值变化，如果出栈元素不是最大值，那么最大值不变，如果出栈元素是最大值，那么出栈后最大值为没出栈前的次大值，那么我们考虑使用一个单调的栈\(s2\)（栈底到栈顶递增）模拟最大值变化，栈\(s1\)模拟入栈出栈操作；如果当前操作是入栈元素\(x\)，并且\(x\)大于等于栈顶元素，那么就让\(x\)同时入栈\(s1、s2\)，若小于，则让\(x\)入栈\(s1\)，如果当前操作是出栈操作，比较\(s1\)栈顶元素与\(s2\)栈顶元素，若相等，说明当前最大元素即为\(s1\)栈顶元素，那么同时让\(s1\)与\(s2\)栈顶元素出栈，不相等则，让\(s1\)栈顶元素出栈，当前最大值即为\(s2\)栈顶元素。

代码

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <map>

#define INF 0x7f7f7f7f
#define MAXN 16005
#define N 200005
#define P 2
#define MOD 99991

typedef long long ll;

namespace fastIO {
    //#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin), p1 == p2) ? EOF : *p1++)
    //char buf[(1 << 22)], *p1 = buf, *p2 = buf;
    inline int read() {
        char c = getchar(); int x = 0, f = 1;
        while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
        while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
        return x * f;
    }
}

using namespace fastIO;
using namespace std;

int t;

ll res,cnt;

unsigned int a[5000006], b[5000006];
ll i1, i2;
void PUSH(ll x) {
    cnt++;
    b[++i2] = x;
    if(x >= a[i1])
        a[++i1] = x;
    res ^= (cnt * a[i1]);
}
void POP() {
    cnt++;
    if(i2 >= 1) {
        if (b[i2] == a[i1])
            i2--, i1--;
        else i2--;
        res ^= (cnt * a[i1]);
    }
}

int n, p, q, m;
unsigned int SA, SB, SC;
unsigned int  rng61() {
    SA ^= SA << 16;
    SA ^= SA >> 5;
    SA ^= SA << 1;
    unsigned int t = SA; SA = SB;
    SB = SC;
    SC ^= t ^ SA;
    return SC;
}
void gen(){
    scanf("%d%d%d%d%u%u%u", &n, &p, &q, &m, &SA, &SB, &SC);
    for(int i = 1; i <= n; i++) {
        if(rng61() % (p + q) < p){
            PUSH(rng61() % m + 1);
        }
        else
            POP();
    }
}

int main() {
    scanf("%d", &t);
    for (int k = 1; k <= t; k++) {
        i1 = i2 = cnt = res = 0;
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        gen();
        printf("Case #%d: %lld\n", k, res);
    }
}