登录
← 返回首页 | 代码片段 › 2 数据结构 › 2.12 CDQ分治与整体二分 › CDQ分治与整体二分 / 搜索
JSON MD

2.12 CDQ分治与整体二分

CDQ分治 三维偏序
48 行
CPP JSON
#pragma GCC optimize(3,"Ofast","inline") #pragma GCC optimize(2)
C++ 47 行 CPP
//#pragma GCC optimize(3,"Ofast","inline")
//#pragma GCC optimize(2)
#include<algorithm>
#include<cstdio>
#define Re register int
using std::sort;
const int N=1e5+5,K=2e5+5;
int n,m,k,C[K],ans[N];
struct QAQ{int a,b,c,cnt,ans;}a[N],Q[N];
inline void in(Re &x){
    int fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
inline bool cmp1(QAQ p,QAQ o){return p.a!=o.a?p.a<o.a:(p.b!=o.b?p.b<o.b:p.c<o.c);}
inline bool cmp2(QAQ p,QAQ o){return p.b<o.b;}
inline void add(Re x,Re v){while(x<=k)C[x]+=v,x+=x&-x;}
inline int ask(Re x){
	Re ans=0;
	while(x)ans+=C[x],x-=x&-x;
	return ans;
}
inline void CDQ(Re L,Re R){
	if(L==R)return;
	Re mid=L+R>>1;
	CDQ(L,mid),CDQ(mid+1,R);
	sort(Q+L,Q+mid+1,cmp2),sort(Q+mid+1,Q+R+1,cmp2);
	Re j=L;
	for(Re i=mid+1;i<=R;++i){
		while(j<=mid&&Q[j].b<=Q[i].b)add(Q[j].c,Q[j].cnt),++j;
		Q[i].ans+=ask(Q[i].c);
	}
	for(Re i=L;i<j;++i)add(Q[i].c,-Q[i].cnt);
}
int main(){
	in(n),in(k);
	for(Re i=1;i<=n;++i)in(a[i].a),in(a[i].b),in(a[i].c);
	sort(a+1,a+n+1,cmp1);
	for(Re i=1;i<=n;++i){
		if(i>2&&a[i].a==a[i-1].a&&a[i].b==a[i-1].b&&a[i].c==a[i-1].c)++Q[m].cnt;
		else Q[++m]=a[i],Q[m].cnt=1;
	}
	CDQ(1,m);
	for(Re i=1;i<=m;++i)ans[Q[i].ans+Q[i].cnt-1]+=Q[i].cnt;
	for(Re i=0;i<n;++i)printf("%d\n",ans[i]);
}
整体二分 P3332 K大数查询
76 行
CPP JSON
【整体二分(P3332 K大数查询)】 代码包含 in, pushup, updata, updata_, pushdown 等核心函数,实现了 整体二分 的算法逻辑。 核心函数: void in(Re &x) — 核心算法函数 void pushup(Re p) — 上推更新节点信息 void updata(Re p,Re L,Re R,Re v) — 核心算法函数 void updata_(Re p) — 核心算法函数 void pushdown(Re p,Re L,Re R) — 下传懒标记 void change(Re p,Re L,Re R,Re l,Re r,Re v) — 核心算法函数 LL ask(Re p,Re L,Re R,Re l,Re r) — 核心算法函数 void sakura(Re l,Re r,Re L,Re R) — 后缀数组 核心结构体:QAQ, Segment_Tree, QAQ 关键配置: N=5e4+3,M=5e4+3,inf=1e9 说明:freopen("123.txt","r",stdin);
C++ 75 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
#define LL long long
using namespace std;
const int N=5e4+3,M=5e4+3,inf=1e9;
int n,x,T,Ans[M];
struct QAQ{int l,r,op,id;LL k;}Q[N+M],Q1[N+M],Q2[N+M];
inline void in(Re &x){
    int fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
struct Segment_Tree{
	#define pl p<<1
	#define pr p<<1|1
	#define Mid (L+R>>1)
	struct QAQ{int CL,add;LL S;}tr[N<<2];
	inline void pushup(Re p){tr[p].S=tr[pl].S+tr[pr].S;}
	inline void updata(Re p,Re L,Re R,Re v){tr[p].S+=v*(R-L+1),tr[p].add+=v;}
	inline void updata_(Re p){tr[p].add=tr[p].S=0,tr[p].CL=1;}
	inline void pushdown(Re p,Re L,Re R){
		if(tr[p].CL)updata_(pl),updata_(pr),tr[p].CL=0;
		if(tr[p].add)updata(pl,L,Mid,tr[p].add),updata(pr,Mid+1,R,tr[p].add),tr[p].add=0;
	}
	inline void change(Re p,Re L,Re R,Re l,Re r,Re v){
		if(l<=L&&R<=r){updata(p,L,R,v);return;}
		pushdown(p,L,R);
		if(l<=Mid)change(pl,L,Mid,l,r,v);
		if(r>Mid)change(pr,Mid+1,R,l,r,v);
		pushup(p);
	}
	inline LL ask(Re p,Re L,Re R,Re l,Re r){
		if(l<=L&&R<=r)return tr[p].S;
		LL ans=0;pushdown(p,L,R);
		if(l<=Mid)ans+=ask(pl,L,Mid,l,r);
		if(r>Mid)ans+=ask(pr,Mid+1,R,l,r);
		return ans;
	}
}T1;
inline void sakura(Re l,Re r,Re L,Re R){
	if(L>R)return;
	if(l==r){
		for(Re i=L;i<=R;++i)if(Q[i].op>1)Ans[Q[i].id]=l;
		return;
	}
	Re mid=l+r>>1,m1=0,m2=0;
	for(Re i=L;i<=R;++i)
		if(Q[i].op&1){
			if(Q[i].k<=mid)Q1[++m1]=Q[i];
			else Q2[++m2]=Q[i],T1.change(1,1,n,Q[i].l,Q[i].r,1);
		}
		else{
			LL tmp=T1.ask(1,1,n,Q[i].l,Q[i].r);
			if(Q[i].k<=tmp)Q2[++m2]=Q[i];
			else Q[i].k-=tmp,Q1[++m1]=Q[i];
		}
	T1.updata_(1);
	for(Re i=1;i<=m1;++i)Q[L+i-1]=Q1[i];
	for(Re i=1;i<=m2;++i)Q[L+m1+i-1]=Q2[i];
	sakura(l,mid,L,L+m1-1);
	sakura(mid+1,r,L+m1,R);
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T);
	for(Re i=1;i<=T;++i){
		in(Q[i].op),in(Q[i].l),in(Q[i].r),in(x),Q[i].k=x;
		if(Q[i].op>1)Q[i].id=++Ans[0];
	}
	sakura(-n,n,1,T);
	for(Re i=1;i<=Ans[0];++i)printf("%d\n",Ans[i]);
}
整体二分 动态区间第K小
57 行
CPP JSON
【整体二分(动态区间第K小)】 代码包含 in, add, ask_, ask, sakura 等核心函数,实现了 整体二分 的算法逻辑。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re v) — 加法更新 int ask_(Re x) — 核心算法函数 int ask(Re l,Re r) — 核心算法函数 void sakura(Re l,Re r,Re L,Re R) — 后缀数组 核心结构体:QAQ, BIT 关键配置: N=1e5+3,M=1e5+3,inf=1e9
C++ 56 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
#define LL long long
using namespace std;
const int N=1e5+3,M=1e5+3,inf=1e9;
int n,x,y,z,T,cnt,a[N],Ans[M];char op;
struct QAQ{int l,r,k,op,id;}Q[N+M*2],Q1[N+M*2],Q2[N+M*2];
inline void in(Re &x){
    int fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
struct BIT{
	int C[N];
	inline void add(Re x,Re v){while(x<=n)C[x]+=v,x+=x&-x;}
	inline int ask_(Re x){Re ans=0;while(x)ans+=C[x],x-=x&-x;return ans;}
	inline int ask(Re l,Re r){return ask_(r)-ask_(l-1);}
}T1;
inline void sakura(Re l,Re r,Re L,Re R){
	if(L>R)return;
	if(l==r){
		for(Re i=L;i<=R;++i)if(Q[i].op>1)Ans[Q[i].id]=l;
		return;
	}
	Re mid=l+r>>1,m1=0,m2=0;
	for(Re i=L;i<=R;++i)
		if(Q[i].op&1){
			if(Q[i].l<=mid)Q1[++m1]=Q[i],T1.add(Q[i].id,Q[i].r);
			else Q2[++m2]=Q[i];
		}
		else{
			Re tmp=T1.ask(Q[i].l,Q[i].r);
			if(Q[i].k<=tmp)Q1[++m1]=Q[i];
			else Q[i].k-=tmp,Q2[++m2]=Q[i];
		}
	for(Re i=1;i<=m1;++i)if(Q1[i].op&1)T1.add(Q1[i].id,-Q1[i].r);
	for(Re i=1;i<=m1;++i)Q[L+i-1]=Q1[i];
	for(Re i=1;i<=m2;++i)Q[L+m1+i-1]=Q2[i];
	sakura(l,mid,L,L+m1-1);
	sakura(mid+1,r,L+m1,R);
}
int main(){
	freopen("123.txt","r",stdin);
	in(n),in(T);
	for(Re i=1;i<=n;++i)in(a[i]),Q[++cnt]=(QAQ){a[i],1,0,1,i};
	while(T--){
		scanf(" %c",&op),in(x),in(y);
		if(op=='C')Q[++cnt]=(QAQ){a[x],-1,0,1,x},Q[++cnt]=(QAQ){a[x]=y,1,0,1,x};
		else in(z),Q[++cnt]=(QAQ){x,y,z,2,++Ans[0]};
	}
	sakura(-inf,inf,1,cnt);
	for(Re i=1;i<=Ans[0];++i)printf("%d\n",Ans[i]);
}
整体二分 静态区间第K小
53 行
CPP JSON
【整体二分(静态区间第K小)】 代码包含 in, add, ask_, ask, sakura 等核心函数,实现了 整体二分 的算法逻辑。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re v) — 加法更新 int ask_(Re x) — 核心算法函数 int ask(Re l,Re r) — 核心算法函数 void sakura(Re l,Re r,Re L,Re R) — 后缀数组 核心结构体:QAQ, BIT 关键配置: N=2e5+3,M=2e5+3,inf=1e9
C++ 52 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
#define LL long long
using namespace std;
const int N=2e5+3,M=2e5+3,inf=1e9;
int n,x,y,z,T,cnt,Ans[M];char op;
struct QAQ{int l,r,k,op,id;}Q[N+M],Q1[N+M],Q2[N+M];
inline void in(Re &x){
    int fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
struct BIT{
	int C[N];
	inline void add(Re x,Re v){while(x<=n)C[x]+=v,x+=x&-x;}
	inline int ask_(Re x){Re ans=0;while(x)ans+=C[x],x-=x&-x;return ans;}
	inline int ask(Re l,Re r){return ask_(r)-ask_(l-1);}
}T1;
inline void sakura(Re l,Re r,Re L,Re R){
	if(L>R)return;
	if(l==r){
		for(Re i=L;i<=R;++i)if(Q[i].op>1)Ans[Q[i].id]=l;
		return;
	}
	Re mid=l+r>>1,m1=0,m2=0;
	for(Re i=L;i<=R;++i)
		if(Q[i].op&1){
			if(Q[i].k<=mid)Q1[++m1]=Q[i],T1.add(Q[i].id,1);
			else Q2[++m2]=Q[i];
		}
		else{
			Re tmp=T1.ask(Q[i].l,Q[i].r);
			if(Q[i].k<=tmp)Q1[++m1]=Q[i];
			else Q[i].k-=tmp,Q2[++m2]=Q[i];
		}
	for(Re i=1;i<=m1;++i)if(Q1[i].op&1)T1.add(Q1[i].id,-1);
	for(Re i=1;i<=m1;++i)Q[L+i-1]=Q1[i];
	for(Re i=1;i<=m2;++i)Q[L+m1+i-1]=Q2[i];
	sakura(l,mid,L,L+m1-1);
	sakura(mid+1,r,L+m1,R);
}
int main(){
	freopen("123.txt","r",stdin);
	in(n),in(T);
	for(Re i=1;i<=n;++i)in(x),Q[++cnt]=(QAQ){0,0,x,1,i};
	for(Re i=1;i<=T;++i)in(x),in(y),in(z),Q[++cnt]=(QAQ){x,y,z,2,i};
	sakura(-inf,inf,1,cnt);
	for(Re i=1;i<=T;++i)printf("%d\n",Ans[i]);
}
已复制