The so-called CDQ divide and conquer is the divide and conquer algorithm invented together with Conprour, Doctorjellyfish and QE Tim

(escape)

preface

Magical mess with black Technology
CDQ divide and conquer can complete some large algorithms through smaller time constants and simpler code difficulty, such as tree nest tree, play convex hull and so on.
Application conditions: query offline, modify independent

Examples

P3810 [template] 3D partial order (flowers bloom on the street)

There are n elements, and each element has three eigenvalues. Element a is greater than element b if and only if all three eigenvalues of a are greater than or equal to b
Let f(i) represent the number of elements (excluding itself) in which a is greater than. For each i, find the number of X in which f(x)=i
n ≤ 2 × 1 0 5 n\le 2\times10^5 n≤2×105

The classic routine of CDQ divide and Conquer: first recursively find the left and right internal contributions, and then find the left and right contributions to each other
Sort by x first, and then sort by y on both sides during each merging. Use double pointers to maintain the tree array and accumulate the answers
Time complexity O ( n l o g n 2 ) O(nlogn^2) O(nlogn2)
In terms of details, note that the same elements need special treatment. Don't forget to empty the tree array

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
const int N=2e5+100;
const int mod=998244353;
inline ll read() {
	ll x(0),f(1);
	char c=getchar();
	while(!isdigit(c)) {
		if(c=='-')f=-1;
		c=getchar();
	}
	while(isdigit(c)) {
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*f;
}

int n,m,k;
struct node{
	int a,b,c,id,w;
}p[N],P[N];
bool cmpa(node u,node v){
	if(u.a!=v.a) return u.a<v.a;
	else if(u.b!=v.b) return u.b<v.b;
	return u.c<v.c;
}	
bool cmpb(node u,node v){
	if(u.b!=v.b) return u.b<v.b;
	else return u.c<v.c;
}

int f[N];
inline void add(int p,int w){
	for(;p<=m;p+=p&-p) f[p]+=w;
	return;
}
inline int ask(int p){
	int res(0);
	for(;p;p-=p&-p) res+=f[p];
	return res;
}

int ans[N],bac[N];
void solve(int l,int r){
	if(l==r) return;
	int mid=(l+r)>>1;
	solve(l,mid);solve(mid+1,r);
	//printf("\nsolve:(%d %d)\n",l,r);
	sort(p+l,p+mid+1,cmpb);
	sort(p+mid+1,p+r+1,cmpb);
	int pl=l;
	for(int i=mid+1;i<=r;i++){
		while(pl<=mid&&p[pl].b<=p[i].b){
			add(p[pl].c,p[pl].w);
			//printf("  add: (%d %d %d) w=%d\n",p[pl].a,p[pl].b,p[pl].c,p[pl].w);
			++pl;
		}
		ans[p[i].id]+=ask(p[i].c);
		//printf("  query: (%d %d %d) add=%d\n",p[i].a,p[i].b,p[i].c,ask(p[i].c));
	}
	for(int i=l;i<pl;i++) add(p[i].c,-p[i].w);
	return;
}
int main(){
#ifndef ONLINE_JUDGE
	//freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
#endif
	n=read();m=read();
	for(int i=1;i<=n;i++){
		P[i]=(node){(int)read(),(int)read(),(int)read()};
	}
	sort(P+1,P+1+n,cmpa);
	int tot(0);
	for(int i=1;i<=n;i++){
		if(i>1&&P[i-1].a==P[i].a&&P[i-1].b==P[i].b&&P[i-1].c==P[i].c) p[tot].w++;
		else{
			p[++tot]=P[i];p[tot].w=1;p[tot].id=tot;
		}
	}
	swap(tot,n);
	solve(1,n);
	for(int i=1;i<=n;i++){
		bac[ans[p[i].id]+p[i].w-1]+=p[i].w;
		//printf("(%d %d %d) ans=%d\n",p[i].a,p[i].b,p[i].c,ans[p[i].id]);
	}
	for(int i=0;i<tot;i++) printf("%d\n",bac[i]);
	return 0;
}
/*
*/

P2487 [SDOI2011] interceptor missile

In order to defend against the missile attack of the enemy, a certain country has developed a missile interception system. However, this missile interception system has a defect: although its first shell can reach any height and intercept missiles at any speed, each shell in the future can not be higher than the height of the previous one, and the flight speed of the intercepted missile can not be greater than the previous one. One day, the radar caught the enemy's missile attack. Since the system is still in the trial stage, there is only one system, so it may not be able to intercept all missiles.
When it is impossible to intercept all missiles, of course, we should choose the scheme that minimizes national losses, that is, to intercept the largest number of missiles. However, there may be multiple schemes with the largest number of interceptor missiles. If there are multiple optimal schemes, we will randomly select one as the final interceptor missile action blueprint.
Our spy has obtained the altitude and speed of all enemy missiles. Your task is to calculate the probability that each missile will be intercepted when making the above decision.

Optimizing DP of 1D-1D using CDQ divide and conquer
First recursively process the dp value of the left half interval, then try to update the right half interval with the dp value of the left half interval, and then recursively process the right half interval
Using tree array to maintain the maximum value of prefix / suffix to ensure complexity
Time complexity O ( n l o g n 2 ) O(nlogn^2) O(nlogn2)
Note: before recursively processing the right half interval, you need to sort it again according to the subscript to make the right half interval ordered again

#include<bits/stdc++.h>
using namespace std;
#define ll __int128
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
const int N=2e5+100;
const int mod=1e9;
inline ll read() {
	ll x(0),f(1);char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}

int n,m,k;
int q[N],cnt;
struct node{
	int a,b,id;
	bool operator < (const node o){return a>o.a;}
}p[N];
bool cmp(node u,node v){
	return u.id<v.id;
}
struct Dp{
	int val;
	ll num;
}dp1[N],dp2[N];
void operator += (Dp &a,Dp b){
	if(b.val>a.val) a=b;
	else if(b.val==a.val) a.num+=b.num;
	return;
}

Dp f[N];
inline void Upd(int p,Dp w){
	for(;p<=cnt;p+=p&-p) f[p]+=w;
	return;
}
inline Dp Ask(int p){
	Dp res=(Dp){0,0};
	for(;p;p-=p&-p) res+=f[p];
	return res;
}
inline void Clear(int p){
	for(;p<=cnt;p+=p&-p) f[p]=(Dp){0,0};
	return;
}
void solve2(int l,int r){
	if(l==r){
		++dp2[l].val;return;
	}
	int mid=(l+r)>>1;
	solve2(mid+1,r);
	//printf("\nsolve: (%d %d)\n",l,r);
	sort(p+l,p+mid+1);sort(p+mid+1,p+r+1);
	int pl=r;
	for(int i=mid;i>=l;i--){
		while(pl>mid&&p[pl].a<=p[i].a){
			Upd(p[pl].b,dp2[p[pl].id]);
			//printf("  add: i=%d DP:(%d %d)\n",p[pl].id,dp2[pl].val,(int)dp2[pl].num);
			--pl;
		}
		dp2[p[i].id]+=Ask(p[i].b);
		//printf("  update: i=%d DP:(%d %d)\n",p[i].id,dp2[i].val,(int)dp2[i].num);
	}
	for(int i=r;i>pl;i--) Clear(p[i].b);
	sort(p+l,p+mid+1,cmp);
	solve2(l,mid);
	return;
}

inline void upd(int p,Dp w){
	p=cnt-p+1;
	for(;p<=cnt;p+=p&-p) f[p]+=w;
	return;
}
inline Dp ask(int p){
	p=cnt-p+1;
	Dp res=(Dp){0,0};
	for(;p;p-=p&-p) res+=f[p];
	return res;
}
inline void clear(int p){
	p=cnt-p+1;
	for(;p<=cnt;p+=p&-p) f[p]=(Dp){0,0};
	return;
}
void solve1(int l,int r){
	if(l==r){
		++dp1[l].val;return;
	}
	int mid=(l+r)>>1;
	solve1(l,mid);
	sort(p+l,p+mid+1);sort(p+mid+1,p+r+1);
	//printf("\nsolve: (%d %d)\n",l,r);
	int pl=l;
	for(int i=mid+1;i<=r;i++){
		while(pl<=mid&&p[pl].a>=p[i].a){
			upd(p[pl].b,dp1[p[pl].id]);
			++pl;
			//printf("  add: i=%d DP:(%d %d)\n",p[i].id,dp1[i].val,(int)dp1[i].num);
		}
		dp1[p[i].id]+=ask(p[i].b);
		//printf("  update: i=%d DP:(%d %d)\n",p[i].id,dp1[i].val,(int)dp1[i].num);
	}
	for(int i=l;i<pl;i++) clear(p[i].b);
	sort(p+mid+1,p+r+1,cmp);
	solve1(mid+1,r);
	return;
}

int main(){
#ifndef ONLINE_JUDGE
	//freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
#endif
	n=read();
	for(int i=1;i<=n;i++){
		p[i].a=read();p[i].b=read();p[i].id=i;dp1[i].num=dp2[i].num=1;
		q[++cnt]=p[i].a;q[++cnt]=p[i].b;
	}
	sort(q+1,q+1+cnt);
	cnt=unique(q+1,q+1+cnt)-q-1;
	for(int i=1;i<=n;i++){
		p[i].a=lower_bound(q+1,q+1+cnt,p[i].a)-q;
		p[i].b=lower_bound(q+1,q+1+cnt,p[i].b)-q;
	}
	solve1(1,n);
	sort(p+1,p+1+n,cmp);
	solve2(1,n);
	ll sum=0;int ans(0);
	for(int i=1;i<=n;i++){
		if(dp1[i].val>ans){
			ans=dp1[i].val;sum=dp1[i].num;
		}
		else if(dp1[i].val==ans){
			sum+=dp1[i].num;
		}
	}
	printf("%d\n",ans);
	for(int i=1;i<=n;i++){
		//printf("i=%d dp1=(%d %d) dp2=(%d %d)\n",i,dp1[i].val,(int)dp1[i].num,dp2[i].val,(int)dp2[i].num);
		if(dp1[i].val+dp2[i].val-1==ans){
			printf("%.5lf ",1.0*dp1[i].num*dp2[i].num/sum);
		}
		else printf("0.00000 ");
	}
	return 0;
}
/*
10
23 7
63 14
84 57
40 74
96 79
20 27
48 37
86 70
66 28
86 47
*/