第十七届同济大学程序设计预选赛H

我们不妨将入栈操作看作在这个时间点加1，将出栈操作看作这个时间点-1。那么询问当前时间点的栈顶元素就是找到最大的后缀下标使得这个后缀的和是1即可。
我们通过线段树来维护区间后缀值，维护时，需要同时维护这个区间和以及后缀最大值。如果采用是自底向上的线段树即zkw线段树，那么query只要一个函数即可。如果采用常规的自顶向下的线段树，需要先找的合法的右端点，然后找到合法的区间用第二个query来查找答案。

代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stack>
using namespace std;

#define lson rt * 2
#define rson rt * 2 + 1

const int N = 2e5 + 100;

struct node {
    int sum, ma;
    node() {
        sum = ma = 0;
    }
    void set(int x) {
        sum = ma = x;
    }
}sa[N * 4];

node cal(node a, node b) {
    node c;
    c.sum = a.sum + b.sum;
    c.ma = max(a.ma + b.sum, b.ma);
    return c;
}

int n, tp;
int op[N], aa[N], bb[N], has[N], rev[N];

void insert(int id, int l, int r, int rt) {
    if (l == r) {
        int i = rev[l];
        if (op[i] == 0) sa[rt].set(1);
        else sa[rt].set(-1);
        return;
    }
    int m = (l + r) / 2;
    if (id <= m) insert(id, l, m, lson);
    else insert(id, m + 1, r, rson);
    sa[rt] = cal(sa[lson], sa[rson]);
}

int res;

void query(node x, int l, int r, int rt) {
    if (l == r) {
        res = bb[rev[l]];
        return;
    }
    int m = (l + r) / 2;
    if (cal(sa[rson], x).ma > 0) query(x, m + 1, r, rson);
    else query(cal(sa[rson], x), l, m, lson);
}

void query(int id, node &x, int l, int r, int rt) {
    if (l == r) {
        x = sa[rt];
        if (sa[rt].sum > 0) query(x, l, r, rt);
        return;
    }
    int m = (l + r) / 2;
    if (id <= m) {
        query(id, x, l, m, lson);
    }
    else {
        query(id, x, m + 1, r, rson);
        if (!res) {
            if (cal(sa[lson], x).ma > 0) {
                query(x, l, m, lson);
            }
            x = cal(sa[lson], x);
        }
    }
}

int main() {
    //freopen("0.txt", "r", stdin);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", op + i);
        if (op[i]) scanf("%d", aa + i);
        else scanf("%d%d", aa + i, bb + i);
        has[++tp] = i;
    }
    sort(has + 1, has + 1 + tp);
    tp = unique(has + 1, has + 1 + tp) - has;
    for (int i = 1; i <= n; i++) {
        aa[i] = lower_bound(has + 1, has + tp, aa[i]) - has;
        if (op[i] != 2) rev[aa[i]] = i;
    }
    for (int i = 1; i <= n; i++) {
        if (op[i] == 2) {
            res = 0;
            node x;
            query(aa[i], x, 1, tp, 1);
            printf("%d\n", res);
        }
        else insert(aa[i], 1, tp, 1);
    }
    return 0;
}