Description

有一個棧。每次告訴你已知在 \(p_i\) 時刻進行了某種操作，問在已知操作按順序結束后棧頂元素是什么。操作數 \(10^5\) 。

Solution

每次 push 就在 \([1,p]\) 區間加一， pop 就是區間減一。詢問就是最靠右的不為零的點。詳見代碼。

#include<bits/stdc++.h> using namespace std;template <class T> inline void read(T &x) {x = 0; static char ch = getchar(); for (; ch < '0' || ch > '9'; ch = getchar());for (; ch >= '0' && ch <= '9'; ch = getchar()) (x *= 10) += ch - '0'; }#define N 100001 #define rep(i, a, b) for (int i = a; i <= b; i++)int n, a[N], Max[N << 2], tag[N << 2];#define ls rt << 1 #define rs ls | 1 #define mid (l + r >> 1)inline void pushDown(int rt, int l, int r) {Max[ls] += tag[rt], tag[ls] += tag[rt];Max[rs] += tag[rt], tag[rs] += tag[rt];tag[rt] = 0; }void update(int rt, int l, int r, int L, int R, int v) {if (L <= l && r <= R) { Max[rt] += v, tag[rt] += v; return; }pushDown(rt, l, r);if (L <= mid) update(ls, l, mid, L, R, v);if (R > mid) update(rs, mid + 1, r, L, R, v);Max[rt] = max(Max[ls] , Max[rs]); }int query(int rt, int l, int r) {if (l == r) return l;pushDown(rt, l, r);if (Max[rs] > 0) return query(rs, mid + 1, r);else return query(ls, l, mid); }int main() {read(n);rep(QwQ, 1, n) {int p, op; read(p), read(op);if (op) read(a[p]), update(1, 1, n, 1, p, 1);else update(1, 1, n, 1, p, -1);printf("%d\n", Max[1] > 0 ? a[query(1, 1, n)] : -1);}return 0; }

轉載于:https://www.cnblogs.com/aziint/p/9181581.html

總結

以上是生活随笔為你收集整理的CodeForces - 760E Nikita and stack的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。