1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129
|
#include <algorithm> #include <cstdio> #include <cstring> #include <set>
static int const N = 100005; static int const NM = 5000000; int rt[N], top, buf[NM]; struct Interval { int l, r, ord; bool operator<(Interval const &a) const { return l < a.l; } }; std::set<Interval> st; struct SegmentTree { int ch[2], val, sum; } nd[NM];
void update(int rt) { nd[rt].sum = nd[nd[rt].ch[0]].sum + nd[rt].val + nd[nd[rt].ch[1]].sum; }
void insert(int &rt, int nl, int nr, int p) { if (!rt) nd[rt = buf[--top]] = nd[0]; if (nl == nr) { nd[rt].val = nd[rt].sum = 1; return; } int mid = nl + nr >> 1; if (p <= mid) insert(nd[rt].ch[0], nl, mid, p); else insert(nd[rt].ch[1], mid + 1, nr, p); update(rt); }
void merge(int &p, int &q) { if (!p || !q) { p = p + q, q = 0; return; } merge(nd[p].ch[0], nd[q].ch[0]), merge(nd[p].ch[1], nd[q].ch[1]); buf[top++] = q, q = 0, update(p); }
int split(int &rt, int k) { if (!rt || nd[rt].sum == k) return 0; if (!k) { int rec = rt; return rt = 0, rec; } if (nd[nd[rt].ch[0]].sum >= k) { int sp = buf[--top]; nd[sp].ch[0] = split(nd[rt].ch[0], k), nd[sp].ch[1] = nd[rt].ch[1], nd[rt].ch[1] = 0; return update(rt), update(sp), sp; } int sp = buf[--top]; nd[sp].ch[0] = 0, nd[sp].ch[1] = split(nd[rt].ch[1], k - nd[nd[rt].ch[0]].sum); return update(rt), update(sp), sp; }
int query(int rt, int nl, int nr, int k) { if (nl == nr) return nl; int mid = nl + nr >> 1; if (nd[nd[rt].ch[0]].sum >= k) return query(nd[rt].ch[0], nl, mid, k); else return query(nd[rt].ch[1], mid + 1, nr, k - nd[nd[rt].ch[0]].sum); }
int main() { for (int i = 1; i < NM; ++i) buf[top++] = i; int n, m, q; scanf("%d%d", &n, &m); for (int i = 1, t; i <= n; ++i) scanf("%d", &t), insert(rt[i], 1, n, t), st.insert((Interval){i, i, 0}); for (; m--;) { int op, l, r; scanf("%d%d%d", &op, &l, &r); std::set<Interval>::iterator L = st.upper_bound((Interval){l}), R = st.upper_bound((Interval){r}); Interval recl = *(--L), recr = *(--R); if (L->l < l) if (L->ord == 0) rt[l] = split(rt[L->l], l - L->l); else rt[l] = split(rt[L->l], L->r - l + 1), std::swap(rt[l], rt[L->l]); if (L != R) { st.erase(L++); for (; L != R; st.erase(L++)) merge(rt[l], rt[L->l]); if (r < R->r) if (R->ord == 0) rt[r + 1] = split(rt[R->l], r - R->l + 1); else rt[r + 1] = split(rt[R->l], R->r - r), std::swap(rt[r + 1], rt[R->l]); merge(rt[l], rt[R->l]); } else if (r < R->r) if (R->ord == 0) rt[r + 1] = split(rt[l], r - l + 1); else rt[r + 1] = split(rt[l], R->r - r), std::swap(rt[r + 1], rt[l]); st.erase(R), st.insert((Interval){l, r, op}); if (recl.l < l) st.insert((Interval){recl.l, l - 1, recl.ord}); if (r < recr.r) st.insert((Interval){r + 1, recr.r, recr.ord}); } scanf("%d", &q); for (std::set<Interval>::iterator it = st.begin(); it != st.end(); ++it) if (q <= nd[rt[it->l]].sum) { if (it->ord == 0) printf("%d\n", query(rt[it->l], 1, n, q)); else printf("%d\n", query(rt[it->l], 1, n, nd[rt[it->l]].sum - q + 1)); break; } else q -= nd[rt[it->l]].sum; return 0; }
|