整体二分学习笔记

整体二分学习笔记

整体二分，就是对所有的操作进行一个整体的二分答案，需要数据结构题满足以下性质：

• 询问的答案具有可二分性。
• 修改对判定答案的贡献相对独立，修改之间互不影响效果。
• 修改如果对判定答案有贡献，则贡献为一确定的与判定标准无关的值。
• 贡献满足交换律、结合律，具有可加性。
• 题目允许离线。

---

例题引入：P3332 [ZJOI2013]K大数查询

Solution1：忘了是啥线段树 套 忘了是啥线段树。

太麻烦了。。。。。。。

点击查看代码

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace __gnu_pbds;
#define int long long// 区间和线段树套权值线段树using namespace std;const int Size=(1<<20)+1;
char buf[Size],*p1=buf,*p2=buf;
char buffer[Size];
int op1=-1;
const int op2=Size-1;
#define getchar()                                                              \
(tt == ss && (tt=(ss=In)+fread(In, 1, 1 << 20, stdin), ss == tt)     \? EOF                                                                 \: *ss++)
char In[1<<20],*ss=In,*tt=In;
inline int read()
{int x=0,c=getchar(),f=0;for(;c>'9'||c<'0';f=c=='-',c=getchar());for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);return f?-x:x;
}
inline void write(int x)
{if(x<0) x=-x,putchar('-');if(x>9)  write(x/10);putchar(x%10+'0');
}int n,m;
int root[1<<20],tot;
struct Tree{//int lazy,cnt,lp,rp;
}tree2[(int)2e7];const int MINN=0,MAXN=50001;void pushdown(int l,int mid,int r,Tree &p)
{if(!p.lazy) return;if(l==r) return;if(!p.lp) p.lp=++tot;if(!p.rp) p.rp=++tot;tree2[p.lp].cnt+=(mid-l+1)*p.lazy;tree2[p.rp].cnt+=(r-mid)*p.lazy;tree2[p.lp].lazy+=p.lazy;tree2[p.rp].lazy+=p.lazy;p.lazy=0;
}void add2(int l,int r,int sl,int sr,int &p)
{if(!p) p=++tot;if(sl<=l&&r<=sr)// if(l==r){tree2[p].cnt+=r-l+1;tree2[p].lazy++;return;}int mid=(l+r)>>1;pushdown(l,mid,r,tree2[p]);if(sl<=mid) add2(l,mid,sl,sr,tree2[p].lp);if(sr>mid) add2(mid+1,r,sl,sr,tree2[p].rp);tree2[p].cnt=tree2[tree2[p].lp].cnt+tree2[tree2[p].rp].cnt;
}void add(int l,int r,int sl,int sr,int x,int p)
{add2(1,n,sl,sr,root[p]);if(l==r) return;int mid=(l+r)>>1,lp=(p<<1),rp=(p<<1)|1;if(x<=mid) add(l,mid,sl,sr,x,lp);else add(mid+1,r,sl,sr,x,rp);
}int query_sum(int l,int r,int sl,int sr,int &p)
{if(!p) return 0;if(sl<=l&&r<=sr) return tree2[p].cnt;int mid=(l+r)>>1,ans=0;pushdown(l,mid,r,tree2[p]);if(sl<=mid) ans=query_sum(l,mid,sl,sr,tree2[p].lp);if(sr>mid) ans+=query_sum(mid+1,r,sl,sr,tree2[p].rp);return ans;
}int maxkth(int l,int r,int sl,int sr,long long k,int p)
{if(l==r) return l;int mid=(l+r)>>1;int lp=(p<<1),rp=(p<<1)|1;long long nw=query_sum(1,n,sl,sr,root[rp]);if(nw>=k) return maxkth(mid+1,r,sl,sr,k,rp);else return maxkth(l,mid,sl,sr,k-nw,lp);
}struct Ask{int op,l,r;long long c;
}ask[50005];
gp_hash_table<int,int>mp;
int a[50005],cnta;
int id[50005];
signed main()
{//mt19937_64 myrand(time(0));n=read();m=read();for(int i=1;i<=m;i++){int op=read(),l=read(),r=read(),c=read();ask[i]={op,l,r,c};if(op==1) a[++cnta]=c;}sort(a+1,a+1+cnta);a[0]=-50001;int cntb=0;for(int i=1;i<=cnta;i++)if(a[i]!=a[i-1]){++cntb;mp[a[i]]=cntb;id[cntb]=a[i];} for(int i=1;i<=m;i++){int op=ask[i].op,l=ask[i].l,r=ask[i].r;if(op==1) add(1,cnta,l,r,mp[ask[i].c],1);if(op==2) cout<<id[maxkth(1,cnta,ask[i].l,ask[i].r,ask[i].c,1)]<<"\n";}return 0;
}

