题目：传送门
题意
思路
先对时间 t 离散化，开线段树维护，对于入栈操作，我们对区间 [ t[i] , n ] 加 1，出栈操作则是减 1，线段树维护一个区间最小值。
对于查询操作，我们通过线段树可以很快的知道，当前时间点 t[i] 对应的栈的元素个数 x，然后， 我们要查询在 t[ i ] 时间前最后一个小于 x 的时间点 T，此时对应的栈的元素个数必定等于 x - 1,且 T + 1 时间点对应的操作必定是入栈操作，此时栈的元素个数为 x，此时的栈即为我们查询的时间点 t[ i ] 对应的栈，那么答案就是此时入栈的数。
#include <bits/stdc++.h> #define LL long long #define ULL unsigned long long #define UI unsigned int #define mem(i, j) memset(i, j, sizeof(i)) #define rep(i, j, k) for(int i = j; i <= k; i++) #define dep(i, j, k) for(int i = k; i >= j; i--) #define pb push_back #define make make_pair #define INF 0x3f3f3f3f #define inf LLONG_MAX #define PI acos(-1) #define fir first #define sec second #define lb(x) ((x) & (-(x))) #define dbg(x) cout<<#x<<" = "<<x<<endl; using namespace std; const int N = 1e6 + 5; struct note { int mi, lz; }t[N]; int Time[N], tmp[N], val[N], op[N]; int real_val[N]; void push_down(int rt) { if(t[rt].lz) { t[rt << 1].mi += t[rt].lz; t[rt << 1 | 1].mi += t[rt].lz; t[rt << 1].lz += t[rt].lz; t[rt << 1 | 1].lz += t[rt].lz; t[rt].lz = 0; } } void update(int rt, int l, int r, int L, int R, int V) { /// 区间更新 if(L <= l && r <= R) { t[rt].mi += V; t[rt].lz += V; return ; } push_down(rt); int mid = (l + r) >> 1; if(L <= mid) update(rt << 1, l, mid, L, R, V); if(R > mid) update(rt << 1 | 1, mid + 1, r, L, R, V); t[rt].mi = min(t[rt << 1].mi, t[rt << 1 | 1].mi); } int query1(int rt, int l, int r, int pos) { /// 单点查询 if(l == r && l == pos) return t[rt].mi; push_down(rt); int mid = (l + r) >> 1; if(pos <= mid) return query1(rt << 1, l, mid, pos); else return query1(rt << 1 | 1, mid + 1, r, pos); } int query2(int rt, int l, int r, int pos, int limit) { /// 找区间[l,r]内在点 pos 前最后一个小于 limit 的坐标 if(l == r) { if(t[rt].mi < limit) return l; return 0; } push_down(rt); int mid = (l + r) >> 1; int ans = 0; if(pos > mid && t[rt << 1 | 1].mi < limit) ans = query2(rt << 1 | 1, mid + 1, r, pos, limit); /// 先找右半区间 if(ans) return ans; /// 找到了就直接返回 return query2(rt << 1, l, mid, pos, limit); /// 找不到再去左半区间找 } int main() { int n; scanf("%d", &n); rep(i, 1, n) { scanf("%d %d", &op[i], &Time[i]); if(op[i] == 0) scanf("%d", &val[i]); tmp[i] = Time[i]; } sort(tmp + 1, tmp + 1 + n); rep(i, 1, n) { Time[i] = lower_bound(tmp + 1, tmp + 1 + n, Time[i]) - tmp; /// 离散化 real_val[Time[i]] = val[i]; } rep(i, 1, n) { if(op[i] == 0) update(1, 1, n, Time[i], n, 1); /// 区间更新 Time[i] ~ n 区间加 1 else if(op[i] == 1) update(1, 1, n, Time[i], n, -1); /// 区间更新 Time[i] ~ n 区间减 1 else { int limit = query1(1, 1, n, Time[i]); /// 先查询时间点 Time[i] 对应的栈的元素个数 int Time_Point = query2(1, 1, n, Time[i], limit); /// 查询区间 1 ~ Time[i] 最后一个栈的元素个数小于 limit 的时间点 int ans = real_val[Time_Point + 1]; /// Time_Point + 1 入栈的元素就是答案 printf("%d ", ans); } } return 0; }