标签：bit   include   mod   void   ffffff   its   inline   build   break   

树套树(splay套线段树) -AcWing 2476

本来想着用multiset套线段树的，结果一直T。改成常数小的splay才过，写完人都傻了^^

/*
 splay套线段树
 */

#include 
using namespace std;

const int N = 5e4+5;
const int M = 1e7+5;
const int INF = 0x3fffffff;

struct SplayNode{
    int s[2],p,v;
    int size;
    void init(int _v,int _p){
        v = _v;
        p = _p;
    }
};


int n,m,op,L,R,X;
int idx;
int root[N tr[u].v];
    }
    u = ++idx;
    if(p) tr[p].s[v > tr[p].v] = u;
    tr[u].init(v, p);
    splay(u, 0, tr_id);
    return u;
}

inline int count_less(int v,int tr_id){
    int u = root[tr_id], cnt = 0;
    while(u){
        if(tr[u].v  v){
            ans = min(ans, tr[u].v);
            u = tr[u].s[0];
        }else{
            u = tr[u].s[1];
        }
    }
    return ans;
}


// seg

void build(int l,int r,int rt){
    insert(-INF, rt);
    insert(INF, rt);
    for(int i = l; i >1;
        build(l, mid, rt= r){
        return count_less(x, rt);
    }else{
        int mid = (l+r)>>1;
        int ans = 0;
        if(ql  mid){
            ans += query_less(mid+1, r, rt>1;
        if(query_less(1, n, 1, ql, qr, mid) >= k){
            r = mid-1;
        }else{
            ans = mid;
            l = mid+1;
        }
    }
    return ans;
}


void modify(int l,int r,int rt,int pos,int v){
    update(arr[pos], v, rt);
    if(l==r){
        arr[pos] = v;
    }else{
        int mid = (l+r)>>1;
        if(pos = r){
        return get_pre(v, rt);
    }else{
        int mid = (l+r)>>1;
        int ans = -INF;
        if(ql  mid){
            ans = max(ans,query_pre(mid+1, r, rt= r){
        return get_suc(v, rt);
    }else{
        int mid = (l+r)>>1;
        int ans = INF;
        if(ql  mid){
            ans = min(ans,query_suc(mid+1, r, rt

树套树(splay套线段树) -AcWing 2476

标签：bit   include   mod   void   ffffff   its   inline   build   break   

原文地址：https://www.cnblogs.com/popodynasty/p/14407264.html