Solution2：整体二分。

我们考虑对于一个询问怎么朴素二分求解。

假设询问区间 \([l,r]\) 中的第 \(k\) 大。

有一个想法是，我们二分可能的答案 \(mid\)，再暴力将 \([l,r]\) 中 \(> mid\) 的数设为 \(1\)，\(\le mid\) 的数设为 \(0\)，统计 \([l,r]\) 中 \(1\) 的个数，设为 \(cnt\)，如果 \(cnt\ge k\)，表明答案一定 \(>mid\)，反之答案一定 \(\le mid\)。然后缩小二分的区间，继续进行上述操作。

至多 \(O(\log V)\) 次二分后，答案一定确定，此时单次二分复杂度最多 \(O(n \log V)\)。

然后考虑 \(q\) 组询问。我们仍尝试根据上述过程求解答案。

我们尝试设计一个二分框架 \(\operatorname{solve}(ql,qr,L,R)\)，表示：

• 操作序列 \([ql,qr]\) 的答案在值域 \([L,R]\) 中。假设当前值域中点为 \(mid\)。

具体地：

对于添数操作，表示添加的值 \(c\) 在值域 \([L,R]\) 中。
对于查询操作，表示该查询的答案在值域 \([L,R]\) 中。

判定完当前贡献后，将操作序列分成答案在值域 \([l,mid]\) 和 \([mid+1,r]\) 两部分，分别向下递归求解。

注意边界问题。

考虑如何判定当前贡献。

我们仍延续单个询问二分的过程，对操作区间 \([ql,qr]\) 中 \(c > mid\) 的区间添数操作，将其视为区间添数 \(1\)，反之则视为 \(0\)。我们需要一个数据结构来支持区间添数 \(1\)（可以视为区间加 \(1\)），区间查询 \(1\) 的个数，自然想到要用线段树来维护这个过程。

然后我们先从左到右扫一遍操作序列。再开两个临时操作序列 \(a1,a2\)，分别存答案在值域 \([L,mid]\) 和 \([mid+1,R]\) 时的操作序列。

对于添数操作，若添加的值 \(c > mid\)，那么在线段树上区间加 \(1\)，并将该操作存进 \(a_2\)。反之存进 \(a_1\)。

对于查询操作，直接在线段树上查询该询问 \(id\) 的询问区间 \([l_{id},r_{id}]\) 中 \(1\) 的个数，设为 \(nw\)，若 \(nw+tmp_{id}>k\)（\(tmp\) 一回再说），那么该询问答案一定在值域 \([mid+1,R]\)，将该询问存进 \(a_2\) 中，反之令 \(tmp_{id}+nw \to tmp_{id}\)，并将该询问存进 \(a_1\)。

你发现，\(tmp_{id}\) 作用是记录第 \(id\) 个询问区间中所有 \(>\) 当前二分值域上界 \(R\) 的数的个数。通过这种类似主席树的方法，我们可以严格保证一个操作只会被分进 \(a_1\) 或 \(a_2\) 其中之一。

扫完操作序列 \([ql,qr]\) 后，需要清空线段树，简单实现是扫一遍 \(a_2\)，将其中所有的添数操作所对应的区间减 \(1\) 即可。

假设现在 \(a_1\) 中有 \(cnt_1\) 个操作。我们将 \(a_1\) 序列拷贝到 \(a\) 序列下标 \([ql,ql+cnt_1)\) 上，将 \(a_2\) 拷贝到 \(a\) 序列下标 \([ql+cnt,qr]\) 上。

递归求解 \(\operatorname{solve}(ql,ql+cnt_1-1,L,mid)\) 和 \(\operatorname{solve}(ql+cnt_1,qr,mid+1,R)\)。

二分的边界条件：当 \(L=R\) 是，操作区间 \([ql,qr]\) 中的所有询问的答案为 \(L\)。

时间复杂度分析：

