rt，有时AC有时TLE#10

#include <bits/stdc++.h>
using namespace std;

inline void train() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

constexpr int N = 2e5+4;

vector<long long> assigner;
vector<long long>::iterator ae;

// Persistent array, allowing single-point update and multi-point query:
// NOTICE THAT FOR ALL QUESTIONS YOU NEED TO MODIFY THIS.

// Another example: Dynamically Construct Something

template <typename Ty>
inline int maxi(Ty a, Ty b) {
    return a > b ? a : b;
}

template <typename Ty>
inline int mini(Ty a, Ty b) {
    return a < b ? a : b;
}

template <typename data, int size, int maxsize>
class persistant_array {
    public:

        struct array_node {
            data storage;
            int lnode, rnode, lref, rref;
        };

        // [S Raise To-Do after 2 templates: Add range modifier.]
        void update(int version, int ver_origin, int where, data value) {
            // Emplace a root if needed or insert
            if (!version_src.count(version)) {
                version_src[version] = emplace_for(1, ns, version_src[ver_origin]);
#ifndef ONLINE_JUDGE
                cerr << "Creating version " << version << endl;
#endif // ONLINE_JUDGE
                update_internal(version_src[version], version_src[ver_origin], where, value);
            } else {
                cerr << "Update error: Version " << version << " already exists" << endl;
                throw exception();
            }
        }

        data query(int version, int where) {
            if (version_src.count(version)) {
                return query_internal(version_src[version], where);
            } else {
                cerr << "Update error: Version " << version << " not exist" << endl;
                throw exception();
            }
        }

        data query(int version, int l, int r) {
            if (version_src.count(version)) {
                return query_internal(version_src[version], l, r);
            } else {
                cerr << "Update error: Version " << version << " not exist" << endl;
                throw exception();
            }
        }

        void copy_version(int version, int origin) {
            //version_src[version] = version_src[origin];
            version_src[version] = emplace_for(1, ns, version_src[origin]);
        }

/*
        persistant_array(function<data,data&> pushdown, function<data,data,data&> pushup, data default_val)
            : pushdown(pushdown), pushup(pushup), default_val(default_val) {
            version_src[0] = build(1, size, default_val);
        }
*/

        /*
        void construct(data *origins, int n = size) {
            this->origins = origins;
            ns = n;
            version_src[0] = build(1, n);
        }
        */


        void construct(data default_val, int n = size) {
            this->default_val = default_val;
            ns = n;
            version_src[0] = build(1, n, default_val);
        }

        persistant_array() : default_val(data()) {

        }


    private:
        array_node stree[maxsize];


        int build(int l, int r, data default_val) {
            if (l > r) return -1;
            int my = assigner++;
            stree[my].lnode = l;
            stree[my].rnode = r;
            if (l == r) {
                stree[my].storage = default_val;
                return my;
            }
            int mid = (l+r) >> 1;
            int ls = stree[my].lref = build(l, mid, default_val);
            int rs = stree[my].rref = build(mid+1, r, default_val);
            pushup(stree[ls].storage, stree[rs].storage, stree[my].storage);
            return my;
        }

        /*
        int build(int l, int r) {
            if (l > r) return -1;
            int my = assigner++;
            stree[my].lnode = l;
            stree[my].rnode = r;
            if (l == r) {
                //stree[my].storage = default_val;
                stree[my].storage = origins[l];
                return my;
            }
            int mid = (l+r) >> 1;
//            stree[my].lref = build(l, mid, default_val);
            int ls = stree[my].lref = build(l, mid);
//            stree[my].rref = build(mid+1, r, default_val);
            int rs = stree[my].rref = build(mid+1, r);
            pushup(stree[ls].storage, stree[rs].storage, stree[my].storage);
            return my;
        }
        */

        int emplace_for(int l, int r, int origin) {
            int my = assigner++;
            stree[my].lnode = l;
            stree[my].rnode = r;
            //stree[my].storage = default_val;
            stree[my].storage = stree[origin].storage;  // ** TO MODIFY **
            stree[my].lref = stree[origin].lref;
            stree[my].rref = stree[origin].rref;
            return my;
        }

