主席树

引入

我们考虑对于一个长度为 \(n\) 的序列去找第 \(k\) 小，如果不用排序的话（虽然用了桶），可以利用一个桶匠所有数纪录下来，然后在桶上做二分即可（不会这个都不会吧），那么对于一个区间的话，我们便可以在区间 \([l, r]\) 上开桶然后做二分，不过这个桶我们该如何维护呢，首先我们想到前缀和，因为用前缀和可以快速求区间，可是如果直接用数组的话，我们无法直接快速的算出区间 \([l, r]\) 的桶，于是我们想到了平衡树的操作，将 \(r\) 处的平衡树把 \(l - 1\) 处的平衡树的一部分去点即可，不过想法很好，空间会炸，而且这很明显没用完美利用平衡树，所以考虑用一种可以将 \(n^2\) 空间换成一个小的空间的线段树。

思路

考虑到在这 \(n\) 次加点中，每次加点最多加一个点，而对于一颗线段树，只有一条链上的值发生了改变，从而我们将改变的数以及所在结构抽出来，形成一颗新的线段树，我们便用 \(log\) 的空间建了一个新的线段树，不过由于是在之前的基础上加的，正真在做这颗线段树的时候，是要算上前面的，所以我们需要将这棵树连回去，所以我们将这棵树的结构在原来位置上存在的边加回来，便是连上了，从而我们就成功的将 \(n ^ 2\) 空间缩小到了 \(nlogn\)，那么在查询的时候，我们只需要考虑左边有多少个比它小的，所以只需要将前缀和的方式处理掉 \(l - 1\) 及以前有多少个数即可。

code

#include <iostream>

using namespace std;

const int MaxN = 2e5 + 10, inf = 1e9;

struct Node {
  int sum, l, r;
} a[MaxN << 5];

int rt[MaxN], n, m, tot;

void insert(int &x, int y, int l, int r, int v) {
  x = ++tot, a[x].sum = a[y].sum + 1;
  if (l == r) {
    return;
  }
  int mid = l + r >> 1;
  if (v <= mid) insert(a[x].l, a[y].l, l, mid, v), a[x].r = a[y].r;
  else insert(a[x].r, a[y].r, mid + 1, r, v), a[x].l = a[y].l;
}

int query(int x, int y, int l, int r, int k) {
  if (l == r) {
    return l;
  }
  int v = a[a[x].l].sum - a[a[y].l].sum, mid = l + r >> 1;
  if (k <= v) return query(a[x].l, a[y].l, l, mid, k);
  else return query(a[x].r, a[y].r, mid + 1, r, k - v);
}

int main() {
  cin >> n >> m;
  for (int i = 1, x; i <= n; i++) {
    cin >> x;
    insert(rt[i], rt[i - 1], 0, inf, x);
  }
  for (int i = 1, l, r, k; i <= m; i++) {
    cin >> l >> r >> k;
    cout << query(rt[r], rt[l - 1], 0, inf, k) << endl;
  }
  return 0;
}

P2839 [国家集训队] middle

当然，这个东西不一定是一个权值线段树

思路

由于要算中位数，所以我们先思考给了 \([l, r]\) 以及中位数 \(k\) 怎么保证这个是中位数，那么很显然将所有 \(< k\) 的改为 \(-1\)，\(\ge k\) 的改为 \(1\)，然后统计一下区间和是否 \(\ge 0\) 如果 \(\ge 0\) 就是可以不过可能可以再大些，否则就是大了，不成立，于是我们考虑二分去找中位数，那么对于会变动的区间又该如何呢？由于不考虑方案，所以我们只需要找方案里答案最大的即可，由于中间的 \([b + 1, c - 1]\) 必选，所以将整个变动区间分为三部分，中间直接求，两边取最大值即可，那我们不可能去暴力改变数组，所以可以用主席树维护当每一个点作为中位数时的每一个数的值。

code

#include <iostream>
#include <algorithm>

using namespace std;

const int MaxN = 40010, inf = 1e9;

