解：splay + 线段树合并，分裂。
首先有个乱搞做法是外层拿splay维护，有序区间缩成splay上一个节点。内层再开个数据结构支持合并分裂有序集合。
内层我一开始想的是splay，然后就没有复杂度保证，乱搞。
后来发现可以用线段树分裂/合并来，全程复杂度一个log还能在线实时回答询问，NB！
解法二：二分答案 + 把原序列转成01序列来排序。这个我没写，但是感觉很神奇。
#include <bits/stdc++.h>
const int N = , M = ;
namespace seg {
int ls[M], rs[M], sum[M], tot, rt[N];
void insert(int p, int l, int r, int &o) {
if(!o) o = ++tot;
if(l == r) {
sum[o]++;
return;
}
int mid = (l + r) >> ;
if(p <= mid) insert(p, l, mid, ls[o]);
else insert(p, mid + , r, rs[o]);
sum[o] = sum[ls[o]] + sum[rs[o]];
return;
}
int merge(int x, int y) {
if(!x || !y) return x | y;
sum[x] += sum[y];
ls[x] = merge(ls[x], ls[y]);
rs[x] = merge(rs[x], rs[y]);
return x;
}
int getKth(int k, int l, int r, int o) {
if(l == r) return r;
int mid = (l + r) >> ;
if(k <= sum[ls[o]]) return getKth(k, l, mid, ls[o]);
else return getKth(k - sum[ls[o]], mid + , r, rs[o]);
}
void split(int o, int &x, int &y, int k) {
if(!o) {
x = y = ;
return;
}
if(!k) {
x = ;
y = o;
return;
}
if(k == sum[o]) {
x = o;
y = ;
return;
}
if(k <= sum[ls[o]]) {
x = ++tot;
y = o;
split(ls[o], ls[x], ls[y], k);
}
else {
y = ++tot;
x = o;
split(rs[o], rs[x], rs[y], k - sum[ls[o]]);
}
sum[x] = sum[ls[x]] + sum[rs[x]];
sum[y] = sum[ls[y]] + sum[rs[y]];
return;
}
void out(int l, int r, int o) {
if(!o || !sum[o]) return;
if(l == r) {
printf("%d ", r);
return;
}
int mid = (l + r) >> ;
out(l, mid, ls[o]);
out(mid + , r, rs[o]);
return;
}
}
/// ---------
int fa[N], s[N][], len[N], lpos[N], rpos[N], siz[N], type[N], root, tot, n, a[N];
std::stack<int> Bin;
int stk[N], top;
inline void pushup(int x) {
siz[x] = siz[s[x][]] + siz[s[x][]] + len[x];
//printf("pushup [%d %d] %d + %d + %d \n", lpos[x], rpos[x], siz[s[x][0]], len[x], siz[s[x][1]]);
if(!fa[x]) root = x;
return;
}
inline void pushdown(int x) {
return;
}
inline void rotate(int x) {
int y = fa[x];
int z = fa[y];
bool f = (s[y][] == x);
fa[x] = z;
if(z) {
s[z][s[z][] == y] = x;
}
s[y][f] = s[x][!f];
if(s[x][!f]) {
fa[s[x][!f]] = y;
}
s[x][!f] = y;
fa[y] = x;
pushup(y);
return;
}
inline void splay(int x, int g = ) {
int y = x;
stk[top = ] = y;
while(fa[y]) {
y = fa[y];
stk[++top] = y;
}
while(top) {
pushdown(stk[top]);
top--;
}
y = fa[x];
int z = fa[y];
while(y != g) {
if(z != g) {
(s[z][] == y) ^ (s[y][] == x) ?
rotate(x) : rotate(y);
}
rotate(x);
y = fa[x];
z = fa[y];
}
pushup(x);
return;
}
void out(int x = root) {
pushdown(x);
if(s[x][]) {
out(s[x][]);
}
printf("[%d %d] ", lpos[x], rpos[x]);
printf("rt = %d : ", seg::rt[x]);
seg::out(, n, seg::rt[x]);
puts("");
if(s[x][]) {
out(s[x][]);
}
return;
}
inline int np(int l, int r, int f, int tp) {
int x;
if(Bin.size()) {
x = Bin.top();
seg::rt[x] = ;
Bin.pop();
}
else x = ++tot;
fa[x] = f;
s[x][] = s[x][] = ;
lpos[x] = l;
rpos[x] = r;
siz[x] = len[x] = r - l + ;
type[x] = tp;
return x;
}
inline int getRP() {
pushdown(root);
int p = s[root][];
pushdown(p);
while(s[p][]) {
p = s[p][];
pushdown(p);
}
return p;
}
inline int getLP() {
pushdown(root);
int p = s[root][];
pushdown(p);
while(s[p][]) {
p = s[p][];
pushdown(p);
}
return p;
}
inline int getPbyR(int k) {
k++;
int p = root;
while() {
//printf("p : [%d %d] %d -> [%d %d] %d [%d %d] %d \n", lpos[p], rpos[p], siz[p], lpos[s[p][0]], rpos[s[p][0]], siz[s[p][0]], lpos[s[p][1]], rpos[s[p][1]], siz[s[p][1]]);
pushdown(p);
if(k <= siz[s[p][]]) {
p = s[p][];
}
else if(k <= siz[s[p][]] + len[p]) {
break;
}
else {
k -= siz[s[p][]] + len[p];
p = s[p][];
}
}
/// p
splay(p);
return p;
}
inline int split(int x, int k) { /* [lpos[x], k] [k + 1, rpos[x]] return left */
int A, B;
splay(x);
int y = getRP();
splay(y, x);
if(type[x] == ) {
seg::split(seg::rt[x], A, B, k);
int z = np(lpos[x] + k, rpos[x], y, type[x]);
rpos[x] = lpos[x] + k - ;
len[x] = rpos[x] - lpos[x] + ;
seg::rt[z] = B;
seg::rt[x] = A;
s[y][] = z;
pushup(y);
pushup(x);
}
else {
seg::split(seg::rt[x], A, B, len[x] - k);
int z = np(lpos[x] + k, rpos[x], y, type[x]);
rpos[x] = lpos[x] + k - ;
len[x] = rpos[x] - lpos[x] + ;
seg::rt[z] = A;
seg::rt[x] = B;
s[y][] = z;
pushup(y);
pushup(x);
}
return x;
}
void dfs(int x, int rt) {
if(s[x][]) {
dfs(s[x][], rt);
}
if(s[x][]) {
dfs(s[x][], rt);
}
if(x != rt) {
seg::rt[rt] = seg::merge(seg::rt[rt], seg::rt[x]);
Bin.push(x);
}
return;
}
inline void Sort(int L, int R, int f) { /* 0 up 1 down */
int x = getPbyR(L);
//printf("x %d [%d %d] y %d [%d %d] \n", x, lpos[x], rpos[x], y, lpos[y], rpos[y]);
if(lpos[x] != L) {
x = split(x, L - lpos[x]);
splay(x);
x = getRP();
}
int y = getPbyR(R);
//printf("x %d [%d %d] y %d [%d %d] \n", x, lpos[x], rpos[x], y, lpos[y], rpos[y]);
if(rpos[y] != R) {
y = split(y, R - lpos[y] + );
}
// merge [x, y]
//printf("x %d [%d %d] y %d [%d %d] \n", x, lpos[x], rpos[x], y, lpos[y], rpos[y]);
splay(x);
int A = getLP();
splay(y);
int B = getRP();
splay(B);
splay(A, B);
/// s[A][1]
x = s[A][];
dfs(x, x);
lpos[x] = L;
rpos[x] = R;
siz[x] = len[x] = R - L + ;
type[x] = f;
s[x][] = s[x][] = ;
pushup(A);
pushup(B);
return;
}
/*
5 5
1 2 3 4 5
1 2 3
1 4 5
1 1 4
0 2 5
0 3 4
1
------------
*/
inline int ask(int p) {
int x = getPbyR(p);
if(type[x] == ) {
int k = p - lpos[x] + ;
return seg::getKth(k, , n, seg::rt[x]);
}
else {
int k = p - lpos[x] + ;
k = len[x] - k + ;
return seg::getKth(k, , n, seg::rt[x]);
}
}
int build(int l, int r, int f) {
int mid = (l + r) >> ;
int x = np(mid, mid, f, );
if(mid && mid <= n) seg::insert(a[mid], , n, seg::rt[x]);
if(l < mid) s[x][] = build(l, mid - , x);
if(mid < r) s[x][] = build(mid + , r, x);
pushup(x);
return x;
}
int main() {
int m;
scanf("%d%d", &n, &m);
for(int i = ; i <= n; i++) {
scanf("%d", &a[i]);
}
/// build
root = build(, n + , );
//out(), puts("");
for(int i = , f, l, r; i <= m; i++) {
scanf("%d%d%d", &f, &l, &r);
Sort(l, r, f);
//out(), puts("");
}
int q;
scanf("%d", &q);
int t = ask(q);
printf("%d\n", t);
return ;
}
AC代码
这题调的时候splay出了大约10个锅，从没写过的线段树分裂一次写对......
线段树分裂，把前k小分成一个，后面分成另一个。实现类似fhqtreap，不过要新开节点。