Overall dichotomy?

The whole score is two points.

  Last time $CDQ$ Divide and conquer has not been written yet , Now let's write the whole dichotomy qwq.

A brief introduction

  wss： As the name suggests, the whole dichotomy is the dichotomy of the whole .

  say concretely , If these conditions are met , We can consider using the whole dichotomy to solve this problem ：

1. Multiple sets of asking
2. Every question can be solved with a two-point answer
3. The answer can be contributed in batches

  This third point may be a little abstract , It may be better to understand with specific topics later , So I won't explain too much here .

Take a look at a simple topic

  Portal ：luogu1533 Poor dog

The main idea of the topic

  Give you a sequence （ Each number is not equal ）, Give you a question every time , Ask you the interval number $k$ Small .

analysis

  Isn't this a board , Direct chairman tree （ Balance tree is also ok qwq） Walk up .

  Today we are going to learn the whole dichotomy , So take a moment , Let's take a look at the analysis idea of overall dichotomy .

  First , Let's see if the above three conditions are satisfied . First, the first condition , Obviously satisfied （ There should be no explanation ）. Then there is the second condition , Also obviously satisfied . Let's consider such a binary answer , Divide one in two on the value range $mid$.$check$ Scan the array once when you are ready , Sweep appears when it is less than $mid$ The number of $res$. If $res=k-1$, that $ans=mid$, Just came out . If $res<k-1$ that $l=mid$, If $res>k-1$, that $r=mid$. In this way, the complexity of each inquiry is obviously $O(n\log n)$ Of , So the total complexity is $O(nm\log n)$ Of .

  Then there is the third condition , The answer can be contributed in batches , How to understand specifically , Let's consider the process of dichotomy .

  First we find one $mid$, It is found that this array is less than $mid$ The number of $res<k-1$ individual , Then it means that the answer we ask for is better than $mid$ Big . So we put $l=mid$, Keep bisection . This is a very normal step in the two-point answer , Right , If it's still a normal two-point answer , We will repeat this process until we find $res=k-1$ until . But let's consider another approach ：

  We have $res$ The number is less than $mid$, And the number we will divide in two next time $mi{d}^{\prime }$ Yes $re{s}^{\prime }$ The number is less than $mi{d}^{\prime }$, Then there is $re{s}^{\prime }optk-1$, Then we subtract from both sides of the equation at the same time $res$, That is to say $re{s}^{\prime }-resoptk-1-res$.

  Now the left formula means less than $mi{d}^{\prime }$ Less than $mid$ The number of , It's satisfaction $a_i\in [mid,mi{d}^{\prime })\wedge i\in [l,r]$ The number of . Then this number should be compared with the number we originally want to compare $k-1$, Subtract the number we find in the middle $res$ Got $k-1-res$ Compare . This is the meaning of batch contribution , Here we need to pay attention to , The contribution in batches we mentioned only refers to the contribution of the left side to the right , Imagine if our first $mid$ Of $res$ Greater than $k-1$ Then the above operations cannot be carried out , So only consider the contribution of left to right .

  So this problem can be done with integral dichotomy What a painful process qwq.

  First of all, because the title doesn't say the range of weights , So let's discretize it . Then we take all inquiries offline , Save it in an array , Just like this. ：

  Every point on the left is a question , For the first $i$ Questions will include $l_i,r_i$ and $k_i$, Then we will dichotomy on the value range , Now we have one in two $mid$, Then we can quickly query how many numbers are less than $mid$, We put less than... In the original array $mid$ The number of is added to a tree array （ Value range plus one ）, So we can quickly query the interval $[l,r]$ How many numbers in are less than $mid$ 了 .

  Then we consider making a query for each query , I found that there are $re{s}_i$ The number satisfies $a_i\in [1,mid\wedge i\in [l,r])$. Then take $re{s}_i$ and $k_i-1$ Make a comparison .

  Then this is the key step of overall dichotomy , The results of the comparison can be divided into two categories ：

1. $re{s}_i\ge k_i+1$, For this part, ask , We classify them into the first category .
2. $re{s}_i<k_i+1$, For this part, ask , We classify them into the second category .

  Then we do the following for these two kinds of inquiries ：

1. The first kind of inquiry , Put it on “ On the left ”, Whatever it is .
2. The second kind of inquiry , Put it on “ On the right ”, also $k_i-=re{s}_i$.

  The purpose of doing this is actually the same as our intention of analyzing the third conditional answer batch contribution above , In this way, we continue to divide downward , Continue processing , Until finally, there is only one question in each category , Then we can return to the answer we worked out （ What you don't understand can be compared with merging and sorting ）.

Code

#include<bits/stdc++.h>
using namespace std;
#define in read()
#define MAXN 300300
#define MAXM 50050

inline int read(){
    
	int x = 0; char c = getchar();
	while(c < '0' or c > '9') c = getchar();
	while('0' <= c and c <= '9'){
    
		x = x * 10 + c - '0'; c = getchar(); 
	}
	return x;
}

int a[MAXN] = {
     0 };
int b[MAXN] = {
     0 };
int n = 0; int m = 0;
int id[MAXN] = {
     0 };
int q1[MAXN] = {
     0 };
int q2[MAXN] = {
     0 };
int pos[MAXN] = {
     0 };
int ans[MAXN] = {
     0 };
struct Tque{
    
	int k;
	int l, r;
}q[MAXM];

int c[MAXN << 2] = {
     0 };
inline int lowbit(int x) {
     return x & -x; }
void add(int x, int y) {
     for(; x <= n; x += lowbit(x)) c[x] += y; }
int query(int x){
    
	int ans = 0;
	for(; x; x -= lowbit(x)) ans += c[x];
	return ans;
}

void solve(int l, int r, int ql, int qr){
    
	if(l == r){
    
		for(int i = ql; i <= qr; i++) ans[id[i]] = l;
		return;
	}
	int mid = (l + r) >> 1; int cnt1 = 0, cnt2 = 0, res;
	for(int i = l; i <= mid; i++) add(pos[i], 1);
	for(int i = ql; i <= qr; i++){
    
		res = query(q[id[i]].r) - query(q[id[i]].l - 1);
		if(res >= q[id[i]].k) q1[++cnt1] = id[i];
		else q[id[i]].k -= res, q2[++cnt2] = id[i];
	}
	for(int i = l; i <= mid; i++) add(pos[i], -1);          //  revoke 
	for(int i = 1; i <= cnt1; i++) id[i + ql - 1] = q1[i];
	for(int i = 1; i <= cnt2; i++) id[i + ql - 1 + cnt1] = q2[i];
	solve(l, mid, ql, cnt1 + ql - 1), solve(mid + 1, r, cnt1 + ql, qr); 
}

int main(){
    
	n = in; m = in;
	for(int i = 1; i <= n; i++) b[i] = a[i] = in, id[i] = i;
	for(int i = 1; i <= m; i++) q[i].l = in, q[i].r = in, q[i].k = in;
	sort(b + 1, b + n + 1);
	int k = unique(b + 1, b + n + 1) - b - 1;
	for(int i = 1; i <= n; i++)
		a[i] = lower_bound(b + 1, b + k + 1, a[i]) - b, pos[a[i]] = i;
	solve(1, n, 1, m);
	for(int i = 1; i <= m; i++) cout << b[ans[i]] << '\n';
	return 0;
}