JZTXT

可持久化线段树模板 区间第k小数,区间前k大数之和

发布时间 2023-04-30 01:11:39作者: magicat

第K小数

//  AC one more times

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define inf64 0x3f3f3f3f3f3f3f3f

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<long long,long long> pll;

const int mod = 998244353;
const int N = 5e5 + 10;

struct segtree
{
	int l, r, s;
}seg[N * 30];

vector<int> vx; 
int n, q, a[N], rt[N], tot;

void update(int id)
{
	seg[id].s = seg[seg[id].l].s + seg[seg[id].r].s;
}

int build(int l, int r)
{
	int id = ++tot;
	if(l == r)
		return id;
	int mid = (l + r) >> 1;
	seg[id].l = build(l, mid);
	seg[id].r = build(mid + 1, r);
	return id; 
}

int change(int u, int l, int r, int pos)
{
	int id = ++tot;
	seg[id] = seg[u];
	if(l == r)	
	{
		seg[id].s++;
		return id;
	}
	int mid = (l + r) >> 1;
	if(pos <= mid)
		seg[id].l = change(seg[u].l, l, mid, pos);
	else
		seg[id].r = change(seg[u].r, mid + 1, r, pos);
	update(id);
	return id;
}

int query(int v, int u, int l, int r, int x)
{
	if(l == r)
		return l;
	int cnt = seg[seg[u].l].s - seg[seg[v].l].s;
	int mid = (l + r) >> 1;
	if(x <= cnt)
		return query(seg[v].l, seg[u].l, l, mid, x);
	else
		return query(seg[v].r, seg[u].r, mid + 1, r, x - cnt);		
}

void solve()
{   
	cin>>n>>q;
	for(int i = 1; i <= n; i++)
	{
		cin>>a[i];
		vx.push_back(a[i]);
	}
	sort(vx.begin(), vx.end());
	vx.erase(unique(vx.begin(), vx.end()), vx.end());
	rt[0] = build(1, vx.size());
	for(int i = 1; i <= n; i++)
		rt[i] = change(rt[i - 1], 1, vx.size(), lower_bound(vx.begin(), vx.end(), a[i]) - vx.begin() + 1);
	
	while(q--)
	{
		int l, r, k;	cin>>l>>r>>k;
		cout<<vx[query(rt[l - 1], rt[r], 1, vx.size(), k) - 1]<<endl;
	}		
}

  
int main()
{
    std::ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    
    int TC = 1;
    
    //cin >> TC;    
    for(int tc = 1; tc <= TC; tc++)
    {
        //cout << "Case #" << tc << ": ";         
        solve();
    }


    return 0;
}

区间前k大数之和（待施工）