[NBUT 1458 Teemo]区间第k大问题，划分树

裸的区间第k大问题，划分树搞起。

#pragma comment(linker, "/STACK:10240000")

#include <map>

#include <set>

#include <cmath>

#include <ctime>

#include <deque>

#include <queue>

#include <stack>

#include <vector>

#include <cstdio>

#include <string>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define X                   first

#define Y                   second

#define pb                  push_back

#define mp                  make_pair

#define all(a)              (a).begin(), (a).end()

#define fillchar(a, x)      memset(a, x, sizeof(a))

#define fillarray(a, b)     memcpy(a, b, sizeof(a))

typedef long long ll;

typedef pair<int, int> pii;

typedef unsigned long long ull;

#ifndef ONLINE_JUDGE

void RI(vector<int>&a,int n){a.resize(n);for(int i=;i<n;i++)scanf("%d",&a[i]);}

void RI(){}void RI(int&X){scanf("%d",&X);}template<typename...R>

void RI(int&f,R&...r){RI(f);RI(r...);}void RI(int*p,int*q){int d=p<q?:-;

while(p!=q){scanf("%d",p);p+=d;}}void print(){cout<<endl;}template<typename T>

void print(const T t){cout<<t<<endl;}template<typename F,typename...R>

void print(const F f,const R...r){cout<<f<<", ";print(r...);}template<typename T>

void print(T*p, T*q){int d=p<q?:-;while(p!=q){cout<<*p<<", ";p+=d;}cout<<endl;}

#endif

template<typename T>bool umax(T&a, const T&b){return b<=a?false:(a=b,true);}

template<typename T>bool umin(T&a, const T&b){return b>=a?false:(a=b,true);}

const double PI = acos(-1.0);

const int INF = 1e9 + ;

const double EPS = 1e-12;

/* -------------------------------------------------------------------------------- */

const int maxn = 1e5 + ;

/** 过程：快排的过程，通过记录进入左子区间的个数的前缀和来解决区间第k大问题 **/

class PartitionTree {

    int cnt[][maxn], val[][maxn], buf[maxn];

    int n;

    void init(int a[], int n) {

        this->n = n;

        fillchar(cnt, );

        fillchar(val, );

        fillarray(val[], a);

        fillarray(buf, a);

        sort(buf, buf + n);

    }

    void build(int l, int r, int dep) {

        if (l == r) return ;

        int m = (l + r) >> , c = , small = ;

        for (int i = l; i <= r; i ++) small += val[dep][i] < buf[m];

        for (int i = l; i <= r; i ++) {

            if (c < m - l + ) {

                if (val[dep][i] < buf[m] || val[dep][i] == buf[m] && small < m - l + ) {

                    cnt[dep][i] = ;

                    val[dep + ][l + c ++] = val[dep][i];

                    small += val[dep][i] == buf[m];

                }

            }

            else break;

        }

        for (int i = l; i <= r; i ++) {

            if (!cnt[dep][i]) val[dep + ][l + c ++] = val[dep][i];

        }

        build(l, m, dep + );

        build(m + , r, dep + );

    }

    /** 第k小 */

    int querykth(int L, int R, int k, int l, int r, int dep) {

        if (k <=  || k > R - L + ) return - ;

        if (L == R) return val[dep][L];

        int m = (l + r) >> , cl = cnt[dep][L - ] - cnt[dep][l - ], cr = cnt[dep][R] - cnt[dep][l - ];

        if (cr - cl >= k) return querykth(l + cl, l + cr - , k, l, m, dep + );

        return querykth(m +  + L - l - cl, m + R - l +  - cr, k - cr + cl, m + , r, dep + );

    }

public:

    void build(int a[], int n) {

        init(a, n);

        build(, n, );

        for (int i = ; i < ; i ++) {

            for (int j = ; j <= n; j ++) {

                cnt[i][j] += cnt[i][j - ];

            }

        }

    }

    int querykth(int L, int R, int k) { return querykth(L, R, k, , n, ); }

};/** 下标从1开始 */

PartitionTree pt;

int a[maxn];

int main() {

#ifndef ONLINE_JUDGE

    freopen("in.txt", "r", stdin);

    //freopen("out.txt", "w", stdout);

#endif // ONLINE_JUDGE

    int n, m;

    while (cin >> n >> m) {

        for (int i = ; i <= n; i ++) {

            scanf("%d", a + i);

        }

        pt.build(a, n);

        int l, r, k;

        for (int i = ; i < m; i ++) {

            scanf("%d%d%d", &l, &r, &k);

            printf("%d\n", pt.querykth(l, r, k));

        }

    }

    return ;

}