Or a blog with template questions. It's said that today has a good relationship with divide and conquer. Divide and conquer in the morning cdq and afternoon as a whole.

What is the overall partition? A special divide and conquer. Like cdq, it adds a plug-in to the simple divide and conquer, but cdq is the merging of references and the whole is the binary search of references.

As we all know, binary search is a good thing, but the problem is that it requires some preprocessing, such as ordering the sequence. This makes it a little weak when asking a lot of times, but it doesn't matter. We have two points as a whole.

The requirement of overall dichotomy is the same as that of cdq. Offline topics need to be allowed, but it supports modification. Moreover, the problems that can be written in overall dichotomy can generally be solved by tree covering tree, but its constant is a little smaller (3 to 7 times), and it should be easier to write.

The idea of overall dichotomy is to dichotomy the value range. The mid obtained each time is not only for a query, but for all queries containing this point, so as to make full use of our computing power. Isn't that good?

There are two template questions. The first is the chairman tree Template question . The meaning of the question is to ask the k-largest range for many times. Of course, you can use the chairman tree, but since the blog title is the overall dichotomy, don't write the chairman tree. The practice is to consider recursive processing. If the value range of the current processing is l and r, and they produce a mid, then we can mark the position of all numbers in [l,mid] as 1, and then query each query. This kind of problems are generally maintained by tree number groups. The boundary is that the left and right pointers coincide, which means that the answer to this series of questions will be the current value.

#include<cstdio>
#include<algorithm>
//#define zczc
using namespace std;
const int N=200010;
const int maxn=1e9;
inline void read(int &wh){
	wh=0;int f=1;char w=getchar();
	while(w<'0'||w>'9'){if(w=='-')f=-1;w=getchar();}
	while(w<='9'&&w>='0'){wh=wh*10+w-'0';w=getchar();}
	wh*=f;return;
}

int m,n,cnt;

#define lowbit (wh&-wh)
int t[N];
inline void change(int wh,int val){
	for(;wh<=m;wh+=lowbit)t[wh]+=val;
}
inline int work(int wh){
	int an=0;
	for(;wh;wh-=lowbit)an+=t[wh];
	return an;
}
#undef lowbit

int ans[N];
struct node{
	int op,id,l,r,k;
}q[N<<1],s1[N<<1],s2[N<<1];

void solve(int wl,int wr,int l,int r){
	if(wl>wr)return;
	if(l==r){
		for(int i=wl;i<=wr;i++)ans[q[i].id]=l;
		return;
	}
	int mid=l+r>>1,t1=0,t2=0;
	for(int i=wl;i<=wr;i++){
		if(q[i].op==1)continue;
		if(q[i].l<=mid){
			change(q[i].r,1);
			s1[++t1]=q[i];
		}
		else s2[++t2]=q[i];
	}
	for(int i=wl;i<=wr;i++){
		if(q[i].op==0)continue;
		int now=work(q[i].r)-work(q[i].l-1);
		if(now>=q[i].k)s1[++t1]=q[i];
		else q[i].k-=now,s2[++t2]=q[i];
	}
	for(int i=wl;i<=wr;i++){
		if(q[i].op==1)continue;
		if(q[i].l<=mid)change(q[i].r,-1);
	}
	for(int i=1;i<=t1;i++)q[wl+i-1]=s1[i];
	for(int i=1;i<=t2;i++)q[wl+t1+i-1]=s2[i];
	solve(wl,wl+t1-1,l,mid);
	solve(wl+t1,wr,mid+1,r);
	return;
}

signed main(){
	
	#ifdef zczc
	freopen("in.txt","r",stdin);
	#endif
	
	read(m);read(n);
	for(int i=1;i<=m;i++){
		cnt++;read(q[i].l);
		q[cnt].op=0;q[cnt].r=i;
	}
	for(int i=1;i<=n;i++){
		cnt++;
		read(q[cnt].l);read(q[cnt].r);read(q[cnt].k);
		q[cnt].id=i,q[cnt].op=1;
	}
	solve(1,cnt,-maxn,maxn);
	for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
	
	return 0;
}

The other is Dynamic Rankings , the title is the same, just ask for modification. In fact, all modifications are OK, because the default is to read in according to the time, and the processing can be done in order.

#include<cstdio>
#include<algorithm>
//#define zczc
using namespace std;
const int N=100010;
const int maxn=1e9;
inline void read(int &wh){
	wh=0;int f=1;char w=getchar();
	while(w<'0'||w>'9'){if(w=='-')f=-1;w=getchar();}
	while(w<='9'&&w>='0'){wh=wh*10+w-'0';w=getchar();}
	wh*=f;return;
}
inline bool get(){
	char w=getchar();
	while(w!='Q'&&w!='C')w=getchar();
	return w=='Q';
}

int m,n,cnt,sr[N];
struct node{
	int op,id,l,r,val;
}a[N*3],s1[N*3],s2[N*3];

#define lowbit (wh&-wh)
int t[N],nt[N],ti;
inline void change(int wh,int val,int wt){
	for(;wh<=m;wh+=lowbit){
		if(nt[wh]!=wt)nt[wh]=wt,t[wh]=0;
		t[wh]+=val;
	}
	return;
}
inline int work(int wh,int wt){
	int an=0;
	for(;wh;wh-=lowbit){
		if(nt[wh]==wt)an+=t[wh];
	}
	return an;
}
#undef lowbit

int ans[N];
void solve(int wl,int wr,int l,int r){
	if(wl>wr)return;
	if(l==r){
		for(int i=wl;i<=wr;i++)ans[a[i].id]=l;
		return;
	}
	ti++;int mid=l+r>>1,t1=0,t2=0;
	for(int i=wl;i<=wr;i++){
		if(a[i].op==0){
			if(a[i].l<=mid){
				change(a[i].r,a[i].val,ti);
				s1[++t1]=a[i];
			}
			else s2[++t2]=a[i];
		}
		else{
			int now=work(a[i].r,ti)-work(a[i].l-1,ti);
			if(now>=a[i].val)s1[++t1]=a[i];
			else{
				a[i].val-=now;
				s2[++t2]=a[i];
			}
		}
	}
	for(int i=1;i<=t1;i++)a[wl+i-1]=s1[i];
	for(int i=1;i<=t2;i++)a[wl+t1+i-1]=s2[i];
	solve(wl,wl+t1-1,l,mid);
	solve(wl+t1,wr,mid+1,r);
	return;
}

signed main(){
	
	#ifdef zczc
	freopen("in.txt","r",stdin);
	#endif
	
	read(m);read(n);
	for(int i=1;i<=m;i++){
		cnt++;read(sr[i]);
		a[cnt].l=sr[i];a[i].r=i;
		a[cnt].op=false;a[cnt].val=1;
	}
	int s1,s2,s3,nid=0;
	for(int i=1;i<=n;i++){
		if(get()){
			read(s1);read(s2);read(s3);
			cnt++;
			a[cnt].op=true,a[cnt].id=++nid;
			a[cnt].l=s1,a[cnt].r=s2,a[cnt].val=s3;
		}
		else{
			read(s1);read(s2);
			cnt++;
			a[cnt].op=false;
			a[cnt].l=sr[s1];a[cnt].r=s1;a[cnt].val=-1;
			cnt++;
			a[cnt].op=false;
			a[cnt].l=s2;a[cnt].r=s1;a[cnt].val=1;
			sr[s1]=s2;
		}
	}
	
	solve(1,cnt,0,maxn);
	for(int i=1;i<=nid;i++)printf("%d\n",ans[i]);
	
	return 0;
}

Finally, the negative field must be shifted to the right instead of division!