hexo-blog/source/_posts/oi/排序.md

---

title: 排序 tags:

• Segment Tree id: "2164" categories:
• - OI
  • Data Structure date: 2018-03-03 02:40:56 ---

题意概述

给定一个$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;
}