526互联

整体二分

发布时间 2023-11-12 12:59:52作者: mRXxy0o0

使用场景

  1. 询问的答案具有可二分性（对于单个询问可以二分答案）
  2. 题目允许使用离线算法
  3. 修改对判定答案的贡献互相独立，修改之间互不影响效果
  4. 修改如果对判定答案有贡献，则贡献为一确定的与判定标准无关的值
  5. 贡献满足交换律，结合律，具有可加性

实现

对答案所在的值域进行二分，记录值域区间 \([l,r]\)，符合条件的询问区间 \([L,R]\)。通过对 \(mid\) 位置的讨论，分辨每一个询问是否满足限制，继续分治。

需要注意辅助数据结构的清空或重赋为某个特定阶段的值，以及左右区间的先后顺序。

一般版

inline void solve(int l,int r,int L,int R){
	if(l>r||L>R) return ;
	if(a[l]==a[r]){
		for(int i=L;i<=R;++i) if(Q[i].tp) ans[Q[i].tp]=a[l];//记录答案
		return ;
	}
	int mid=l+r>>1,cnt1=0,cnt2=0;
	for(int i=l;i<=mid;++i) //加入左部贡献 
	for(int i=L;i<=R;++i) //枚举询问可不可以并放入Q1、Q2内 
	for(int i=l;i<=mid;++i) //清空 
	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);
}

判断无解

inline void solve(int l,int r,int L,int R){
	if(l>r||L>R) return ;
	int mid=l+r>>1,cnt1=0,cnt2=0;
	for(int i=l;i<=mid;++i) //加入左部贡献 
	for(int i=L;i<=R;++i) //枚举询问可不可以并放入Q1、Q2内 
	for(int i=l;i<=mid;++i) //清空 
	if(l==r){
		for(int i=1;i<=cnt1;++i) ans[Q1[i].id]=a[l].d;//最后再做一次
		return ;
	}
	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);
}

复杂度&流程

板子 \(O(n\log n)\)，可以套上树状数组、线段树、主席树 \(\dots\)

每个值被讨论 \(\log\) 次，每个询问被讨论 \(\log\) 次。在这道题中，就利用这点，可以暴力枚举询问不重复对应的点。