整体二分基础

还是放模板题的一篇博客。话说今天和分治挺有缘，上午cdq，下午整体分治。

整体分治为何物？一种特殊的分治，和cdq一样是在朴素分治上加了外挂，只不过cdq是参照的归并，整体是参照的二分查找。

众所周知二分查找可是个好东西，但问题在于它需要一定的预处理，比如让序列有序。这就让它在询问次数很多时显得有点力不从心，但没关系，我们有整体二分。

整体二分的要求和cdq一样，需要允许离线的题目，但它支持修改。而且能用整体二分写的题目一般都能用树套树来解决，但它常数小一点（3到7倍的样子），写起来也要简单一点。

整体二分的思路就是对于值域进行二分，每次得出来的mid不只是针对某一个询问，而是针对所有包含了这个点的询问，这样就充分利用了我们的算力，这不挺好？

有两个模板题。第一个是主席树的模板题。题意是多次询问区间第k大，当然可以用主席树来做，但既然博客题目是整体二分，那就不写主席树吧。做法上就是考虑递归处理，假如当前处理的值域是l和r，它们产生了一个mid，那么我们就可以把所有处在[l,mid]之中的数的位置标记为1，然后对于每个询问进行查询即可，这类题一般用的树状数组维护。边界就是左右指针重合，这说明这一系列的询问答案都会是当前的值。

#include
#include
//#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;
}

另一个是Dynamic Rankings，题目一样，只是要求修改。修改其实都还好，由于读入的时候默认是按时间来的，处理的时候来就按顺序可以了。

#include
#include
//#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;
}

最后说一句，负数域一定要用右移而不是除法！