题意概述
给定一个$1$到$n$的全排列。有$m$次操作,每次操作将第$l$项到第$r$项之间的数按升序或降序排序。求所有操作完成后第$q$项的值。
数据范围:$1 \le n, m \le 10^5$。
算法分析
用set维护所有有序的区间,每个区间用一棵权值线段树来维护。这样就把排序操作变成了区间的分裂与合并(即线段树的分裂与合并)。
看起来线段树的复杂度很玄学,但可以大致证明一下:
初始时,线段树有$O(n\log n)$个节点。
分裂操作需要找到第$k$大的数,并把路径上的节点拆到两棵树上。一次分裂操作的时间复杂度为$O(\log n)$,新增节点数为$O(\log n)$。
合并操作每调用一次,都会删除一个节点。因此合并操作的总时间复杂度与最大点数相关,为$O((n+m)\log n)$。
由此得证。
代码
/* * Try to have as good a life as you can under the circumstances. */ #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; }