二进制分组处理的问题有这样一些特性:
- 强制在线(离线一般可以CDQ分治)。
话说其实觉得二进制分组比CDQ分治好写诶 - 插入和查询。
- 对应的数据结构不支持增量构建(无法快速插入,只能全局构建)。
这种数据结构的例子有很多,如凸包、AC自动机、后缀数组(但后缀数组不适用二进制分组)甚至是主席树。
二进制分组的思想是维护很多组数据结构,适时暴力合并(具体看代码)。时空复杂度为原数据结构乘个log。不支持后缀数组是因为后缀数组的“操作”之间是互相有影响的(字符连成串),所以不能把它们分成好多组。
合并时最不济就是拿这些元素重新构建一遍,当然一些数据结构可能支持更优秀的合并方式:如凸包归并排序,trie可以类似线段树合并等。
可以顺便解决查询之前某一段操作的影响的问题,只要套上线段树即可。值得一提的是,对于这类问题如果不强制在线,可以把所有查询放到线段树上(类似线段树分治),然后把所有插入(一坨插入)在线段树上跑,在每个节点把可以属于这个节点的所有插入构建一个数据结构,最后销毁。这样空间可以做到。例如这道题:
【BZOJ4137】火星商店问题
我的做法:相当于离线之后的二进制分组,空间复杂度是的(线段树和trie树),有点卡。
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+50,M=1e7;
int n,m,s[N],v[N],n1,n2;
int c[M][2],tot,sum[M],rt[N];
int ql,qr,d,l,r;
struct node{int l,r,x,ql,qr;}Q[N];
struct node1{int x,y;bool friend operator <(node1 a,node1 b){return a.x<b.x;}}b[N];
vector<int>trt[N*4],tid[N*4];
int read(){
int x=0,c;
while(!isdigit(c=getchar()));
while(isdigit(c))x=x*10+(c^48),c=getchar();
return x;
}
void insert(int &x,int y,int d,int k){
x=++tot;sum[x]=sum[y]+1;
if(k==-1)return;int op=d>>k&1;
c[x][!op]=c[y][!op];
insert(c[x][op],c[y][op],d,k-1);
}
int query(int L,int R,int d,int k){
if(k==-1)return 0;int op=d>>k&1;
if(sum[c[R][op^1]]-sum[c[L][op^1]])return query(c[L][op^1],c[R][op^1],d,k-1)^1<<k;
return query(c[L][op],c[R][op],d,k-1);
}
void init(int x,int l,int r){
int nn=0;
for(int i=l;i<=r;i++)b[++nn]=(node1){s[i],v[i]};
sort(b+1,b+nn+1);
trt[x].resize(nn+1);tid[x].resize(nn+1);
for(int i=1;i<=nn;i++)insert(trt[x][i],trt[x][i-1],b[i].y,17),tid[x][i]=b[i].x;
}
void build(int x,int l,int r){
init(x,l,r);if(l==r)return;
int mid=(l+r)>>1;
build(x<<1,l,mid);build(x<<1|1,mid+1,r);
}
int query(int x){
int ll=lower_bound(tid[x].begin(),tid[x].end(),l)-tid[x].begin();
int rr=upper_bound(tid[x].begin(),tid[x].end(),r)-tid[x].begin();
if(ll==rr||!ll||!rr)return 0;ll--;rr--;
return query(trt[x][ll],trt[x][rr],d,17);
}
int query(int x,int l,int r){
if(ql>qr||qr<1)return 0;
if(l>=ql&&r<=qr)return query(x);
int mid=(l+r)>>1,ret=0;
if(ql<=mid)ret=query(x<<1,l,mid);
if(qr>mid)ret=max(ret,query(x<<1|1,mid+1,r));
return ret;
}
int main(){
n=read();m=read();
for(int i=1;i<=n;i++)insert(rt[i],rt[i-1],read(),17);
for(int i=1;i<=m;i++){
if(read())n1++,Q[n1].l=read(),Q[n1].r=read(),Q[n1].x=read(),Q[n1].qr=n2,Q[n1].ql=max(1,n2-read()+1);
else n2++,s[n2]=read(),v[n2]=read();
}
build(1,1,n2);
for(int i=1;i<=n1;i++){
ql=Q[i].ql;qr=Q[i].qr;d=Q[i].x;l=Q[i].l,r=Q[i].r;
printf("%d\n",max(query(rt[Q[i].l-1],rt[Q[i].r],Q[i].x,17),query(1,1,n2)));
}
return 0;
}
而刚才所述的做法详见yyb的博客(Orz yyb),空间是的。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define RG register
#define MAX 100100
#define lson (now<<1)
#define rson (now<<1|1)
#define pb(x) push_back(x)
inline int read()
{
RG int x=0,t=1;RG char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=-1,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return x*t;
}
struct Buy{int s,v,t;}q[MAX],tmp1[MAX],tmp2[MAX];
struct Ask{int l,r,tl,tr,x;}p[MAX];
bool cmp(Buy a,Buy b){return a.s<b.s;}
int rt[MAX];
namespace Trie//可持久化Trie
{
struct Trie{int son[2],w;}t[MAX<<5];
int tot,rt[MAX];
void insert(int &x,int ff,int w,int now)
{
t[x=++tot]=t[ff];t[x].w++;
if(now==-1)return;
bool c=w&(1<<now);
insert(t[x].son[c],t[ff].son[c],w,now-1);
}
int Query(int l,int r,int w,int now)
{
if(now==-1)return 0;
bool c=w&(1<<now);
int tmp=t[t[r].son[c^1]].w-t[t[l].son[c^1]].w;
if(tmp)return Query(t[l].son[c^1],t[r].son[c^1],w,now-1)+(1<<now);
else return Query(t[l].son[c],t[r].son[c],w,now-1);
}
}
int n,m,ans[MAX];
vector<int> seg[MAX<<2];
int cnt1,cnt2;
//对于线段树的每个节点插入对应的询问
//线段树的每个节点代表着一个购买的时间
//然后对于每个线段树上的节点，维护哪些询问出现在了这些时间之中
//所以对于一个节点维护一个vector，将出现在这段时间中的询问放入vector中
void Modify(int now,int l,int r,int L,int R,int x)
{
if(L>R)return;
if(L<=l&&r<=R){seg[now].pb(x);return;}
int mid=(l+r)>>1;
if(L<=mid)Modify(lson,l,mid,L,R,x);
if(R>mid)Modify(rson,mid+1,r,L,R,x);
}
int S[MAX],top;
//对于当前节点计算在区间内的答案
//考虑如何计算贡献，因为保证了当前节点内的所有询问的时间
//所以只需要考虑区间的问题了，因此按照区间维护可持久化Trie即可
int Binary(int x)
{
int l=1,r=top,ret=0;
while(l<=r)
{
int mid=(l+r)>>1;
if(S[mid]<=x)ret=mid,l=mid+1;
else r=mid-1;
}
return ret;
}
void Calc(int now,int L,int R)
{
top=Trie::tot=0;
for(int i=L;i<=R;++i)
{
S[++top]=q[i].s;
Trie::insert(rt[top],rt[top-1],q[i].v,17);
}
for(int i=0,len=seg[now].size();i<len;++i)
{
int k=seg[now][i];
int l=Binary(p[k].l-1),r=Binary(p[k].r);
ans[k]=max(ans[k],Trie::Query(rt[l],rt[r],p[k].x,17));
}
}
void Divide(int now,int l,int r,int L,int R)
{
if(L>R)return;int mid=(l+r)>>1,t1=0,t2=0;
Calc(now,L,R);if(l==r)return;
for(int i=L;i<=R;++i)
if(q[i].t<=mid)tmp1[++t1]=q[i];
else tmp2[++t2]=q[i];
for(int i=1;i<=t1;++i)q[i+L-1]=tmp1[i];
for(int i=1;i<=t2;++i)q[i+L-1+t1]=tmp2[i];
Divide(lson,l,mid,L,L+t1-1);
Divide(rson,mid+1,r,L+t1,R);
}
int main()
{
n=read();m=read();
for(int i=1;i<=n;++i)Trie::insert(rt[i],rt[i-1],read(),17);
for(int i=1;i<=m;++i)
{
int opt=read();
if(!opt)
{
int s=read(),v=read();++cnt1;
q[cnt1]=(Buy){s,v,cnt1};
}
else
{
int l=read(),r=read(),x=read(),d=read();
ans[++cnt2]=Trie::Query(rt[l-1],rt[r],x,17);
p[cnt2]=(Ask){l,r,max(1,cnt1-d+1),cnt1,x};
}
}
for(int i=1;i<=cnt2;++i)Modify(1,1,cnt1,p[i].tl,p[i].tr,i);
sort(&q[1],&q[cnt1+1],cmp);//按照商店的编号依次插入所有物品
Divide(1,1,cnt1,1,cnt1);
for(int i=1;i<=cnt2;++i)printf("%d\n",ans[i]);
return 0;
}
例题:
CF710F String Set Queries
维护一个字符串集合,支持加删字符串,查询集合中串在给定模板串中出现次数和,强制在线。
多字符串匹配问题,可以想到AC自动机,可是AC自动机是先建好trie后bfs构建的,不支持动态插串。这时满足上述提到的问题的性质,可以考虑二进制分组。其实这就是个板子题啦。
不过这题还要支持删除,我们发现我们维护的信息具有可减性,那么我们维护删除掉的串的信息,一减就好啦!
值得一提的是,trie树的合并可以做到很优秀,于是空间是的!
#include<bits/stdc++.h>
using namespace std;
const int N=6e5+50;
int m,rt[2][30],sz[2][30],c[N][26],tot,cnt[N],sum[N],fail[N],q[N],l,r,num[2],c2[N][26];char s[N];
void build(int d,int x){
int p=rt[d][x]=++tot;
for(int i=0;s[i];i++)p=c[p][s[i]-'a']=++tot;
cnt[p]=1;
}
void merge(int &x,int y){//类似线段树合并
if(!x||!y){x^=y;return;}
for(int i=0;i<26;i++)
merge(c[x][i],c[y][i]);
cnt[x]+=cnt[y];
}
void getfail(int rt){
l=1;r=0;
for(int i=0;i<26;i++)
if(c[rt][i])fail[c2[rt][i]=q[++r]=c[rt][i]]=rt;
else c2[rt][i]=rt;//要把原trie上的边保留,因为合并时要用到
while(l<=r){
int x=q[l++];sum[x]=sum[fail[x]]+cnt[x];
for(int i=0;i<26;i++){
int y=c[x][i],z=c2[fail[x]][i];
if(y)fail[y]=z,c2[x][i]=q[++r]=y;
else c2[x][i]=z;
}
}
}
int query(int d){
int ret=0;
for(int i=1;i<=num[d];i++)
for(int j=0,p=rt[d][i];s[j];j++)
ret+=sum[p=c2[p][s[j]-'a']];
return ret;
}
void change(int d){
build(d,++num[d]);sz[d][num[d]]=1;
while(num[d]>1&&sz[d][num[d]]==sz[d][num[d]-1])//其实类似自底向上的线段树
merge(rt[d][num[d]-1],rt[d][num[d]]),sz[d][--num[d]]*=2;
getfail(rt[d][num[d]]);
}
int main(){
scanf("%d",&m);
for(int i=1,op;i<=m;i++){
scanf("%d%s",&op,s);
if(op==3)printf("%d\n",query(0)-query(1)),fflush(stdout);
else change(op-1);
}
return 0;
}
P3309 [SDOI2014]向量集
维护一个向量集合,支持插入向量,查询第L到第R个插入的向量与给定向量点乘的最大值,强制在线。
首先根据点乘的定义式随便化化式子发现是可以斜率优化的形式,于是转化成了维护凸包。
凸包的随机插入是比较困难的(平衡树?)而且我们发现题目里竟然还有查询第L到第R个这类的字眼,那么二进制分组他不香嘛?于是还是个板子题...
值得一提的是两个凸包合并之后原来的凸包还要留着,所以空间是的。没有区间查询的二进制分组一般可以用垃圾回收等技巧优化空间。
#include<bits/stdc++.h>
#define LL long long
#define pb push_back
using namespace std;
const int N=4e5+50,inf=0x7fffffff;
int n,id[N],xx,yy,m,ql,qr;char S[3],T[3];LL ans;
struct node{
vector<int>x,y;
void insert(int xx,int yy){
int n;
while((n=x.size()-1)>0&&1ll*(y[n]-y[n-1])*(xx-x[n])<=1ll*(yy-y[n])*(x[n]-x[n-1]))x.pop_back(),y.pop_back();
x.pb(xx);y.pb(yy);
}
void merge(node L,node R){
int i=0,j=0;
for(;i<L.x.size()&&j<R.x.size();)
if(L.x[i]<R.x[j]||L.x[i]==R.x[j]&&L.y[i]<R.y[j])insert(L.x[i],L.y[i]),i++;
else insert(R.x[j],R.y[j]),j++;
for(;i<L.x.size();i++)insert(L.x[i],L.y[i]);
for(;j<R.x.size();j++)insert(R.x[j],R.y[j]);
}
LL query(int xx,int yy){
if(!x.size())return -1e18;
int l=1,r=x.size()-1,ans=0;
while(l<=r){
int mid=(l+r)>>1;
if(1ll*(y[mid]-y[mid-1])*yy+1ll*(x[mid]-x[mid-1])*xx>=0)ans=mid,l=mid+1;
else r=mid-1;
}
return 1ll*xx*x[ans]+1ll*yy*y[ans];
}
}t[2][N*4];
void build(int x,int l,int r){
if(l==r){id[l]=x;return;}
int mid=(l+r)>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
}
void add(){
int x=id[++m];
t[0][x].x.pb(xx);t[1][x].x.pb(-xx);
t[0][x].y.pb(yy);t[1][x].y.pb(-yy);
for(;(x&1)&&x>1;x>>=1)for(int k=0;k<2;k++)
t[k][x>>1].merge(t[k][x^1],t[k][x]);
}
void query(int x,int l,int r){
if(l>=ql&&r<=qr){ans=max(ans,yy>0?t[0][x].query(xx,yy):t[1][x].query(-xx,-yy));return;}
int mid=(l+r)>>1;
if(ql<=mid)query(x<<1,l,mid);
if(qr>mid)query(x<<1|1,mid+1,r);
}
int main(){
scanf("%d%s",&n,S);
build(1,1,n);
for(int i=1;i<=n;i++){
scanf("%s%d%d",T,&xx,&yy);
if(S[0]!='E')xx^=ans,yy^=ans;
if(T[0]=='A')add();
else{
scanf("%d%d",&ql,&qr);
if(S[0]!='E')ql^=ans,qr^=ans;
ans=-1e18;query(1,1,n);
printf("%lld\n",ans);ans&=inf;
}
}
return 0;
}