struct Node {
  int x, l, r, lmax, rmax;
} a[MaxN << 5];

struct S {
  int x, y;

  bool operator<(const S &j) const {
    return x < j.x;
  }
} b[MaxN];

int rt[MaxN], n, m, tot;

void insert(int &x, int y, int k, int v, int l = 1, int r = n) {
  x = ++tot, a[x] = a[y];
  if (l == r) {
    a[x].x = v, a[x].lmax = a[x].rmax = v;
    return;
  }
  int mid = l + r >> 1;
  if (k <= mid)
    insert(a[x].l, a[y].l, k, v, l, mid);
  else
    insert(a[x].r, a[y].r, k, v, mid + 1, r);
  a[x].lmax = max(a[a[x].l].lmax, a[a[x].r].lmax + a[a[x].l].x);
  a[x].rmax = max(a[a[x].r].rmax, a[a[x].l].rmax + a[a[x].r].x);
  a[x].x = a[a[x].l].x + a[a[x].r].x;
}

int query(int x, int pl, int pr, int l = 1, int r = n) {
  if (pl <= l && r <= pr) {
    return a[x].x;
  }
  if (l > pr || r < pl) return 0;
  int mid = l + r >> 1;
  return query(a[x].l, pl, pr, l, mid) + query(a[x].r, pl, pr, mid + 1, r);
}

int queryl(int x, int pl, int pr, int l = 1, int r = n) {
  if (pl <= l && r <= pr) {
    return a[x].lmax;
  }
  int mid = l + r >> 1;
  if (mid >= pr) {
    return queryl(a[x].l, pl, pr, l, mid);
  } else if (mid < pl) {
    return queryl(a[x].r, pl, pr, mid + 1, r);
  }
  return max(queryl(a[x].l, pl, pr, l, mid), query(a[x].l, pl, pr, l, mid) + queryl(a[x].r, pl, pr, mid + 1, r));
}

int queryr(int x, int pl, int pr, int l = 1, int r = n) {
  if (pl <= l && r <= pr) {
    return a[x].rmax;
  }
  int mid = l + r >> 1;
  if (mid >= pr) {
    return queryr(a[x].l, pl, pr, l, mid);
  } else if (mid < pl) {
    return queryr(a[x].r, pl, pr, mid + 1, r);
  }
  return max(queryr(a[x].r, pl, pr, mid + 1, r), query(a[x].r, pl, pr, mid + 1, r) + queryr(a[x].l, pl, pr, l, mid));
}

bool Check(int x, int a, int b, int c, int d) {
  int cnt = 0;
  if (b + 1 <= c - 1) {
    cnt += query(rt[x], b + 1, c - 1);
  }
  cnt += queryr(rt[x], a, b) + queryl(rt[x], c, d);
  return cnt >= 0;
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> b[i].x, b[i].y = i;
  }
  sort(b + 1, b + n + 1);
  for (int i = 1; i <= n; i++) {
    insert(rt[i], rt[i - 1], b[i].y, 1);
  }
  rt[n + 1] = rt[n];
  for (int i = 2; i <= n; i++) {
    insert(rt[i + n], rt[i + n - 1], b[i - 1].y, -1);
  }
  cin >> m;
  for (int tmp[5] = {0}, x = 0; m; m--) {
    cin >> tmp[0] >> tmp[1] >> tmp[2] >> tmp[3];
    tmp[0] = (tmp[0] + x) % n + 1, tmp[1] = (tmp[1] + x) % n + 1, tmp[2] = (tmp[2] + x) % n + 1, tmp[3] = (tmp[3] + x) % n + 1;
    sort(tmp, tmp + 4);
    int l = 1, r = n;
    while (l < r) {
      int mid = l + r + 1 >> 1;
      Check(mid + n, tmp[0], tmp[1], tmp[2], tmp[3]) ? l = mid : r = mid - 1;
    }
    cout << b[l].x << endl;
    x = b[l].x;
  }
  return 0;
}