题目：二逼平衡树 及其启示

改变数据结构的写法了， 以后就把所有抽象数据类型塞到namespace
里去了qwq

// WA、 TEL 且 RE 的代码， 以后再调
#include<bits/stdc++.h>
using namespace std;
const int maxlog = 20;

namespace fhq {
    
    const int maxn = maxlog * 50000 + 1001;
    int siz[maxn] ,ls[maxn], rs[maxn], rnd[maxn], val[maxn], tot;
    
    int newnode(int v)
    {
        val[++tot] = v; rnd[tot] = rand(); siz[tot] = 1;
//      ls[tot] = rs[tot] = 0;
        return tot;
    }
    
    void update(int k)
    {
        siz[k] = siz[ls[k]] + siz[rs[k]] + 1;
    }
    
    void merge(int &k,int a, int b)
    {
        if(!a || !b)
        {
            k = a + b;
            return;
        }
        if(rnd[a] < rnd[b])
        {
            k = a;
            merge(rs[a], rs[a], b);
        }
        else
        {
            k = b;
            merge(ls[b], a, ls[b]);
        }
        update(k);
    }
    
    void split(int k, int &a, int &b, int weight)
    {
        if(!k)
        {
            a = b = 0;
            return;
        }
        if(val[k] <= weight)
        {
            a = k;
            split(rs[a], rs[a], b, weight);
        }
        else
        {
            b = k;
            split(ls[b], a, ls[b], weight);
        }
        update(k);
    }
    
    void ins(int &rt, int v)
    {
        int a = 0, b = 0;
        split(rt, a, b, v);
        merge(a, a, newnode(v));
        merge(rt, a, b);
    }
    
    int quesrank(int &rt, int k)
    {
        int a = 0, b = 0;
        split(rt, a, b, k-1);
        int ret = siz[a];
        merge(rt, a, b);
        return ret;
    }
    
    void del(int &rt,int k)
    {
        int a = 0, b = 0, c = 0;
        split(rt, a, c, k);
        split(a, a, b, k-1);
        merge(b, ls[b], rs[b]);
        merge(a, a, b);
        merge(rt, a, c);
    }
    
    int ma(int p)
    {
        if(!siz[p]) return -2147483647;
        while(rs[p]) p=rs[p];
        return val[p];
    }
    
    int mi(int p)
    {
        if(!siz[p]) return 2147483647;
        while(ls[p]) p=ls[p];
        return val[p];
    }
    
    int pre(int &rt,int k)
    {
        int a = 0, b = 0;
        split(rt, a, b, k-1);
        int ret = ma(a);
        merge(rt, a, b);
        return ret;
    }
    
    int nxt(int &rt,int k)
    {
        int a = 0, b = 0;
        split(rt, a, b, k);
        int ret = mi(b);
        merge(rt, a, b);
        return ret;
    }
    
}

namespace seg {
    
    const int maxn = maxlog * 50000;
    
    int ls[maxn], rs[maxn], fhqrt[maxn];
    int rt, tot, n;
    
    int m, vec[5005];
    
    void build(int* a, int &u, int l,int r)
    {
        if(!u) u = ++tot;
        //
        for(int i=l; i<=r; ++i) fhq::ins(fhqrt[u], a[i]);
        //build fhq
        if(l == r) return;
        int mid = (l + r) >> 1;
        build(a, ls[u], l, mid);
        build(a, rs[u], mid + 1, r);
    }
    
    void vis(int u, int l,int r,int x,int y)
    {
        if(x<=l && r<=y) {
            vec[++m] = u;
            return;
        }
        int mid = (l + r) >> 1;
        if(x <= mid) vis(ls[u], l, mid, x, y);
        if(y > mid) vis(rs[u], mid + 1, r, x, y);
    }
    
    void getvec(int l,int r)
    {
        m = 0;
        vis(rt, 1, n, l, r);
    }
    
    int quesrank(int l,int r,int k)
    {
        getvec(l, r);
        int ret = 0;
        for(int i=1; i<=m; ++i)
        {
            ret += fhq::quesrank(fhqrt[vec[i]], k);
        }
        return ret + 1;
    }
    
    int queskth(int l,int r,int k)
    {
        int L = 0, R = 100000000;
        while(L!=R)
        {
            int mid = (L+R+1) >> 1;
            if(quesrank(l, r, mid) > k) R = mid-1;
            else L = mid;
        }
        return L;
    }
    
    //modify(seg::rt, 1, n, pos, k);
    int modify(int u, int l,int r,int pos,int k)
    {
        
        if(l == r) {
            int ret = fhq::val[fhqrt[u]];
            fhq::del(fhqrt[u], ret);
            fhq::ins(fhqrt[u], k);
            return ret;
        }
        int mid = (l+r) >> 1; int d;
        if(pos<=mid) d = modify(ls[u], l, mid, pos, k);
        else d = modify(rs[u], mid + 1, r, pos, k);
        fhq::del(fhqrt[u], d);
        fhq::ins(fhqrt[u], k);
        
        return 1;
        
    }
    
    int quesprev(int l,int r,int k)
    {
        getvec(l, r);
        int ret = -2147483647;
        for(int i=1; i<=m; ++i)
        {
            ret = max(ret, fhq::pre(fhqrt[vec[i]], k));
        }
        return ret;
    }
    
    int quesnext(int l,int r,int k)
    {
        getvec(l, r);
        int ret = 2147483647;
        for(int i=1; i<=m; ++i)
        {
            ret = min(ret, fhq::nxt(fhqrt[vec[i]], k));
        }
        return ret;
    } 
    
}

int a[50005], n, m;

int main()
{
    
    srand((unsigned)time(0));
    
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; ++i) scanf("%d", &a[i]);
    seg::build(a, seg::rt, 1, n);
    seg::n = n;
    
    while(m--)
    {
        int opt; scanf("%d", &opt);
        if(opt == 1)
        {
            int l, r, k; scanf("%d%d%d", &l, &r, &k);
            cout << seg::quesrank(l, r, k) << '\n';
        }
        if(opt == 2)
        {
            int l, r, k; scanf("%d%d%d", &l, &r, &k);
            cout << seg::queskth(l, r, k) << '\n';
        }
        if(opt == 3)
        {
            int pos, k; scanf("%d%d", &pos, &k);
            seg::modify(seg::rt, 1, n, pos, k);
        }
        if(opt == 4)
        {
            int l, r, k; scanf("%d%d%d", &l, &r, &k);
            cout << seg::quesprev(l, r, k) <<'\n';
        }
        if(opt == 5)
        {
            int l, r, k; scanf("%d%d%d", &l, &r, &k);
            cout << seg::quesnext(l, r, k) <<'\n';
        }
    }
    
    return 0;
    
}

题目：二逼平衡树 及其启示

原文：https://www.cnblogs.com/tztqwq/p/12149438.html