P1533 && P3834 (整体二分)

#include <iostream>
#include <algorithm>
using namespace std;
constexpr int maxn = 2e5 + 10;
int n, m, cnt;
int ans[maxn], a[maxn], c[maxn];
pair <int, int> b[maxn];
struct query {
	int l, r, k, id, type;
} e[maxn << 1], A1[maxn << 1], A2[maxn << 1];
struct Tree {
	int sum[maxn];
	#define lowbit(x) x & -x
	inline void update (int x, int k) { while (x <= n) sum[x] += k, x += lowbit(x); }
	inline int query (int x) {
		int res = 0;
		while (x) res += sum[x], x -= lowbit(x);
		return res;
	}
} tree;
inline void solve (int l, int r, int bl, int br) {
	if (bl > br) return;
	if (l == r) {
		for (int i = bl; i <= br; i ++)
			if (e[i].type == 2) ans[e[i].id] = l;
		return;
	}
	int mid = l + r >> 1;
	int cnt1 = 0, cnt2 = 0;
	for (int i = bl; i <= br; i ++) {
		if (e[i].type == 1) {
			if (e[i].l <= mid) A1[++ cnt1] = e[i], tree.update(e[i].id, 1);
			else A2[++ cnt2] = e[i]; 
		} else if (e[i].type == 2) {
			int res = tree.query(e[i].r) - tree.query(e[i].l - 1);
			if (res >= e[i].k) A1[++ cnt1] = e[i];
			if (res < e[i].k) A2[++ cnt2] = e[i], A2[cnt2].k -= res;  
		}
	}
	for (int i = bl; i <= br; i ++)
		if (e[i].type == 1 && e[i].l <= mid) tree.update(e[i].id, -1);
	for (int i = 1; i <= cnt1; i ++) e[bl + i - 1] = A1[i];
	for (int i = 1; i <= cnt2; i ++) e[bl + cnt1 + i - 1] = A2[i];
	solve(l, mid, bl, bl + cnt1 - 1), solve(mid + 1, r, bl + cnt1, br);
}
int main () {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	cin >> n >> m;
	for (int i = 1; i <= n; i ++)
		cin >> a[i], b[i].first = c[i] = a[i], b[i].second = i;
	sort(b + 1, b + n + 1);
	for (int i = 1; i <= n; i ++) a[b[i].second] = i;
	for (int i = 1; i <= n; i ++) e[++ cnt] = (query){a[i], 1, 1, i, 1};
	for (int i = 1; i <= m; i ++) {
		cin >> e[++ cnt].l >> e[cnt].r >> e[cnt].k;
		e[cnt].type = 2, e[cnt].id = i;
	}
	solve(1, n, 1, cnt);
	for (int i = 1; i <= m; i ++) cout << c[b[ans[i]].	second] << '\n';
	return 0;
}

（错误的代码，样例错误）

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int n , m , cnt;
int ans[maxn] ,  a[maxn] , c[maxn];
pair<int , int> b[maxn];

struct edge
{
    int x , y , k , id , type;
}e[maxn * 2] , a1[maxn * 2] , a2[maxn * 2];

inline int read()
{
    int asd = 0, qwe = 1; char zxc;
    while (!isdigit(zxc = getchar())) if (zxc == '-') qwe = -1;
    while (isdigit(zxc)) asd = asd * 10 + zxc - '0', zxc = getchar();
    return asd * qwe;
}

inline void solve(int l , int r , int ql , int qr);

int main()
{
    n = read() , m = read();
    
    for(int i = 1;i <= n;i++)
        b[i].first = c[i] = a[i] = read() , b[i].second = i;
    
    sort(b + 1 , b + n + 1);
    
    for(int i = 1;i <= n;i++) a[b[i].second] = i;
    for(int i = 1;i <= n;i++) e[++cnt] = (edge){a[i] , 1 , 1 , i , 1};

    for(int i = 1;i <= m;i++)
    {
        e[++cnt].x = read() , e[cnt].y = read();
        e[cnt].k = read() , e[cnt].type = 2 , e[cnt].id = i;
    }
    // return 0;
    solve(1 , n , 1 , cnt);

    for(int i = 1;i <= m;i++)
        printf("%d\n" , c[b[ans[i]].second]);
    return 0;
}

struct Tree
{
    int sum[maxn];
    
    inline int lowbit(int x) { return x & (-x); }
    inline void update(int x , int y) { while(x <= n) sum[x] += y , x += lowbit(x); }
    inline int ask(int x) { int res = 0; while(x) res += sum[x] , x -= lowbit(x); return res; }

}t;

inline void solve(int l , int r , int ql , int qr)
{
    if(ql > qr) return;
    
    if(l == r)
    {
        for(int i = ql;i <= qr;i++)
            if(e[i].type == 2) ans[e[i].id] = l;
        return;
    }

    int mid = (l + r) >> 1;
    int cnt1 = 0 , cnt2 = 0;
    
    for(int i = ql;i <= qr;i++)
    {
        if(e[i].type == 1)
        {
            if(e[i].x <= mid) a1[++cnt1] = e[i] , t.update(e[i].id , 1);
            else a2[++cnt2] = e[i];
        }
        
        if(e[i].type == 2)
        {
            
            int res = t.ask(e[i].y) - t.ask(e[i].x - 1);
            if(res >= e[i].k) a1[++cnt1] = e[i];
            if(res < e[i].k) a2[++cnt2] = e[i] , a2[cnt2].k -= res;
        }
    }
    
    for(int i = ql;i <= qr;i++)
        if(e[i].type == 1 && e[i].x <= mid) t.update(e[i].id , -1);

    for(int i = 1;i <= cnt1;i++) e[ql + i - 1] = a1[i];
    for(int i = 1;i <= cnt2;i++) e[ql + cnt1 + i - 1] = a2[i];
    
    solve(l , mid , ql , ql + cnt1 - 1);
    solve(mid + 1 , r , ql + cnt1 , qr);
}

(正确的代码)