题解 P3380 【【模板】二逼平衡树（树套树）】
xgzc
2019-02-07 14:57:08
### 题解
过年的假期里肯定要用硬核数据结构打发时间啊
所以我大胆尝试，用了一种速度不能算最快但是码量绝对是很大的一种方法
~~居然控制在了6KB以内~~
**线段树套红黑树**~~（逃~~
这是一次前所未有的尝试
因为线段树套平衡树求区间第$k$小复杂度是$\mathrm{O}(\log^3n)$的
所以速度比不上树状数组套线段树
但是应该在线段树套平衡树的代码中算比较快的了吧
~~不然有愧于红黑树这个名字~~
### 代码
```cpp
#include<cstdio>
#include<cstring>
#include<climits>
#include<algorithm>
inline int read()
{
int data = 0, w = 1;
char ch = getchar();
while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if(ch == '-') w = -1, ch = getchar();
while(ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar();
return data * w;
}
const int maxn(5e4 + 10), maxm(1e7);
int son[2][maxm], fa[maxm], size[maxm], cur;
int cnt[maxm], col[maxm], val[maxm], root, tree[maxn << 2];
inline void newNode(int k, int c, int f)
{
int x = ++cur;
fa[x] = f, size[x] = cnt[x] = 1;
val[x] = k, col[x] = c;
}
inline void update(int x) { size[x] = size[son[0][x]] + cnt[x] + size[son[1][x]]; }
inline void rotate(int x, int r)
{
int y = son[!r][x]; son[!r][x] = son[r][y];
if(son[r][y]) fa[son[r][y]] = x;
fa[y] = fa[x]; if(!fa[x]) root = y;
else son[x == son[1][fa[x]]][fa[x]] = y;
son[r][y] = x, fa[x] = y, size[y] = size[x];
update(x);
}
inline void transplant(int to, int from)
{
fa[from] = fa[to]; if(!fa[to]) root = from;
else son[to == son[1][fa[to]]][fa[to]] = from;
}
int findMin(int x) { while(son[0][x]) x = son[0][x]; return x; }
void insertFixUp(int z)
{
while(col[fa[z]])
{
int f = fa[z], g = fa[f], l = f == son[0][g], y = son[l][g];
if(col[y]) col[y] = col[f] = 0, col[z = g] = 1;
else
{
if(z == son[l][f]) z = f, rotate(z, !l);
col[fa[z]] = 0, col[fa[fa[z]]] = 1; rotate(g, l);
}
}
col[root] = 0;
}
void insert(int k)
{
int x = root, y = 0;
while(x)
{
++size[y = x]; if(val[x] == k) return (void) (++cnt[x]);
x = son[val[x] < k][x];
}
newNode(k, 1, y);
if(!y) root = cur; else son[val[y] < k][y] = cur;
insertFixUp(cur);
}
void delFixUp(int x)
{
while(x != root && (!col[x]))
{
int l = x == son[0][fa[x]], f = fa[x], w = son[l][f];
if(col[w])
{
col[f] = 1, col[w] = 0;
rotate(f, !l); w = son[l][f];
}
if((!col[son[0][w]]) && (!col[son[1][w]])) col[w] = 0, x = fa[x];
else
{
if(!col[son[l][w]])
col[w] = 1, col[son[!l][w]] = 0,
rotate(w, l), w = son[l][f];
col[w] = col[f], col[f] = 0; col[son[l][w]] = 0;
rotate(fa[w], !l); x = root;
}
}
col[x] = 0;
}
void erase(int k)
{
int z = root, w = 0;
while(z)
{
--size[w = z]; if(k == val[z]) break;
z = son[val[z] < k][z];
}
if(z)
{
if(cnt[z] > 1) return (void) (--cnt[z]);
int y = z, x, oldc = col[y];
if(!son[0][z]) x = son[1][z], transplant(z, son[1][z]);
else if(!son[1][z]) x = son[0][z], transplant(z, son[0][z]);
else
{
y = findMin(son[1][z]); oldc = col[y], x = son[1][y];
if(fa[y] == z) fa[x] = y;
else
{
int tmpy = y;
while(tmpy != z) size[tmpy] -= cnt[y], tmpy = fa[tmpy];
transplant(y, son[1][y]); son[1][y] = son[1][z];
fa[son[1][y]] = y;
}
transplant(z, y); son[0][y] = son[0][z];
fa[son[0][y]] = y, col[y] = col[z]; update(y);
}
if(!oldc) delFixUp(x);
}
else while(w) ++size[w], w = fa[w];
}
inline int cmp(int x, int k) { return (val[x] < k) ? 0 : (val[x] ^ k ? 1 : -1); }
int suc(int k, int b)
{
int x = root, p = 0, res = -INT_MAX;
while(x)
if(cmp(x, k) == b) res = val[p = x], x = son[!b][x];
else x = son[b][x];
return res ^ -INT_MAX ? res : (b ? INT_MAX : -INT_MAX);
}
int rank(int r)
{
int x = root, ret = 0;
while(x)
{
if(val[x] < r) ret += size[son[0][x]] + cnt[x], x = son[1][x];
else x = son[0][x];
}
return ret;
}
int a[maxn], n, m;
void insert(int pos, int val)
{
int rt = 1, l = 1, r = n, mid;
while(l ^ r)
{
root = tree[rt]; insert(val); tree[rt] = root;
mid = (l + r) >> 1, rt <<= 1;
if(pos <= mid) r = mid;
else l = mid + 1, ++rt;
}
root = tree[rt]; insert(val); tree[rt] = root;
}
void update(int pos, int val)
{
int rt = 1, l = 1, r = n, mid;
while(l ^ r)
{
root = tree[rt]; insert(val); erase(a[pos]); tree[rt] = root;
mid = (l + r) >> 1, rt <<= 1;
if(pos <= mid) r = mid;
else l = mid + 1, ++rt;
}
root = tree[rt]; insert(val); erase(a[pos]);
tree[rt] = root; a[pos] = val;
}
int lower(int ql, int qr, int val, int rt = 1, int l = 1, int r = n)
{
if(qr < l || r < ql) return 0;
root = tree[rt];
if(ql <= l && r <= qr) return rank(val);
int mid = (l + r) >> 1, lson = rt << 1, rson = lson | 1;
return lower(ql, qr, val, lson, l, mid)
+ lower(ql, qr, val, rson, mid + 1, r);
}
int suc(int ql, int qr, int val, int opt, int rt = 1, int l = 1, int r = n)
{
if(qr < l || r < ql) return opt ? INT_MAX : -INT_MAX;
root = tree[rt];
if(ql <= l && r <= qr) return suc(val, opt);
int mid = (l + r) >> 1, lson = rt << 1, rson = lson | 1;
int lans = suc(ql, qr, val, opt, lson, l, mid);
int rans = suc(ql, qr, val, opt, rson, mid + 1, r);
return opt ? std::min(lans, rans) : std::max(lans, rans);
}
int k_th(int ql, int qr, int k)
{
int l = 0, r = 100000001, mid, rnk;
while(l < r)
{
mid = (l + r) >> 1; rnk = lower(ql, qr, mid);
if(rnk < k) l = mid + 1; else r = mid;
}
return l - 1;
}
int main()
{
n = read(), m = read();
for(int i = 1; i <= n; i++) insert(i, a[i] = read());
while(m--)
{
int opt = read(), x = read(), y = read(), z;
switch(opt)
{
case 1: z = read(); printf("%d\n", lower(x, y, z) + 1); break;
case 2: z = read(); printf("%d\n", k_th(x, y, z)); break;
case 3: update(x, y); break;
case 4: case 5: z = read();
printf("%d\n", suc(x, y, z, opt - 4)); break;
}
}
return 0;
}
```