主席树 常见题目类型总结(未完待续)

😊 | Powered By HeartFireY

一、 主席树维护区间第K大 📕 | Require：主席树

主席树最基础的应用，对于给定的序列建立权值数组，对于每个元素建立一棵主席树，维护 [ 1 , n ] [1,n] [1,n]的数字个数(前缀和)。查询时在树上二分查找。对于当前节点判断左子树的节点个数是否满足比 k k k大，如果满足则向左递归查询，否则减去左子树节点个数向右子树递归查询。

#include 
using namespace std;

const int N = 2e5 + 10;

int a[N], b[N], n, m;
int root[N], tot;
int lc[N  n >> m;
    for(int i = 1; i > a[i];
        b[i] = a[i];
    }
    sort(b + 1, b + 1 + n);
    int n_1 = unique(b + 1, b + 1 + n) - (b + 1);
    for(int i = 1; i  l >> r >> k;
        cout r, i∈[l,r]，那么表示与 
     
      
       
       
         i 
        
       
      
        i 
       
      
    i相同数字点位于区间之外。那么求不同数字个数问题便转化为给定求所有满足 
     
      
       
       
         l 
        
       
         < 
        
       
         = 
        
       
         i 
        
       
         < 
        
       
         = 
        
       
         r 
        
       
         , 
        
       
           
        
       
         n 
        
       
         x 
        
       
         t 
        
       
         [ 
        
       
         i 
        
       
         ] 
        
       
         > 
        
       
         r 
        
       
      
        l a[i]; b[i] = a[i];
        }
        sort(b + 1, b + 1 + n);
        ll sz = unique(b + 1, b + 1 + n) - b - 1;
        for(int i = 1; i > 1;
        cout = k) return query(tree[u.lc], tree[v.lc], tree[lca.lc], tree[lca_fa.lc], l, mid, k);
    return query(tree[u.rc], tree[v.rc], tree[lca.rc], tree[lca_fa.rc], mid + 1, r, k - sum);
}

inline void dfs(int u, int fa){
    update(tree[root[fa]], tree[root[u] = ++cnt], 1, le, id(u));
    f[u][0] = fa;
    dep[u] = dep[fa] + 1;
    for(register int i = 1; i = dep[v]) u = f[u][i];
    if(u == v) return u;
    for(register int i = 18; i >= 0; i--)
        if(f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
    return f[u][0];
}

inline int querypath(int u, int v, int k){
    int lcaa = lca(u, v);
    return rid(query(tree[root[u]], tree[root[v]], tree[root[lcaa]], tree[root[f[lcaa][0]]], 1, le, k));
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    //freopen("stdin.in", "r", stdin);
    //freopen("stdout.out", "w", stdout);
    cin >> n >> m;
    for(register int i = 1; i > a[i]; b[i] = a[i]; }
    for(register int i = 1, u, v; i > u >> v;
        g[u].push_back(v), g[v].push_back(u);
    }
    sort(b + 1, b + 1 + n);
    le = unique(b + 1, b + n + 1) - (b + 1);
    build(tree[root[0] = ++cnt], 1, le);
    dfs(1, 0);
    while(m--){
        int u, v, k; cin >> u >> v >> k;
        ans = querypath(u ^ lastans, v, k);
        cout > v; g[u].push_back(v), g[v].push_back(u); } sort(b + 1, b + 1 + n); le = unique(b + 1, b + n + 1) - (b + 1); build(tree[root[0] = ++cnt], 1, le); dfs(1, 0); while(m–){ int u, v, k; cin >> u >> v >> k; ans = querypath(u ^ lastans, v, k); cout