整体二分

整体二分：对所有的询问一起进行二分
满足前提：
$①：$①：单组询问可以二分
$②：$②：对于修改具有高效的数据结构维护
$③：$③：贡献满足交换律，结合律，具有可加性
$④：$④：可以离线
$⑤：$⑤：具有类似决策单调性

大致过程：
每次对询问 $(x, y)$(x,y) 并且答案在 $(l, r)$(l,r) 进行处理
处理结束后，答案在 $mid$mid 之前的询问放在左边
答案在 $mid$mid 之后的询问减掉 $(l,mid)$(l,mid) 的贡献，放在右边
递归处理
时间复杂度：$O(q \times log(r - l) \times 修改)$O(q×log(r−l)×修改)

---

例题一：P3527 [POI2011] MET-Meteors

大意：区间加，询问每个点达到指定数目的最少次数
题解：注意树状数组进行区间修改

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
using pii = pair <int,int>;
const int maxn = 6e5 + 5;
int n, m, k, ans[maxn];
int L[maxn], R[maxn], A[maxn];
ll d[maxn];
vector <int> g[maxn];
struct node{
	int nd, id;
} a[maxn], ta[maxn];

inline void add(int x, ll v){
	for(int i=x; i<=m<<1; i+=(i&-i))
		d[i] += v;
}
inline ll sum(int x){
	ll ret = 0;
	for(int i=x; i; i-=(i&-i))
		ret += d[i];
	return ret;
}

void solve(int l, int r, int x, int y){
	if(l > r || x > y) return; 
	if(l == r){
		for(int i=x; i<=y; i++) ans[a[i].id] = l;
		return ;
	}
	int mid = l + r >> 1, tl = 0, tr = n;
	for(int i=l; i<=mid; i++) add(L[i], A[i]), add(R[i]+1, -A[i]);
	for(int i=x; i<=y; i++){
		ll tmp = 0;
		for(auto j : g[a[i].id]) {
			tmp += sum(j) + sum(j+m);
			if(tmp >= a[i].nd) break;
		}
		if(tmp >= a[i].nd) ta[++tl] = a[i];
		else ta[++tr] = a[i], ta[tr].nd -= tmp;
	}
	for(int i=l; i<=mid; i++) add(L[i], -A[i]), add(R[i]+1, A[i]);
	for(int i=1; i<=tl; i++) a[x+i-1] = ta[i];
	for(int i=n+1; i<=tr; i++) a[x+tl+i-n-1] = ta[i];
	if(tl) solve(l, mid, x, x+tl-1);
	if(tr>n) solve(mid+1, r, x+tl, y);
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i=1, x; i<=m; i++){
		scanf("%d", &x);
		g[x].push_back(i);
	}
	for(int i=1; i<=n; i++){
		scanf("%d", &a[i].nd);
		a[i].id = i;
	}
	scanf("%d", &k);
	for(int i=1; i<=k; i++){
		scanf("%d%d%d", L+i, R+i, A+i);
		if(R[i] < L[i]) R[i] += m;
	}
	solve(1, k+1, 1, n);
	for(int i=1; i<=n; i++)
		if(ans[i] == k+1) puts("NIE");
		else printf("%d\n", ans[i]);
}

---

例题二：P3834 【模板】可持久化线段树 1（主席树）

大意：静态区间第 $k$k 大
题解：考虑如何修改，对于答案在 $(l,mid)$(l,mid)，首先要加入一个数，处理完之后再删除
因此对于要加入的数，考虑值是否在 $(l,mid)$(l,mid) 内，否则直接放到右边
若要加入，则直接维护位置的修改，查询时就直接查区间和
注意因为要先加入数字然后查询，并且本题不需要离散化

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
const int maxn = 8e5 + 5;
int n, m, a[maxn], d[maxn];
int ans[maxn];
struct node{
	int l, r, k, id;
} q[maxn], tq[maxn];

void add(int x, int v){
	for(int i=x; i<=n; i+=i&-i)
		d[i] += v;
}
int sum(int x){
	int ret = 0;
	for(int i=x; i; i-=i&-i)
		ret += d[i];
	return ret;
}

