01/3
19:54
OI

[HEOI2016/TJOI2016]排序 [线段树合并分裂]

[HEOI2016/TJOI2016]排序

今日见高一要学线段树分裂,发现自己没写过,大惊,来补了一下这个题。。。

其实这题很水的,只不过线段树分裂当板子用,专门记一下。。。

维护权值线段树,把一段区间都塞进权值线段树当作排好了。

那么用set维护线段树的根,操作一段区间的时候,把涉及到的一段取出来就好了。取出来合并涉及到线段树合并和分裂的操作。

其实线段树分裂就是找k大,同时新建一棵线段树,把前k大放进新线段树里,并且在旧线段树上删除这部分。

#include <bits/stdc++.h>

using std::cerr;
using std::endl;

inline int rd() {
  int a = 1, b = 0; char c = getchar();
  while (!isdigit(c)) a = c == '-' ? 0 : 1, c = getchar();
  while (isdigit(c)) b = b * 10 + c - '0', c = getchar();
  return a ? b : -b;
}

const int N = 1e5 + 233;

int n, m, Q;

struct Node {
  int l, r, root, op;
};

bool operator<(const Node &a, const Node &b) {
  return a.r < b.r;
}

std::set<Node> set;

struct SegTree {
  int ls, rs, sum;
} seg[N * 30];
int stk[N * 30], top;

inline int new_node() {
  int x = stk[top--];
  seg[x].ls = seg[x].rs = seg[x].sum = 0;
  return x;
}

inline void remove(int p) {
  stk[++top] = p;
}

void insert(int &p, int x, int L, int R) {
  if (!p) p = new_node();
  ++seg[p].sum;
  if (L == R) return;
  int mid = (L + R) >> 1;
  if (x <= mid) insert(seg[p].ls, x, L, mid);
  else insert(seg[p].rs, x, mid + 1, R);
}

int merge(int x, int y) {
  if (!x || !y) return x + y;
  int z = new_node();
  seg[z].ls = merge(seg[x].ls, seg[y].ls);
  seg[z].rs = merge(seg[x].rs, seg[y].rs);
  seg[z].sum = seg[x].sum + seg[y].sum;
  remove(x), remove(y);
  return z;
}

int split(int p, int x, int L, int R) {
  if (!p) return 0;
  int q = new_node();
  seg[q].sum += x; seg[p].sum -= x;
  if (L == R) return q;
  int mid = (L + R) >> 1, s = seg[seg[p].ls].sum;
  if (x < s) seg[q].ls = split(seg[p].ls, x, L, mid);
  else {
    seg[q].ls = seg[p].ls, seg[p].ls = 0;
    seg[q].rs = split(seg[p].rs, x - s, mid + 1, R);
  }
  return q;
}

int get_kth(int p, int x, int L, int R) {
  if (L == R) return L;
  int mid = (L + R) >> 1, s = seg[seg[p].ls].sum;
  if (s >= x) return get_kth(seg[p].ls, x, L, mid);
  else return get_kth(seg[p].rs, x - s, mid + 1, R);
}

inline int seq_split(int l, int r) {
  std::set<Node>::iterator it = set.lower_bound({0, l, 0, 0});
  if (it->l != l) {
    Node tmp = *it;
    set.erase(it);
    if (!tmp.op) {
      int root = split(tmp.root, l - tmp.l, 1, n);
      set.insert({ tmp.l, l - 1, root, 0 });
      set.insert({ l, tmp.r, tmp.root, 0 });
    } else {
      int root = split(tmp.root, tmp.r - l + 1, 1, n);
      set.insert({ tmp.l, l - 1, tmp.root, 1 });
      set.insert({ l, tmp.r, root, 1 });
    }
  }
  it = set.lower_bound({ 0, r, 0, 0 });
  if (it->r != r) {
    Node tmp = *it;
    set.erase(it);
    if (!tmp.op) {
      int root = split(tmp.root, r - tmp.l + 1, 1, n);
      set.insert({ tmp.l, r, root, 0 });
      set.insert({ r + 1, tmp.r, tmp.root, 0 });
    } else {
      int root = split(tmp.root, tmp.r - r, 1, n);
      set.insert({ tmp.l, r, tmp.root, 1 });
      set.insert({ r + 1, tmp.r, root, 1 });
    }
  }
  int ret = 0;
  while (true) {
    it = set.lower_bound({ 0, l, 0, 0 });
    if (it == set.end() || it->l > r)
      break;
    Node tmp = *it;
    set.erase(tmp);
    ret = merge(ret, tmp.root);
  }
  return ret;
}

int main() {
  // freopen("data", "r", stdin);
  n = rd(), m = rd();
  for (int i = 0; i < N * 30 - 1; ++i)
    stk[++top] = i;
  for (int i = 1; i <= n; ++i) {
    int x = rd(), root = 0;
    insert(root, x, 1, n);
    set.insert({ i, i, root, 0 });
  }
  while (m--) {
    int op = rd(), x = rd(), y = rd(), root = seq_split(x, y);
    set.insert({ x, y, root, op });
  }
  Q = rd();
  int root = seq_split(Q, Q);
  printf("%d\n", get_kth(root, 1, 1, n));
  return 0;
}