每个操作最多被遍历 \(O(\log V)\) 次，每次遍历一个操作的复杂度为线段树的 \(O(\log n)\)。

总时间复杂度 \(O(m \log V \log n)\)，\(n,m,V\) 同阶，可以看成 \(O(n \log^2 n)\)。可以通过本题。

Code：

#include<bits/stdc++.h>
#define int long longusing namespace std;const int Size=(1<<20)+1;
char buf[Size],*p1=buf,*p2=buf;
char buffer[Size];
int op1=-1;
const int op2=Size-1;
#define getchar()                                                              \
(tt == ss && (tt=(ss=In)+fread(In, 1, 1 << 20, stdin), ss == tt)     \? EOF                                                                 \: *ss++)
char In[1<<20],*ss=In,*tt=In;
inline int read()
{int x=0,c=getchar(),f=0;for(;c>'9'||c<'0';f=c=='-',c=getchar());for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);return f?-x:x;
}
inline void write(int x)
{if(x<0) x=-x,putchar('-');if(x>9)  write(x/10);putchar(x%10+'0');
}const int N=5e4+5;
int n,m;
int laz[N<<2],sum[N<<2];
#define lp (p<<1)
#define rp ((p<<1)|1)void pushdown(int p,int l,int mid,int r)
{if(!laz[p]) return;laz[lp]+=laz[p];laz[rp]+=laz[p];sum[lp]+=(mid-l+1)*laz[p];sum[rp]+=(r-mid)*laz[p];laz[p]=0;
}void pushup(int p)
{sum[p]=sum[lp]+sum[rp];
}void add(int l,int r,int sl,int sr,int k,int p)
{if(l>r||sl>sr) return;if(sl<=l&&r<=sr) { laz[p]+=k; sum[p]+=k*(r-l+1); return; }int mid=(l+r)>>1;pushdown(p,l,mid,r);if(sl<=mid) add(l,mid,sl,sr,k,lp);if(sr>mid) add(mid+1,r,sl,sr,k,rp);pushup(p);
}int query(int l,int r,int sl,int sr,int p)
{if(l>r||sl>sr) return 0;if(sl<=l&&r<=sr) return sum[p];int mid=(l+r)>>1,ans=0;pushdown(p,l,mid,r);if(sl<=mid) ans+=query(l,mid,sl,sr,lp);if(sr>mid) ans+=query(mid+1,r,sl,sr,rp);pushup(p);return ans;
}struct Node{int op,x,y,z,id;
}a[N<<1],a1[N<<1],a2[N<<1];
int ans[N],tmp[N];void solve(int ql,int qr,int l,int r)
{if(l>r||ql>qr) return;if(l==r){for(int i=ql;i<=qr;i++) if(a[i].op==2) ans[a[i].id]=l;return;}int mid=(l+r)>>1;int cnt1=0,cnt2=0;for(int i=ql;i<=qr;i++){if(a[i].op==1){if(a[i].z>mid) add(1,n,a[i].x,a[i].y,1,1),a2[++cnt2]=a[i];else a1[++cnt1]=a[i];}else{int nw=query(1,n,a[i].x,a[i].y,1);if(nw+tmp[a[i].id]>=a[i].z) a2[++cnt2]=a[i];else a1[++cnt1]=a[i],tmp[a[i].id]+=nw;}}for(int i=1;i<=cnt2;i++)if(a2[i].op==1) add(1,n,a2[i].x,a2[i].y,-1,1);for(int i=1;i<=cnt1;i++) a[i+ql-1]=a1[i];for(int i=1;i<=cnt2;i++) a[qr-cnt2+i]=a2[i];// cout<<"["<<l<<","<<r<<"] mid="<<mid<<" cntl="<<cnt1<<" cntr="<<cnt2<<"\n";solve(ql,ql+cnt1-1,l,mid);solve(ql+cnt1,qr,mid+1,r);
}signed main()
{// freopen("P3332.in","r",stdin);// freopen("P3332.out","w",stdout);n=read();m=read();for(int i=1;i<=m;i++){int op=read(),x=read(),y=read(),z=read();a[i]={op,x,y,z,i};}solve(1,m,-n-1,n+1);for(int i=1;i<=m;i++)if(ans[i]) write(ans[i]),putchar('\n');//mt19937_64 myrand(time(0));return 0;
}

log

• 尝试学习次数：\(x\) 次。

• 时间跨度：\(8\) 个月。