整体二分

个人认为就是爆改cdq。

大体思路和 cdq 相同：

• 每次递归传入操作集合 op 和区间 \([l,r]\)，表示修改操作的修改位置以及查询操作的答案都位于 \([l,r]\) 内$；
• 统计左区间修改对全区间查询的贡献；
• 判断查询应下放到左右哪个区间；
• 分割操作至左右两区间

例题

海亮 OJ 题单

P3834 【模板】可持久化线段树 2

#include<iostream>
#include<vector>
using namespace std;
const int N = 2E5 + 10;
const int A = 1e9;

struct Op {
	int x, y, k;
	int id, tp;
};

int n, Q;
int ans[N];

namespace BIT {
	int sum[N];
	inline int lowbit(int x) { return x & -x; }
	inline void modify(int p, int v) {
		for(int i = p; i <= n; i += lowbit(i)) {
			sum[i] += v;
		}
	}
	inline int query(int p) {
		int res = 0;
		for(int i = p; i > 0; i -= lowbit(i)) {
			res += sum[i];
		}
		return res;
	}
	inline int query(int l, int r) {
		return query(r) - query(l - 1);
	}
}

void solve(vector<Op> &op, int l, int r) {
	if(op.empty()) return;
	if(l == r) {
		for(Op o : op) {
			if(o.tp == 0) {
				ans[o.id] = l;
			}
		}
		return;
	}
	int mid = (l + r) >> 1;
	for(Op o : op) {
		if(o.tp == 1 && o.x <= mid) BIT::modify(o.id, 1); 
	}
	vector<Op> lop, rop;
	for(Op o : op) {
		if(o.tp == 0) {
			int cnt = BIT::query(o.x, o.y);
			if(cnt >= o.k) lop.push_back(o);
			else rop.push_back({o.x, o.y, o.k - cnt, o.id, o.tp});
		} else {
			if(o.x <= mid) lop.push_back(o);
			else rop.push_back(o); 
		}
	}
	for(Op o : op) {
		if(o.tp == 1 && o.x <= mid) BIT::modify(o.id, -1);
	}
	solve(lop, l, mid);
	solve(rop, mid + 1, r);
}

vector<Op> op;

int main() {
	
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n >> Q;
	for(int i = 1; i <= n; i++) {
		int x;
		cin >> x;
		op.push_back({x, 0, 0, i, 1}); 
	}
	for(int i = 1; i <= Q; i++) {
		int l, r, k;
		cin >> l >> r >> k;
		op.push_back({l, r, k, i, 0});
	}
	
	solve(op, -A, A);
	
	for(int i = 1; i <= Q; i++) {
		cout << ans[i] << '\n'; 
	}
	
	return 0;
}

P2617 Dynamic Rankings

#include<iostream>
#include<vector>
using namespace std;
const int N = 1E5 + 10;
const int A = 1E9; 

struct Op {
	int x, y, k;
	int id, tp;
};

int n, m;
int ans[N];

namespace BIT {
	int sum[N];
	inline int lowbit(int x) { return x & -x; }
	inline void modify(int p, int v) {
		for(int i = p; i <= n; i += lowbit(i)) {
			sum[i] += v;
		} 
	}
	inline int query(int p) {
		int res = 0;
		for(int i = p; i > 0; i -= lowbit(i)) {
			res += sum[i];
		}
		return res;
	} 
	inline int query(int l, int r) {
		return query(r) - query(l - 1);
	}
}

void cdq(vector<Op>& op, int l, int r) {
	if(op.empty()) return; 
	if(l == r) {
		for(Op o : op) {
			if(o.tp == 0) ans[o.id] = l;
		}
		return;
	}
	int mid = (l + r) >> 1;
	vector<Op> lop, rop;
	for(Op o : op) {
		if(o.tp == 0) {
			int lcnt = BIT::query(o.x, o.y);
			if(o.k <= lcnt) lop.push_back(o);
			else rop.push_back({o.x, o.y, o.k - lcnt, o.id, o.tp}); 
		} else if(o.x <= mid) {
			BIT::modify(o.id, o.tp);
			lop.push_back(o);
		} else {
			rop.push_back(o);
		}
	}
	for(Op o : op) {
		if(o.tp && o.x <= mid) {
			BIT::modify(o.id, -o.tp);
		}
	}
	cdq(lop, l, mid);
	cdq(rop, mid + 1, r);
} 

int a[N];
vector<Op> op;

int main() {
	
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		op.push_back({a[i], 0, 0, i, 1});
	}
	
	int nq = 0;
	while(m--) {
		char c;
		int l, r, x, y, k;
		cin >> c;
		if(c == 'Q') {
			cin >> l >> r >> k;
			op.push_back({l, r, k, ++nq, 0}); 
		} else {
			cin >> x >> y;
			op.push_back({a[x], 0, 0, x, -1});
			op.push_back({y, 0, 0, x, 1});
			a[x] = y;
		}
	}
	
	cdq(op, 0, A);
	
	for(int i = 1; i <= nq; i++) {
		cout << ans[i] << '\n';
	}
	
	return 0;
}