CDQ分治和整体二分板子

陌上花开

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10, M = 2e5 + 10;
int n, k, m, ans[N], tr[M], res[N], tot[N];
int lowbit(int x){
	return x & -x; 
}
void insert(int x, int val){
	for(; x <= k; x += lowbit(x))
		tr[x] += val;
	return;
}
int query(int x){
	int ret = 0;
	for(; x; x -= lowbit(x))
		ret += tr[x];
	return ret;
}
struct pos{
	int x, y, z, val, id;
	bool operator < (const pos a) const {
		return (x == a.x) ? ((y == a.y) ? z < a.z : y < a.y) : x < a.x;
	}
}tmp[N], flo[N];
void cdq(int L, int R){
	if(L == R) return;
	int mid = (L + R) >> 1;
	cdq(L, mid); cdq(mid + 1, R); 
	int l = L, r = mid + 1;
	int len = 0;
	while(l <= mid || r <= R){
		if(r > R || l <= mid && flo[l].y <= flo[r].y){
			insert(flo[l].z, flo[l].val);
			tmp[++len] = flo[l];
			l++;
		} else {
			tmp[++len] = flo[r];
			ans[flo[r].id] += query(flo[r].z);
			r++;
		} 
	}
	for(int i = L; i <= mid; i++)
		insert(flo[i].z, -flo[i].val);
	for(int i = 1; i <= len; i++)
		flo[L - 1 + i] = tmp[i];
	return;
}
int main(){
	scanf("%d%d", &n, &k);
	for(int i = 1; i <= n; i++)
		scanf("%d%d%d", &flo[i].x, &flo[i].y, &flo[i].z), flo[i].val = 1;
	sort(flo + 1, flo + n + 1);
	for(int i = 1; i <= n; i++){
		flo[++m] = flo[i]; flo[m].id = m;
		int j = i + 1; 
		while(j <= n && flo[j].x == flo[i].x && flo[j].y == flo[i].y && flo[j].z == flo[i].z)
			flo[m].val++, j++;
		tot[m] = flo[m].val;
		i = j - 1;
	}
	cdq(1, m);
	for(int i = 1; i <= m; i++) res[ans[i] + tot[i] - 1] += tot[i];
	for(int i = 0; i < n; i++) printf("%d
", res[i]); 
	return 0;
}

动态查询第k大

#include<bits/stdc++.h>
using namespace std;
#define mkp make_pair
#define pb push_back
typedef long long ll;
const int N = 1e5 + 10, inf = 1e9 + 7; 
struct node{
	int tp, pos, x, y, val;
}q[N * 3], q1[N * 3], q2[N * 3];
int n, m, W = 2e5, cnt, is[N], ans[N], tr[N << 1], lst[N]; 
int lowbit(int x){ return x & -x; } 
void insert(int x, int val){
	for(; x <= W; x += lowbit(x))
		tr[x] += val; 
	return;
}
int query(int x){
	int ret = 0;
	for(; x; x -= lowbit(x))
		ret += tr[x];
	return ret;
}
void solve(int l, int r, int L, int R){
	if(L > R) return;
	if(l == r){
		for(int i = L; i <= R; i++)
			if(q[i].tp == 1) ans[q[i].pos] = l;
		return; 
	}
	int mid = (l + r) >> 1, cnt1 = 0, cnt2 = 0;
	for(int i = L; i <= R; i++){
		if(q[i].tp) {
			int sum = query(q[i].y) - query(q[i].x - 1);
			if(sum >= q[i].val) q1[++cnt1] = q[i];
			else q[i].val -= sum, q2[++cnt2] = q[i]; 
		} else {
			if(q[i].x <= mid) insert(q[i].pos, q[i].val), q1[++cnt1] = q[i];
			else q2[++cnt2] = q[i];
		}
	}
	for(int i = L; i <= R; i++)
		if(!q[i].tp && q[i].x <= mid) insert(q[i].pos, -q[i].val);
	for(int i = 1; i <= cnt1; i++) q[L + i - 1] = q1[i];
	for(int i = 1; i <= cnt2; i++) q[L + cnt1 + i - 1] = q2[i]; 
	solve(l, mid, L, L + cnt1 - 1); solve(mid + 1, r, L + cnt1, R);
	return;
}
int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1, x; i <= n; i++)
		scanf("%d", &x), q[++cnt] = (node){0, i, x, 0, 1}, lst[i] = x;
	for(int i = 1, x, y, z; i <= m; i++){
		char tp[5];
		scanf("%s", tp);
		if(tp[0] == 'Q'){
			is[i] = 1;
			scanf("%d%d%d", &x, &y, &z);
			q[++cnt] = (node){1, i, x, y, z};
		} else {
			scanf("%d%d", &x, &y);
			q[++cnt] = (node){0, x, lst[x], 0, -1};
			q[++cnt] = (node){0, x, y, 0, 1}; lst[x] = y; 
		}
	}
	solve(0, inf, 1, cnt);
	for(int i = 1; i <= m; i++)
		if(is[i]) printf("%d
", ans[i]);
	return 0;
}