“科大讯飞杯”第十七届同济大学程序设计预选赛暨高校网络友谊赛 H 时空栈

题目描述

https://ac.nowcoder.com/acm/contest/5477/H

简要题意：现在一个空栈和 $n$ 次操作，操作有三种：在时间 $t$ 入栈 $v$；在时间 $t$ 出栈；求时间 $t$ 的栈顶元素，需要注意的是每次查询操作，是相当于将之前操作按照给出的时间排序依次执行的结果，输入保证出入栈合法，且时间 $t$ 互不相同

$n\le 2\times 10^5$

Solution

我们以时间为下标建线段树，入栈看做 $+1$，出栈看做 $-1$，这样在查询时可以知道现在栈内有多少元素

仔细观察栈内元素的个数变化，不妨设查询时栈内元素个数为 $t$，能够发现栈顶元素的插入时间是最后一次栈内元素为 $t-1$ 的时间加一，这个东西可以用线段树维护，具体详见代码

#include <iostream>
#include <algorithm>
#define maxn 200010
using namespace std;

#define lc i << 1
#define rc i << 1 | 1
struct Seg {
    int v, add;
} T[maxn * 4];
inline void maintain(int i) { T[i].v = min(T[lc].v, T[rc].v); }

inline void Update(int i, int add) { T[i].v += add; T[i].add += add; } 

inline void pushdown(int i) {
    int &add = T[i].add; if (!add) return ;
    Update(lc, add); Update(rc, add);
    add = 0; 
}

void update(int i, int l, int r, int L, int R, int v) {
    if (l > R || r < L) return ;
    if (L <= l && r <= R) return Update(i, v);
    int m = l + r >> 1; pushdown(i);
    update(lc, l, m, L, R, v); update(rc, m + 1, r, L, R, v);
    maintain(i); 
}

int query(int i, int l, int r, int k) {
    if (l == r) return T[i].v;
    int m = l + r >> 1; pushdown(i);
    if (k <= m) return query(lc, l, m, k);
    else return query(rc, m + 1, r, k); 
}

int query(int i, int l, int r, int L, int R, int v) {
    if (l > R || r < L && T[i].v >= v) return 0;
    if (l == r) return T[i].v < v ? l : 0; pushdown(i); 
    int m = l + r >> 1, t = query(rc, m + 1, r, L, R, v);
    if (t) return t;
    else return query(lc, l, m, L, R, v);
}

int n, a[maxn];

struct Query {
    int opt, t, v;
} Q[maxn];

int b[maxn];
void init_hash() {
    for (int i = 1; i <= n; ++i) b[i] = Q[i].t;
    sort(b + 1, b + n + 1); int cnt = unique(b + 1, b + n + 1) - b - 1;
    for (int i = 1; i <= n; ++i) Q[i].t = lower_bound(b + 1, b + cnt + 1, Q[i].t) - b; 
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> Q[i].opt >> Q[i].t;
        if (Q[i].opt == 0) cin >> Q[i].v;
    } init_hash();
    for (int i = 1; i <= n; ++i) {
        if (Q[i].opt == 0) {
            update(1, 1, n, Q[i].t, n, 1);
            a[Q[i].t] = Q[i].v;
        }
        else if (Q[i].opt == 1)
            update(1, 1, n, Q[i].t, n, -1);
        else cout << a[query(1, 1, n, 1, Q[i].t, query(1, 1, n, Q[i].t)) + 1] << "\n";
    }
    return 0; 
}