void solve(int l, int r, int x, int y){
	if(l > r || x > y) return;
	if(l == r){
		for(int i=x; i<=y; i++) ans[q[i].id] = l;
		return ;
	}
	int mid = l + r >> 1, tl = 0, tr = n + m;
	for(int i=x; i<=y; i++){
		if(q[i].id == 0){
			if(q[i].k <= mid) tq[++tl] = q[i], add(q[i].l, 1);
			else tq[++tr] = q[i];
		} else {
			int tmp = sum(q[i].r) - sum(q[i].l-1);
			if(tmp >= q[i].k) tq[++tl] = q[i];
			else tq[++tr] = q[i], tq[tr].k -= tmp;
		}
	}
	for(int i=1; i<=tl; i++) {
		q[x+i-1] = tq[i];
		if(tq[i].id == 0) add(tq[i].l, -1);
	}
	for(int i=n+m+1; i<=tr; i++) q[x+tl+i-n-m-1] = tq[i];
	solve(l, mid, x, x+tl-1);
	solve(mid+1, r, x+tl, y);
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i=1; i<=n; i++) scanf("%d", a+i);
	for(int i=1; i<=n; i++) q[i].id = 0, q[i].k = a[i], q[i].l = i;
	for(int i=1; i<=m; i++){
		scanf("%d%d%d", &q[i+n].l, &q[i+n].r, &q[i+n].k);
		q[i+n].id = i;
	}
	solve(0, 2e9, 1, n + m);
	for(int i=1; i<=m; i++) printf("%d\n", ans[i]);
}

---

例题三：P2617 Dynamic Rankings

大意：动态区间第 $k$k 大
题解：与静态的唯一区别在于有修改
那么修改可以分为删除一个数之后再加入一个数
注意修改的先后顺序

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
const int maxn = 8e5 + 5;
int n, m, a[maxn], d[maxn];
int ans[maxn], cnt, tot, num[maxn];
struct node{
	int l, r, k, id, tp;
} q[maxn], tq[maxn];

inline void add(int x, int v){
	for(int i=x; i<=n; i+=i&-i)
		d[i] += v;
}
inline int sum(int x){
	int ret = 0;
	for(int i=x; i; i-=i&-i)
		ret += d[i];
	return ret;
}

void solve(int l, int r, int x, int y){
	if(l > r || x > y) return;
	if(l == r){
		for(int i=x; i<=y; i++) ans[q[i].id] = l;
		return ;
	}
	int mid = l + r >> 1, tl = 0, tr = cnt;
	for(int i=x; i<=y; i++){
		if(q[i].tp == 1 && mid >= q[i].r) add(q[i].l, 1);
		if(q[i].tp == 2 && mid >= q[i].r) add(q[i].l, -1);
		if(q[i].tp == 3) num[i] = sum(q[i].r) - sum(q[i].l-1);
	}
	for(int i=x; i<=y; i++){
		if(q[i].tp == 1 && mid >= q[i].r) add(q[i].l, -1);
		if(q[i].tp == 2 && mid >= q[i].r) add(q[i].l, 1);
		if(q[i].tp == 1 || q[i].tp == 2){
			if(q[i].r <= mid) tq[++tl] = q[i];
			else tq[++tr] = q[i];
		} else {
			if(num[i] >= q[i].k) tq[++tl] = q[i];
			else tq[++tr] = q[i], tq[tr].k -= num[i];
		}
	}
	for(int i=1; i<=tl; i++) q[x+i-1] = tq[i];
	for(int i=cnt+1; i<=tr; i++) q[x+tl+i-cnt-1] = tq[i];
	solve(l, mid, x, x+tl-1);
	solve(mid+1, r, x+tl, y);
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i=1; i<=n; i++) scanf("%d", a+i);
	for(int i=1; i<=n; i++) q[i].tp = 1, q[i].l = i, q[i].r = a[i];
	cnt = n; char op;
	for(int i=1, l, r, k; i<=m; i++){
		scanf("%s", &op);
		if(op == 'Q'){
			scanf("%d%d%d", &l, &r, &k);
			q[++cnt].l = l, q[cnt].r = r, q[cnt].k = k;
			q[cnt].id = ++tot, q[cnt].tp = 3;
		} else {
			scanf("%d%d", &l, &r);
			q[++cnt].l = l, q[cnt].r = a[l];
			q[cnt].tp = 2;
			q[++cnt].l = l, a[l] = q[cnt].r = r;
			q[cnt].tp = 1;
		}
	}
	solve(0, 2e9, 1, cnt);
	for(int i=1; i<=tot; i++) printf("%d\n", ans[i]);
}