        void update_internal(int root, int origin, int where, data value) {
            if (stree[root].lnode == where && stree[root].rnode == where) {
                stree[root].storage += value;
#ifndef ONLINE_JUDGE
                cerr << "Modifying " << where << " as " << value << endl;
#endif // ONLINE_JUDGE
                return;
            }
            int mid = (stree[root].lnode + stree[root].rnode) >> 1;
            if (where <= mid) {
                stree[root].lref = emplace_for(stree[root].lnode, mid, stree[origin].lref);
                //pushdown(stree[root].storage, stree[stree[root].lref].storage);
                update_internal(stree[root].lref, stree[origin].lref, where, value);
            } else {
                stree[root].rref = emplace_for(mid+1, stree[root].rnode, stree[origin].rref);
                //pushdown(stree[root].storage, stree[stree[root].rref].storage);
                update_internal(stree[root].rref, stree[origin].rref, where, value);
            }

            pushup(stree[stree[root].lref].storage, stree[stree[root].rref].storage, stree[root].storage);
#ifndef ONLINE_JUDGE
            cerr << "Pushup [" << stree[root].lnode << "," << stree[root].rnode << "] = " << stree[root].storage << endl;
#endif // ONLINE_JUDGE
        }

        data query_internal(int root, int where) {
            if (stree[root].lnode == where && stree[root].rnode == where) {
                return stree[root].storage;
            }
            int mid = (stree[root].lnode + stree[root].rnode) >> 1;
            if (where <= mid) {
                return query_internal(stree[root].lref, where);
            } else {
                return query_internal(stree[root].rref, where);
            }
        }

        data query_internal(int root, int l, int r) {
            if (l > r) return this->default_val;
            if (stree[root].lnode >= l && stree[root].rnode <= r) {
                return stree[root].storage;
            }
            int mid = (stree[root].lnode + stree[root].rnode) >> 1;
            data fin;
            data lq = query_internal(stree[root].lref, maxi(l, stree[root].lnode), mini(mid, r));
            data rq = query_internal(stree[root].rref, maxi(mid+1, l), mini(stree[root].rnode, r));
            pushup(lq, rq, fin);
            return fin;
        }

        //function<data,data&> pushdown;

        //function<data,data,data&> pushup;
        void pushup(data left, data right, data &root) {
            root = left + right;
        }


        unordered_map<int, int> version_src;

        int assigner = 0, ns;
        data default_val;
        //data *origins;
};

// End.

int n, m, a[N];
persistant_array<int, N, int(4e6)> ptree;

// [l, r]
inline int fetch_value_for(int l, int r, int rel) {
    //int rel = lower_bound(assigner.begin(), ae, pos) - assigner.begin() + 1;
    //eturn ptree.query(r, rel) - ptree.query(l-1, rel);
    auto rp = ptree.query(r, 1, rel), lp = ptree.query(l-1, 1, rel);
#ifndef ONLINE_JUDGE
    cerr << "fetch [" << l << "," << r <<"] for " << rel << ": " << rp << "-" << lp << endl;
#endif // ONLINE_JUDGE
    return rp-lp;
}

int main() {
    train();

    cin>>n>>m;
    for (int i = 1; i <= n; i++) {
        cin>>a[i];
        assigner.push_back(a[i]);
    }
    sort(assigner.begin(), assigner.end());
    ae = unique(assigner.begin(), assigner.end());
    size_t dsz = ae - assigner.begin();
    ptree.construct(0, dsz);
    for (int i = 1; i <= n; i++) {
        int rel = lower_bound(assigner.begin(), ae, a[i]) - assigner.begin() + 1;
#ifndef ONLINE_JUDGE
        cerr << "Update at " << rel << endl;
#endif // ONLINE_JUDGE
        ptree.update(i, i-1, rel, 1);
#ifndef ONLINE_JUDGE
        cerr << "END -- Update at " << rel << endl;
#endif // ONLINE_JUDGE
    }
    for (int qs = 0; qs < m; qs++) {
        int l,r,k;
        cin>>l>>r>>k;
        int al = -1, ar = dsz+1;
        while (al+1<ar) {
            int mid = (al + ar) >> 1;
            // Check mid.
            int res = fetch_value_for(l, r, mid + 1);
#ifndef ONLINE_JUDGE
            cerr << "Reaching " << mid << " (number " << assigner[mid] << ") has " << res << " number(s)" << endl;
#endif // ONLINE_JUDGE

            if (res >= k) {
                // Too large
                ar = mid;
            } else {
                al = mid;
            }
        }
        cout<<assigner[ar]<<'\n';
    }

    cout<<flush;
    return 0;
}