题解 P6198 【[EER1]单调栈】
xht
2020-03-11 14:11:36
本来不想写这题题解的，结果发现题解区全是带 $\log$ 的屑做法......
贪心的过程很显然：
1. 若某个位置为 $-1$，把它设成前一个数的 $+1$ 即可。
2. 从区间 $[1,n]$ 开始递归处理。
3. 对于一个区间 $[l,r]$，用区间内最小的数将区间再划分为若干的个子区间。
4. 在最小的数所在的位置上，从右往左依次从小到大填数。
5. 从左往右依次处理每个子区间。
要证这个贪心，首先要证明这么做的正确性，然后证明没有更优解。
这两个证明都很 trivial，BF 的题解也有写，不是本文重点，略过。
本文的重点在于，BF 实现上面那个过程莫名其妙地用了一个 `set`。
可以线性为啥要带 $\log$，可以 `vector` 为啥要 `set`，屑（
这种题就应该出到 $10^7 \sim 10^8$ 卡死 $\log$（
没错，我写这个题解就是为了 diss BF 的（
另外，个人感觉这题也就是个 C，不知道为啥能放 E 去（
```cpp
const int N = 1e6 + 7;
int n, a[N], ans[N], t, cnt;
vi p[N], q;
void solve(int l, int r, int o) {
if (l > r) return;
for (int i = p[o].size() - 1; ~i; i--)
if (p[o][i] <= r) q.pb(p[o][i]);
else break;
while (q.size()) ans[q.back()] = ++t, q.pop_back();
solve(l, p[o].back() - 1, o + 1);
int x = p[o].back();
p[o].pop_back();
while (p[o].size() && p[o].back() <= r)
solve(x + 1, p[o].back() - 1, o + 1),
x = p[o].back(), p[o].pop_back();
solve(x + 1, r, o + 1);
}
int main() {
rd(n), rda(a, n);
for (int i = 1; i <= n; i++)
if (!~a[i]) a[i] = a[i-1] + 1;
for (int i = n; i; i--) p[a[i]].pb(i);
solve(1, n, 1);
for (int i = 1; i <= n; i++) print(ans[i], " \n"[i==n]);
return 0;
}
```