主席树模板

可持久化线段树 2

题意：

给一数组多次询问一个区间求该区间第k大的数 n和q都可以到达2e5

思路：

每次查询直接暴力找第k大的数肯定会超时然而如果用普通线段树因为每次查询的k不一样就要维护很多棵树会爆空间所以要用主席树

每次更新一个数就添加一个根节点只更新维护的区间中包含当前数的节点其余的点延续上一个根节点维护的线段树

利用前缀和思想：

l r区段的数的个数就是sum[rt[r]] - sum[rt[l - 1]]

#include
#include
#include<string> 
#include<set> 
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define ull unsigned long long
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
#define m_p make_pair
#define pi acos(-1)
using namespace std;
 
const int N = 3e5 + 5;
const double eps = 1e-4;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
inline ll qpow(ll x, ll y, ll M){ll ans=1;while(y){if(y&1)ans=ans*x%M;x=x*x%M;y=y>>1;}return ans;}
inline ll gcd(ll x, ll y){return y?gcd(y,x%y):x;}
int n;
ll a[N], b[N], len, p, m;
ll sum[N << 5], lc[N <<5], rc[N << 5], rt[N << 5], sz;
string s;

//建树 sz记录 节点个数 rt数组 记录每个根节点的编号 
void build(ll &rt, ll l, ll r){
    rt = ++sz;
    sum[rt] = 0;
    if(l == r) return;
    ll mid = (l + r) >> 1;
    build(lc[rt], l, mid);
    build(rc[rt], mid + 1, r);
} 

//更新  
ll update(ll o, ll l, ll r){
    //新建一个点  
    ll oo = ++sz;
    //延续前一个根节点的信息 
    lc[oo] = lc[o];
    rc[oo] = rc[o];
    sum[oo] = sum[o] + 1;
    if(l == r) return oo;
    ll mid = (l + r) / 2;
    if(mid >= p) lc[oo] = update(lc[oo], l, mid);
    else rc[oo] = update(rc[oo], mid + 1, r);
    return oo;//用于递归返回新建点 使更新关系 
}

//询问 
ll query(ll u, ll v, ll l, ll r, ll k){
    ll mid = (l + r) / 2;
    //左区间的个数 
    ll x = sum[lc[v]] - sum[lc[u]];
    if(l == r) return l;
    //多了再往左找 
    if(x >= k) return query(lc[u], lc[v], l, mid, k);
    else return query(rc[u], rc[v], mid + 1, r, k - x); //少了往右找 
}
 
void solve()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        b[i] = a[i];
    }
    //离散化 去重  
    sort(b + 1, b + 1 + n);
    len = unique(b + 1, b + 1 + n) - b - 1;
    //建空树 也可以不建 
    build(rt[0], 1, len);
    for(int i = 1; i <= n; i++){
        //二分查找a[i]再b数组中的位置 
        p = lower_bound(b + 1, b + 1 + len, a[i]) - b;
        rt[i] = update(rt[i - 1], 1, len);
    }
    ll l, r, k;
    while(m--){
        cin >> l >> r >> k;
        ll ans = b[query(rt[l - 1], rt[r], 1, len, k)];
        cout << ans << "\n";
    }
}    
 
signed main()
{
    IOS;
    //init();
    ll t = 1;
    //cin>>t;
    while(t--)
        solve();
    return 0;
}

线段树

主席树模板

可持久化线段树 2

相关

#直径，线段树#51nod 1766 树上的最远点对

「NOI2020」命运（树形DP+线段树合并）

线段树学习笔记 1

关于线段树的一些认识

线段树

[NOI2015]软件包管理器（巧用线段树）

P6242 【模板】线段树 3

P5494 【模板】线段树分裂

CF1557D Ezzat and Grid（线段树）

cf739 C. Alyona and towers（线段树）

可持久化线段树

Codeforces Round #625 Div1 C,二维偏序，排序+线段树

标签