BZOJ 4552
题意：给出一个$1$到$n$的全排列，现在对这个全排列序列进行$m$次局部排序，排序分为两种：
$1:(0,l,r)$表示将区间$[l,r]$的数字升序排序
$2:(1,l,r)$表示将区间$[l,r]$的数字降序排序最后询问第$q$位置上的数字。
方法一
只有一个位置，我们可以二分这个上面的数是多少。
考虑将数的排序转化为二进制数$01$的排序。因为二进制数$01$的排序只需要升序将所有$0$放在$1$前，降序反之。
那么我们怎么将数转化成这个呢，我们考虑大于二分值的数赋值为$1$, 否则为$0$，对询问离线，线段树辅助$01$数排序，求出最后的结果，然后如果$q$上是$1$，说明当前二分值小了，否则大了。
线段树排序$01$数即查询区间$01$个数，再区间修改
本方法难想但是代码好写。
方法二
考虑直接模拟题目的过程，我们可以将原来的每个数变成孤立的每个点，那么每次排序都会合并一系列点，并且此时还可能需要分裂。我们考虑一个支持合并、按前$k$大分裂的权值线段树。用一个$\text{Set}(l,r,nd,op)$来维护区间合并情况，即记录$[l,r]$的根在$nd$, 是升序还是降序，然后分裂时二分找出来后处理即可。具体可以看代码实现。这里体现了数据结构互相辅助的优势。
本方法好想，但是代码难写。本题为了训练线段树分裂，我写了方法二的代码。
本文借鉴于 HEOI2016/TJOI2016 排序 解题报告（二分答案/线段树分裂合并+set） - 星星之火OIer - 博客园
知识点
1、将数的排序转化为二进制数$01$的排序的方法 (用于二分)。
2、数据结构互相辅助的优势。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 100000 + 5;
int n, m, a[MAXN];
struct data { // set 记录节点
int l, r, nd, op; // 区间，根，是降序还是升序
bool operator < (const data &rhs) const {return r == rhs.r ? l < rhs.l : r < rhs.r;}
};
namespace seg {
#define M ((l + r) >> 1)
int sz, lc[MAXN * 60], rc[MAXN * 60], sumv[MAXN * 60];
void update(int l, int r, int &now, int x) { // 加一个值
if (!now) now = ++sz;
++sumv[now];
if (l == r) return ;
if (x <= M) update(l, M, lc[now], x); else update(M + 1, r, rc[now], x);
}
int kth(int l, int r, int now, int k) { // 找 k 大
if (l == r) return l;
int whw = sumv[lc[now]];
if (k <= whw) return kth(l, M, lc[now], k);
else return kth(M + 1, r, rc[now], k - whw);
}
void split(int l, int r, int now, int &res, int k) { // 按 k 大将小于等于 k 的分到 res 里，其他留在 now 里
if (!now) return ;
if (!res) res = ++sz;
if (l == r) {sumv[now] -= k, sumv[res] += k; return ;}
int whw = sumv[lc[now]];
if (whw > k) split(l, M, lc[now], lc[res], k);
else if (whw == k) lc[res] = lc[now], lc[now] = 0;
else if (whw < k) {
lc[res] = lc[now], lc[now] = 0;
split(M + 1, r, rc[now], rc[res], k - whw);
} // 和 kth 差不多
sumv[now] = sumv[lc[now]] + sumv[rc[now]];
sumv[res] = sumv[lc[res]] + sumv[rc[res]]; // pushup
}
int merge(int &x, int y) { // 合并两个线段树
if (x == 0) return x = y;
if (y == 0) return 0;
sumv[x] += sumv[y];
return merge(lc[x], lc[y]), merge(rc[x], rc[y]);
}
}
namespace S {
set<data > s;
int split(int l, int r) { // 将 [l, r] 分出来使得 set 里有这个区间，返回这个区间的根
set<data >::iterator it = s.lower_bound((data){0, l, 0, 0});
if (it->l != l) { // l 在 *it 区间里
data whw = *it; s.erase(it); int gg = 0;
if (whw.op == 1) { // 降序
seg::split(1, n, whw.nd, gg, whw.r - l + 1);
s.insert((data){whw.l, l - 1, whw.nd, 1});
s.insert((data){l, whw.r, gg, 1});
} else { // 增序
seg::split(1, n, whw.nd, gg, l - whw.l);
s.insert((data){whw.l, l - 1, gg, 0});
s.insert((data){l, whw.r, whw.nd, 0});
}
}
it = s.lower_bound((data){0, r, 0, 0});
if (it->r != r) { // r 在 *it 区间里
data whw = *it; s.erase(it); int gg = 0;
if (whw.op == 1) { // 降序
seg::split(1, n, whw.nd, gg, whw.r - r);
s.insert((data){whw.l, r, whw.nd, 1});
s.insert((data){r + 1, whw.r, gg, 1});
} else { // 增序
seg::split(1, n, whw.nd, gg, r - whw.l + 1);
s.insert((data){whw.l, r, gg, 0});
s.insert((data){r + 1, whw.r, whw.nd, 0});
}
}
int ret = 0;
while (1) { // 将刚刚分出来的区间合成一个
it = s.lower_bound((data){0, l, 0, 0});
if (it == s.end() || it->r > r) break ; //
seg::merge(ret, it->nd);
s.erase(it);
}
return ret;
}
}
void clean() {
}
int solve() {
clean();
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
int x = 0;
seg::update(1, n, x, a[i]);
S::s.insert((data){i, i, x, 0});
}
for (int op, l, r, i = 1; i <= m; ++i) {
scanf("%d%d%d", &op, &l, &r);
int x = S::split(l, r);
S::s.insert((data){l, r, x, op}); // 记得将整个区间加到 set 里
}
int p; scanf("%d", &p);
int x = S::split(p, p);
printf("%d\n", seg::kth(1, n, x, 1));
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
