解：splay + 线段树合并，分裂。
首先有个乱搞做法是外层拿splay维护，有序区间缩成splay上一个节点。内层再开个数据结构支持合并分裂有序集合。
内层我一开始想的是splay，然后就没有复杂度保证，乱搞。
后来发现可以用线段树分裂/合并来，全程复杂度一个log还能在线实时回答询问，NB！
解法二：二分答案 + 把原序列转成01序列来排序。这个我没写，但是感觉很神奇。
1 #include2 3 const int N = 100010, M = 20000010; 4 5 namespace seg { 6 int ls[M], rs[M], sum[M], tot, rt[N]; 7 void insert(int p, int l, int r, int &o) { 8 if(!o) o = ++tot; 9 if(l == r) { 10 sum[o]++; 11 return; 12 } 13 int mid = (l + r) >> 1; 14 if(p <= mid) insert(p, l, mid, ls[o]); 15 else insert(p, mid + 1, r, rs[o]); 16 sum[o] = sum[ls[o]] + sum[rs[o]]; 17 return; 18 } 19 int merge(int x, int y) { 20 if(!x || !y) return x | y; 21 sum[x] += sum[y]; 22 ls[x] = merge(ls[x], ls[y]); 23 rs[x] = merge(rs[x], rs[y]); 24 return x; 25 } 26 int getKth(int k, int l, int r, int o) { 27 if(l == r) return r; 28 int mid = (l + r) >> 1; 29 if(k <= sum[ls[o]]) return getKth(k, l, mid, ls[o]); 30 else return getKth(k - sum[ls[o]], mid + 1, r, rs[o]); 31 } 32 void split(int o, int &x, int &y, int k) { 33 if(!o) { 34 x = y = 0; 35 return; 36 } 37 if(!k) { 38 x = 0; 39 y = o; 40 return; 41 } 42 if(k == sum[o]) { 43 x = o; 44 y = 0; 45 return; 46 } 47 if(k <= sum[ls[o]]) { 48 x = ++tot; 49 y = o; 50 split(ls[o], ls[x], ls[y], k); 51 } 52 else { 53 y = ++tot; 54 x = o; 55 split(rs[o], rs[x], rs[y], k - sum[ls[o]]); 56 } 57 sum[x] = sum[ls[x]] + sum[rs[x]]; 58 sum[y] = sum[ls[y]] + sum[rs[y]]; 59 return; 60 } 61 void out(int l, int r, int o) { 62 if(!o || !sum[o]) return; 63 if(l == r) { 64 printf("%d ", r); 65 return; 66 } 67 int mid = (l + r) >> 1; 68 out(l, mid, ls[o]); 69 out(mid + 1, r, rs[o]); 70 return; 71 } 72 } 73 74 /// --------- 75 76 int fa[N], s[N][2], len[N], lpos[N], rpos[N], siz[N], type[N], root, tot, n, a[N]; 77 std::stack Bin; 78 int stk[N], top; 79 80 inline void pushup(int x) { 81 siz[x] = siz[s[x][0]] + siz[s[x][1]] + len[x]; 82 //printf("pushup [%d %d] %d + %d + %d \n", lpos[x], rpos[x], siz[s[x][0]], len[x], siz[s[x][1]]); 83 if(!fa[x]) root = x; 84 return; 85 } 86 87 inline void pushdown(int x) { 88 return; 89 } 90 91 inline void rotate(int x) { 92 int y = fa[x]; 93 int z = fa[y]; 94 bool f = (s[y][1] == x); 95 96 fa[x] = z; 97 if(z) { 98 s[z][s[z][1] == y] = x; 99 }100 s[y][f] = s[x][!f];101 if(s[x][!f]) {102 fa[s[x][!f]] = y;103 }104 s[x][!f] = y;105 fa[y] = x;106 107 pushup(y);108 return;109 }110 111 inline void splay(int x, int g = 0) {112 int y = x;113 stk[top = 1] = y;114 while(fa[y]) {115 y = fa[y];116 stk[++top] = y;117 }118 while(top) {119 pushdown(stk[top]);120 top--;121 }122 123 y = fa[x];124 int z = fa[y];125 while(y != g) {126 if(z != g) {127 (s[z][1] == y) ^ (s[y][1] == x) ?128 rotate(x) : rotate(y);129 }130 rotate(x);131 y = fa[x];132 z = fa[y];133 }134 pushup(x);135 return;136 }137 138 void out(int x = root) {139 pushdown(x);140 if(s[x][0]) {141 out(s[x][0]);142 }143 printf("[%d %d] ", lpos[x], rpos[x]);144 printf("rt = %d : ", seg::rt[x]);145 seg::out(1, n, seg::rt[x]);146 puts("");147 if(s[x][1]) {148 out(s[x][1]);149 }150 return;151 }152 153 inline int np(int l, int r, int f, int tp) {154 int x;155 if(Bin.size()) {156 x = Bin.top();157 seg::rt[x] = 0;158 Bin.pop();159 }160 else x = ++tot;161 fa[x] = f;162 s[x][0] = s[x][1] = 0;163 lpos[x] = l;164 rpos[x] = r;165 siz[x] = len[x] = r - l + 1;166 type[x] = tp;167 return x;168 }169 170 inline int getRP() {171 pushdown(root);172 int p = s[root][1];173 pushdown(p);174 while(s[p][0]) {175 p = s[p][0];176 pushdown(p);177 }178 return p;179 }180 181 inline int getLP() {182 pushdown(root);183 int p = s[root][0];184 pushdown(p);185 while(s[p][1]) {186 p = s[p][1];187 pushdown(p);188 }189 return p;190 }191 192 inline int getPbyR(int k) {193 k++;194 int p = root;195 while(1) {196 //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]]);197 pushdown(p);198 if(k <= siz[s[p][0]]) {199 p = s[p][0];200 }201 else if(k <= siz[s[p][0]] + len[p]) {202 break;203 }204 else {205 k -= siz[s[p][0]] + len[p];206 p = s[p][1];207 }208 }209 /// p210 splay(p);211 return p;212 }213 214 inline int split(int x, int k) { /* [lpos[x], k] [k + 1, rpos[x]] return left */215 int A, B;216 splay(x);217 int y = getRP();218 splay(y, x);219 if(type[x] == 0) {220 seg::split(seg::rt[x], A, B, k);221 int z = np(lpos[x] + k, rpos[x], y, type[x]);222 rpos[x] = lpos[x] + k - 1;223 len[x] = rpos[x] - lpos[x] + 1;224 seg::rt[z] = B;225 seg::rt[x] = A;226 s[y][0] = z;227 pushup(y);228 pushup(x);229 }230 else {231 seg::split(seg::rt[x], A, B, len[x] - k);232 int z = np(lpos[x] + k, rpos[x], y, type[x]);233 rpos[x] = lpos[x] + k - 1;234 len[x] = rpos[x] - lpos[x] + 1;235 seg::rt[z] = A;236 seg::rt[x] = B;237 s[y][0] = z;238 pushup(y);239 pushup(x);240 }241 return x;242 }243 244 void dfs(int x, int rt) {245 if(s[x][0]) {246 dfs(s[x][0], rt);247 }248 if(s[x][1]) {249 dfs(s[x][1], rt);250 }251 if(x != rt) {252 seg::rt[rt] = seg::merge(seg::rt[rt], seg::rt[x]);253 Bin.push(x);254 }255 return;256 }257 258 inline void Sort(int L, int R, int f) { /* 0 up 1 down */259 int x = getPbyR(L);260 261 //printf("x %d [%d %d] y %d [%d %d] \n", x, lpos[x], rpos[x], y, lpos[y], rpos[y]);262 263 if(lpos[x] != L) {264 x = split(x, L - lpos[x]);265 splay(x);266 x = getRP();267 }268 int y = getPbyR(R);269 //printf("x %d [%d %d] y %d [%d %d] \n", x, lpos[x], rpos[x], y, lpos[y], rpos[y]);270 if(rpos[y] != R) {271 y = split(y, R - lpos[y] + 1);272 }273 // merge [x, y]274 //printf("x %d [%d %d] y %d [%d %d] \n", x, lpos[x], rpos[x], y, lpos[y], rpos[y]);275 splay(x);276 int A = getLP();277 splay(y);278 int B = getRP();279 splay(B);280 splay(A, B);281 /// s[A][1]282 x = s[A][1];283 dfs(x, x);284 lpos[x] = L;285 rpos[x] = R;286 siz[x] = len[x] = R - L + 1;287 type[x] = f;288 s[x][0] = s[x][1] = 0;289 pushup(A);290 pushup(B);291 return;292 }293 /*294 5 5295 1 2 3 4 5296 1 2 3297 1 4 5298 1 1 4299 0 2 5300 0 3 4301 1302 ------------303 */304 inline int ask(int p) {305 int x = getPbyR(p);306 if(type[x] == 0) {307 int k = p - lpos[x] + 1;308 return seg::getKth(k, 1, n, seg::rt[x]);309 }310 else {311 int k = p - lpos[x] + 1;312 k = len[x] - k + 1;313 return seg::getKth(k, 1, n, seg::rt[x]);314 }315 }316 317 int build(int l, int r, int f) {318 int mid = (l + r) >> 1;319 int x = np(mid, mid, f, 0);320 if(mid && mid <= n) seg::insert(a[mid], 1, n, seg::rt[x]);321 if(l < mid) s[x][0] = build(l, mid - 1, x);322 if(mid < r) s[x][1] = build(mid + 1, r, x);323 pushup(x);324 return x;325 }326 327 int main() {328 int m;329 scanf("%d%d", &n, &m);330 for(int i = 1; i <= n; i++) {331 scanf("%d", &a[i]);332 }333 /// build334 root = build(0, n + 1, 0);335 336 //out(), puts("");337 338 for(int i = 1, f, l, r; i <= m; i++) {339 scanf("%d%d%d", &f, &l, &r);340 Sort(l, r, f);341 //out(), puts("");342 }343 int q;344 scanf("%d", &q);345 int t = ask(q);346 printf("%d\n", t);347 return 0;348 }
这题调的时候splay出了大约10个锅，从没写过的线段树分裂一次写对......
线段树分裂，把前k小分成一个，后面分成另一个。实现类似fhqtreap，不过要新开节点。