树——查询区间第K大的数————主席树(模板0.5）

川长思鸟来 2024-04-17 16:13 74阅读 0赞

[主席树——>][Link 1]

###### 一、不带修改版模板 ######

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1e5+50;
    int Q, cnt;// Q 表示询问次数， cnt表示结点总数，
    int T[maxn], ls[40*maxn], rs[40*maxn], sum[40*maxn];
    int a[maxn],b[maxn];// a是原数组， b是去重后的数组
    int n, m;// n是a的元素个数 ， m是b的元素个数
    void input()
    { 
        cin>>n>>Q;
        for(int i = 1;i <= n;i++)
        { 
            cin>>a[i];
            b[i] = a[i];
        }
    }
    int build(int l, int r)
    { 
        int now = ++cnt;
        if(l < r)
        { 
            int mid = (l+r)>>1;
            ls[now] = Build(l, mid);// 建立左子树
            rs[now] = Build(mid+1, r);  //建立右子树
        }
        return now;
    }
    
    void Build(int rt, int loc)
    { 
        T[rt] = ++cnt;
        sum[cnt] = sum[T[mark-1]]+1；
        int l = 1, r = m, now = cnt, old = T[mark-1];// old 指向上一棵树
        while(ls[old]||rs[old])// 如果上一棵树的做儿子或者有儿子有一个存在
        { 
            int mid = (l+r)>>1;
            if(loc > mid)// 表示插入的数在右面
            { 
                ls[now] = ls[old];// 左面没变化 直接赋给新树
                rs[now] = ++cnt;// 右儿子开辟新的结点
                sum[rs[now]]  = sum[rs[old]]+1; //因为插入了一个元素， 所以比旧树+1
                now = rs[now]; // 跳右子树， 在进行该操作（本质是一个递归）
                old = rs[old];
                l = mid+1;
            }
            else// 如果插入的数在左面
            { 
                rs[now] = rs[old];
                ls[now] = ++cnt;
                sum[ls[now]] = sum[rs[old]]+1;
                now = ls[now];
                old = ls[old];
                r = mid;
    
            }
    
        }
    
    }
    
    int query(int rt1, int rt2, int l, int r, int k)
    { 
        if(l == r)return l;// 返回这个数
    
        int lm = sum[ls[rt2]] - sum[ls[rt1]]; //lm表示区间[l,r]左半部分元素的个数
        int mid = (l+r)>>1;
    
        if(k<= lm)// 如果k<=lm ， 表示第k大的数 在[l,r]区间的左面
        { 
            return query(ls[rt1],ls[rt2], l, mid, k);// 递归询问左面
        }
        else return query(rs[rt1], rt[rt2], mid+1, r, k-lm) // 否则询问右面, 但是 要减去做做区间lm个元素.
    
    
    }
    
    int main()
    { 
    
        ios_base::sync_with_stdio(false);
        input();
        sort(b+1, b+1+n);
        m = unique(b+1, b+1+n)-(b+1);// 去重操作
        T[0] = build(1, m);// 初始化树
    
        for(int i = 1;i <= n;i++)
        { 
            int loc = lower_bound(b+1, b+1+m, a[i])- b;/****离散化**/
            Build(i, loc);//每插入一个元素， 建立一个新树
        }
    	int x, y, k;
        for(int i = 1;i <= Q;i++)
        { 
            cin>>x>>y>>k;
            int res = query(T[x-1], T[y], 1, m, k);// T[x-1]的树维护区间[1, x-1]的信息， T[y]维护区间[1, y]内的信息
            cout<<b[res]<<endl;
        }
    
        return 0;
    }

[Link 1]: https://blog.csdn.net/qq_39809664/article/details/79934516#commentBox