Overall dichotomy

The overall dichotomy without repair is offline, which is not very useful except that it takes up a small space. But... You can't imagine whether the person who makes the question will block your space, so let's have a look

Pre knowledge

• Two point answer
• Tree array
• Divide and conquer

First of all, those who can split the whole must meet the following conditions:

1. For a single sub problem, you can use a two-point answer to solve the problem
2. The title is offline, not forced online
3. The contribution of sub questions to the answer can be superimposed

Next, let's move on to the main topic (those who don't have two answers can learn first and then look at it)
First, let's look at a problem (Luogu p3834)

Considering the processing of a query, we think of a binary answer. Not only that, in this question, all queries are offline, so we can try the overall binary answer.
(the following picture is the idea given by oi wiki)

The so-called overall dichotomy is to dichotomize the answers to all questions. For example, in this question, the value of our first dichotomy is 15770 (assuming), so we put all positions less than or equal to 15770 (in fact, the positions of the values between the dichotomous interval [l, mid], because of the divide and conquer writing method, we can ensure that the current query is greater than l) Add 1 to all of them, and then when we ask for a single query, we can find a prefix sum according to the query interval, and then we can know how many numbers are less than or equal to 15770 in this interval (set as x) , when x is greater than or equal to the K of the query, it means that the answer of the query is less than the value of the current dichotomy, then the query should be placed in the left section of the next overall dichotomy answer, otherwise, it should be placed in the right section, and the current query should be changed to the k - x largest (because the contribution additivity is satisfied). We use a tree array for the prefix sum.
(if you don't understand, you can understand it by looking at the next simulation.)
//
For convenience, the sample is regarded as discrete data, that is
5 5
3 1 2 4 5
Ask for the first three
2 2 1
3 4 1
4 5 1
//

Finally, paste the code
//The complexity of this thing is also nlogn. It runs like the chairman tree

#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back


using namespace std;
using ll = long long;
using pii = pair<int, int>;


const int maxn = 2e5 + 10;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;

struct Query
{
    int type, l, r, k, id;
    Query(int b, int c, int d, int e)
    {
        type = 1, l = b, r =  c, k = d, id = e;
    }
    Query(int a, int b)
    {
        type = 0, l = r = a, k = b, id = 0;
    }
    Query(){}
}q[maxn << 1], ql[maxn << 1], qr[maxn << 1];

int n, m;
int tree[maxn], ans[maxn];

int lowbit(int x)
{
    return (x & (-x));
}

int sum(int num)
{
    int ans = 0;
    while (num)
    {
        ans += tree[num];
        num -= lowbit(num);
    }
    return ans;
}

void add(int num, int val)
{
    while (num <= n)
    {
        tree[num] += val;
        num += lowbit(num);
    }
}

void solve(int l, int r, int lef, int rig)
{
    if (lef > rig) return;
    int i;
    if (l == r)
    {
        for (i = lef; i <= rig; i++)
            if (q[i].type) ans[q[i].id] = l;
        return ;
    }
    int mid = l + r >> 1, cnt1 = 0, cnt2 = 0;
    for (i = lef; i <= rig; i++)
    {
        if (!q[i].type)
        {
            if (q[i].k <= mid)
            {
                add(q[i].l, 1);
                ql[++cnt1] = q[i];
            }
            else qr[++cnt2] = q[i];
            continue;
        }
        int x = sum(q[i].r) - sum(q[i].l - 1);
        if (x >= q[i].k)
            ql[++cnt1] = q[i];
        else
        {
            q[i].k -= x;
            qr[++cnt2] = q[i];
        }
    }
    for (i = 1; i <= cnt1; i++)
        if (!ql[i].type) add(ql[i].l, -1);
    for (i = 1; i <= cnt1; i++)
        q[i] = ql[i];
    for (i = 1; i <= cnt2; i++)
        q[i + cnt1] = qr[i];
    solve(l, mid, 1, cnt1);
    solve(mid + 1, r, cnt1 + 1, cnt1 + cnt2);
}

pii a[maxn];
int val[maxn];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    int i, j;
    for (i = 1; i <= n; i++)
        cin >> a[i].first, a[i].second = i;
    sort(a + 1, a + 1 + n);

    int cnt = 0;
    a[0].first = 1e9;
    for (i = 1; i <= n; i++)
    {
        if (a[i].first != a[i - 1].first)
            q[i] = Query(a[i].second, ++cnt), val[cnt] = a[i].first;
        else
            q[i] = Query(a[i].second, cnt);
    }

    int l, r, k;
    for (i = 1; i <= m; i++)
    {
        cin >> l >> r >> k;
        q[i + n] = Query(l, r, k, i);
    }
    solve(1, cnt, 1, n + m);
    for (i = 1; i <= m; i++)
        cout << val[ans[i]] << endl;
}

Combined with the code, it is estimated that it is OK