[51nod1952]栈

前言

题面传送门

这里讲的是有别于单调栈和单调队列的做法。

要想看这种做法的,请转至 yongshi的文章

题意

要求维护一个异常的栈。

$n$ 次操作,除了正常的栈顶插入删除外,还有一个栈尾插入的操作,每次操作后询问栈内元素最大值。

$n \le 10^7, 0 \le x \le 10^9$($x$ 表示插入的数)。

时限1.5s,输入由参数产生,输出答案对 $10^9 + 7$ 取模的值。

分析

显然只能 $\mathcal O(n)$。

考虑没有栈尾插入的时候怎么做。

不需要什么单调栈 + 普通栈,直接用一个栈记录前缀最大值就行了,删除就直接让栈顶指针前移一格。

现在加入了栈尾插入,直接这么搞行不通了。

但即使是这样也不能向单调队列单调栈屈服

正当我冥思苦的时候,旁边的 $\text{zls}$ 突然冒出一句:

另开一个普通栈放栈尾插入的不就行了?每次正常栈pop完了直接暴力把这个新开的栈一个个塞回原栈继续维护前缀最大值就可以了

这么暴力显然过不去啊

然而并不对。其实感性想一想,这样的复杂度貌似是对的…

均摊下来,每个元素最多只会被入新栈一次,入普通栈一次,出栈一次

也就是说,这样子操作的时间复杂度还是 $\mathcal O(n)$ 的

带了个 3 的常数,但实际上比 3 小很多(总共就 $10^7$ 个操作)

具体实现上,新栈因为没有删除操作而只有整体搬空,可以直接用一个全局变量记录新栈的全局最大值;

原栈和原来没有尾部插入一样,不需要记录原数据,直接只记录前缀最大值就可以了。

(不要像我这种 $\text{lese}$ 一样把新栈也搞成前缀最大值…调了半天)

这样子我们就可以以极低的代码,时间,思维复杂度解决这个题目了。

总比想破头去想单调队列 + 单调栈好

代码

指针可能不太友好,不过差不多啦- -凑合着看看吧

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
/**********************************************************
* Author : EndSaH
* Email : hjxhb1@gmail.com
* Created Time : 2019-03-11 12:45
* FileName : 1952.cpp
* Website : https://endsah.cf
* *******************************************************/

#include <cstdio>
#include <cctype>
#include <cassert>
#include <algorithm>

typedef long long LL;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define Debug(s) debug("The message in line %d, Function %s: %s\n", __LINE__, __FUNCTION__, s)
#define getchar() (ipos == iend and (iend = (ipos = _ibuf) + fread(_ibuf, 1, __bufsize, stdin), ipos == iend) ? EOF : *ipos++)
#define putchar(ch) (opos == oend ? fwrite(_obuf, 1, __bufsize, stdout), opos = _obuf : 0, *opos++ = (ch))
#define __bufsize (1 << 21)

char _ibuf[__bufsize], _obuf[__bufsize], _stk[20];
char *ipos = _ibuf, *iend = _ibuf, *opos = _obuf, *oend = _obuf + __bufsize, *stkpos = _stk;

struct END
{ ~END() { fwrite(_obuf, 1, opos - _obuf, stdout); } }
__;

inline int read()
{
register int x = 0;
register char ch;
while (!isdigit(ch = getchar()));
while (x = (x << 3) + (x << 1) + (ch & 15), isdigit(ch = getchar()));
return x;
}

template <typename _INT>
inline void write(_INT x)
{
while (*++stkpos = x % 10 ^ 48, x /= 10, x);
while (stkpos != _stk)
putchar(*stkpos--);
}

template <typename _Tp>
inline bool Chkmax(_Tp& x, const _Tp& y)
{ return x < y ? x = y, true : false; }

template <typename _Tp>
inline bool Chkmin(_Tp& x, const _Tp& y)
{ return x > y ? x = y, true : false; }

const int maxN = 1e7 + 2;
const int mod = 1e9 + 7;

int n, A, B, C, xi, a, aa, b, bb, MOD, ans, max;
int stk1[maxN], stk2[maxN], *pos1 = stk1, *pos2 = stk2;

inline void Mod(int& x)
{ x >= mod ? x -= mod : 0; }

inline void Getopt()
{
xi = ((LL)xi * aa + bb) % MOD;
if ((pos1 - stk1) + (pos2 - stk2) <= 1)
a = 0, b = xi;
else
{
int tmp = xi % (A + B + C);
if (tmp < A)
a = 0, b = xi;
else if (tmp < A + B)
a = 1, b = xi;
else
a = 2;
}
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("1952.in", "r", stdin);
freopen("1952.out", "w", stdout);
#endif
n = read(), A = read(), B = read(), C = read();
xi = read(), aa = read(), bb = read(), MOD = read();
for (register int i = 1; i <= n; ++i)
{
Getopt();
switch (a)
{
case 0 :
*++pos1 = b;
Chkmax(*pos1, *(pos1 - 1));
break;
case 1 :
Chkmax(max, *++pos2 = b);
break;
case 2 :
if (pos1 == stk1)
{
max = 0;
while (pos2 != stk2)
{
*++pos1 = *pos2--;
Chkmax(*pos1, *(pos1 - 1));
}
}
--pos1;
break;
default :
assert(false);
}
Mod(ans += std::max(*pos1, max));
}
write(ans);
return 0;
}

$\huge \text{Thanks for your consideration!}$