P3369 普通平衡树

普通平衡树：用权值线段树维护有序多重集

问题

P3369 【模板】普通平衡树
动态维护一个可重集合，支持插入、删除、查询排名、第 $k$ 小、前驱和后继。

数据规模：操作数 $n\le 10^5$，$|x|\le 10^7$。

虽然本题叫平衡树，但是这里提供一种权值线段树的做法。

发现六种操作的核心都是维护值域中的元素个数。所以可以采用权值的数据结构来处理，当然需要离散化，如果值是中间计算出来，无法离线的话，就不能使用当前离线离散化版本了，可使用动态开点权值线段树或平衡树。

设 idx 是 $x$ 离散化后的下标，线段树节点维护对应值域内的元素总数。

• 插入 $x$：在 idx 处加 $1$；
• 删除 $x$：在 idx 处减 $1$；
• 查询 $x$ 的排名：统计所有严格小于 $x$ 的元素数，再加 $1$；
• 查询第 $k$ 小：根据左右子树元素个数在线段树上向下定位；
• 查询 $x$ 的前驱：先统计严格小于 $x$ 的元素数 $k$，答案是第 $k$ 小；
• 查询 $x$ 的后继：先统计小于等于 $x$ 的元素数 $k$，答案是第 $k+1$ 小。

重复元素直接累加在同一个叶子上，因此线段树中维护的是元素个数，而不是不同值的个数。

时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。

▶

P3369

struct Disc {
/* ======================================== */
vector<int> v;
void clear( ) { v.clear( ); }
void add( int x ) { v.push_back( x ); }
void init( ) {
    sort( v.begin( ), v.end( ) );
    v.erase( unique( v.begin( ), v.end( ) ), v.end( ) );
}
int size( ) { return v.size( ); }
int get_idx( int x ) { return lower_bound( v.begin( ), v.end( ), x ) - v.begin( ) + 1; }
int get_val( int idx ) { return v[idx - 1]; }
/* ======================================== */
} disc;

#define ls ( u << 1 )
#define rs ( u << 1 | 1 )

struct SegTree {
/* ======================================== */
struct Node { 
    int l, r;
    ll cnt;
} tr[maxn << 2];

void push_up( int u ) {
    tr[u].cnt = tr[ls].cnt + tr[rs].cnt;
}

void build( int u, int l, int r ) {
    tr[u].l = l, tr[u].r = r, tr[u].cnt = 0;
    if( l == r ) return ;
    int mid = ( l + r ) >> 1;
    build( ls, l, mid );
    build( rs, mid + 1, r );
}

void upd( int u, int pos, int val ) {
    if( tr[u].l == tr[u].r ) { 
        tr[u].cnt += val;
        return ;
    }
    int mid = ( tr[u].l + tr[u].r ) >> 1;
    if( pos <= mid ) upd( ls, pos, val );
    else upd( rs, pos, val );
    push_up( u );
}

int ask( int u, int l, int r ) {
    if( l > r ) return 0;
    if( l <= tr[u].l && tr[u].r <= r ) return tr[u].cnt;
    int mid = ( tr[u].l + tr[u].r ) >> 1;
    int res = 0;
    if( l <= mid ) res += ask( ls, l, r );
    if( mid < r ) res += ask( rs, l, r );
    return res;
}

int kth( int u, ll k ) {
    if( tr[u].l == tr[u].r ) return tr[u].l;
    if( tr[ls].cnt >= k ) return kth( ls, k );
    return kth( rs, k - tr[ls].cnt );
}
/* ======================================== */
} seg;

struct Query { int opt, x; };

void solve( ) {
    int n = read( );

    vector<Query> qs( n );
    for( int i = 0; i < n; ++ i ) {
        int t = read( ); int x = read( );
        qs[i] = { t, x };
        if( t != 4 ) disc.add( x );
    }
    disc.init( );

    seg.build( 1, 1, disc.size( ) );
    for( auto [t, x] : qs ) {
        if( t == 1 ) {
            int idx = disc.get_idx( x );
            seg.upd( 1, idx, 1 );
        }
        else if( t == 2 ) {
            int idx = disc.get_idx( x );
            seg.upd( 1, idx, -1 );
        }
        else if( t == 3 ) {
            int idx = disc.get_idx( x );
            int rnk = seg.ask( 1, 1, idx - 1 ) + 1;
            cout << rnk << '\n';
        }
        else if( t == 4 ) {
            int pos = seg.kth( 1, x );
            cout << disc.get_val( pos ) << '\n';
        }
        else if( t == 5 ) {
            int idx = disc.get_idx( x );
            int rnk = seg.ask( 1, 1, idx - 1 );
            int pos = seg.kth( 1, rnk );
            cout << disc.get_val( pos ) << '\n';
        }
        else if( t == 6 ) {
            int idx = disc.get_idx( x );
            int rnk = seg.ask( 1, 1, idx ) + 1;
            int pos = seg.kth( 1, rnk );
            cout << disc.get_val( pos ) << '\n';
        }
    }
}

记录

• 归属：线段树基础理论、[[离散化]]
• 新增：有序多重集的六种操作可以统一为值域计数、前缀计数与线段树第 $k$ 小；离线离散化时还要加入集合中未必存在的查询值。
• 分类：待定