主席树

静态区间第 $k$ 小

Luogu-P3834

struct Tree {
  int cnt;
  vector<int> su, ls, rs;
  Tree(int n): cnt(0) {
    n = (n + 1) << 5;
    su = ls = rs = vector<int>(n);
  };
  int build(int l, int r) {
    ++cnt;
    su[cnt] = 0;
    int mid = (l + r) >> 1;
    if (l < r) {
      ls[cnt] = build(l, mid), rs[cnt] = build(mid + 1, r);
    }
    return cnt;
  }
  int update(int pre, int l, int r, int x) {
    int rt = ++cnt;
    ls[rt] = ls[pre];
    rs[rt] = rs[pre];
    su[rt] = su[pre] + 1;
    if (l < r) {
      int mid = (l + r) >> 1;
      if (x <= mid) {
        ls[rt] = update(ls[pre], l, mid, x);
      } else {
        rs[rt] = update(rs[pre], mid + 1, r, x);
      }
    }
    return rt;
  }
  int query(int a, int b, int l, int r, int k) {
    if (l >= r) {
      return l;
    }
    int t = su[ls[b]] - su[ls[a]];
    int mid = (l + r) >> 1;
    if (t >= k) {
      return query(ls[a], ls[b], l, mid, k);
    } else {
      return query(rs[a], rs[b], mid + 1, r, k - t);
    }
  }
};

void solve() {
  int n, q;
  cin >> n >> q;
  vector<int> a(n), rt(n + 1);
  Tree tr(n);
  for (auto &i : a) {
    cin >> i;
  }
  auto b = a;
  sort(b.begin(), b.end());
  b.erase(unique(b.begin(), b.end()), b.end());
  rt[0] = tr.build(1, b.size());
  auto getId = [&](int x) {
    return lower_bound(b.begin(), b.end(), x) - b.begin();
  };
  for (int i = 1; i <= n; ++i) {
    rt[i] = tr.update(rt[i - 1], 1, b.size(), getId(a[i - 1]) + 1);
  }
  while (q--) {
    int l, r, k;
    cin >> l >> r >> k;
    int pos = tr.query(rt[l - 1], rt[r], 1, b.size(), k);
    cout << b[pos - 1] << endl;
  }
}

可持久化数组

Luogu-P3919

struct Tree {
  int cnt;
  vector<int> su, ls, rs, a;

  Tree(int n): cnt(0) {
    n = (n + 1) << 5;
    su = ls = rs = a = vector<int>(n);
  };

  int build(int l, int r) {
    int rt = ++cnt;
    if (l == r) {
      su[rt] = a[l];
      return rt;
    }
    int mid = (l + r) >> 1;
    ls[rt] = build(l, mid);
    rs[rt] = build(mid + 1, r);
    return rt;
  }

  int modify(int pre, int l, int r, int x, int u) {
    int rt = ++cnt;
    ls[rt] = ls[pre];
    rs[rt] = rs[pre];
    su[rt] = su[pre];
    if (l == r) {
      su[rt] = x;
      return rt;
    }
    int mid = (l + r) >> 1;
    if (u <= mid) {
      ls[rt] = modify(ls[pre], l, mid, x, u);
    }
    if (u > mid) {
      rs[rt] = modify(rs[pre], mid + 1, r, x, u);
    }
    return rt;
  }

  int query(int rt, int l, int r, int u) {
    if (l == r) {
      return su[rt];
    }
    int mid = (l + r) >> 1;
    if (u <= mid) {
      return query(ls[rt], l, mid, u);
    } else {
      return query(rs[rt], mid + 1, r, u);
    }
  }
};

void solve() {
  int n, q;
  cin >> n >> q;
  vector<int> rt(q + 1);
  Tree tr(n);
  for (int i = 1; i <= n; ++i) {
    cin >> tr.a[i];
  }
  rt[0] = tr.build(1, n);
  for (int i = 1; i <= q; ++i) {
    int pre, op;
    cin >> pre >> op;
    if (op == 1) {
      int pos, x;
      cin >> pos >> x;
      rt[i] = tr.modify(rt[pre], 1, n, x, pos);
    } else if (op == 2) {
      int pos;
      cin >> pos;
      cout << tr.query(rt[pre], 1, n, pos) << endl;
      rt[i] = rt[pre];
    }
  }
}

可持久化并查集

TODO