二进制分组思想很简单，就是把下标拆成几个2的次幂的和，对每个2的次幂维护答案，复杂度是暴力重构一组的复杂度乘log（如果可以归并可能会少个log）。

这里其实想整理下一些修改独立的数据结构题的套路。

离线算法：

　　(1) 只有插入：CDQ分治。

　　(2) 有删除：

　　　　支持删除操作：CDQ分治。

　　　　不支持删除但支持按插入反序撤销：线段树分治。

　　　　不支持删除与撤销：时间倒流。

　　(3)每次询问的是某个修改区间内的所有修改都生效时的答案：分治+前后缀和。

　　(4)答案可二分、修改的贡献具有交换律、结合律、可加性：整体二分。

　　(5)每次询问的是一个区间：莫队、回滚莫队。

在线算法： (1) 随机。 (2) 二进制分组。

 

二进制分组题表：

[BZOJ4140]共点圆加强版

论文题。化下式子发现是一个半平面，于是问题变为在线插入点并询问某个半平面内是否有点。维护点集的凸包，每次合并两组的时候暴力重构即可。

1 #include
      
        2 #include
       
         3 #include
        
          4 #define pb push_back 5 #define rep(i,l,r) for (int i=(l); i<=(r); i++) 6 using namespace std; 7  8 const int N=500100; 9 double x,y;10 int n,ans,top,op;11 struct P{ double x,y; }a[N];12 bool operator <(const P &a,const P &b){ return a.x==b.x ? a.y
         
          b.y ? 1e18 : -1e18;16     return (a.y-b.y)/(a.x-b.x);17 }18 19 struct Gr{20     vector
          
p,q; int tot,top;21     void ins(P x){ tot++; p.pb(x); }22     void clear(){ p.clear(); q.clear(); tot=top=0; }23 24     void build(){25         sort(p.begin(),p.end()); top=1; q.clear(); q.pb(p[0]);26         rep(i,1,tot-1){27             while (top>1 && sl(q[top-1],q[top-2])-sl(q[top-1],p[i])>=0) top--,q.pop_back();28             q.pb(p[i]); top++;29         }30     }31 32     bool que(double x,double y){33         double k=-x/y; int l=1,r=top-1,res=0;34         while (l<=r){35             int mid=(l+r)>>1;36             if (sl(q[mid],q[mid-1])<=k) l=mid+1,res=mid; else r=mid-1;37         }38         return 2*x*q[res].x+2*y*q[res].y>=x*x+y*y;39     }40 }B[50];41 42 void ins(double x,double y){43     B[++top].ins((P){x,y});44     while (top>1 && B[top].tot==B[top-1].tot){45         rep(i,0,B[top].tot-1) B[top-1].ins(B[top].p[i]);46         B[top--].clear();47     }48     B[top].build();49 }50 51 bool que(double x,double y){52     if (!top) return 0;53     rep(i,1,top) if (!B[i].que(x,y)) return 0;54     return 1;55 }56 57 int main(){58     scanf("%d",&n);59     rep(i,1,n){60         scanf("%d%lf%lf",&op,&x,&y); x+=ans; y+=ans;61         if (!op) ins(x,y);62         else if (que(x,y)) ans++,puts("Yes"); else puts("No");63     }64     return 0;65 }
         
        
       
      

 

[BZOJ2989]数列

树套树或者CDQ分治或者3D-Tree模板题，大家都用它来练二进制分组。

对插入时间二进制分组，然后就是一个二维数点问题，两组的合并最好用归并。

主席树是一个DAG，要注意删除与垃圾回收的实现。

1 #include
      
        2 #include
       
         3 #include
        
          4 #define mp make_pair 5 #define pb push_back 6 #define rep(i,l,r) for (int i=(l); i<=(r); i++) 7 using namespace std; 8  9 const int N=200010,M=200000,K=65000,inf=1e9;10 char op[10];11 bool vis[N<<5];12 int n,Q,top,tot,nd,a[N],rt[20][N],ls[N<<5],rs[N<<5],v[N<<5],stk[N<<5];13 vector
         
          
            >t,ve[20];14 15 int get(){16     if (top) { vis[stk[top]]=1; return stk[top--]; }17         else{ vis[++nd]=1; return nd; }18 }19 20 int que(int x,int y,int L,int R,int l,int r){21     if (L==l && r==R) return v[y]-v[x];22     int mid=(L+R)>>1;23     if (r<=mid) return que(ls[x],ls[y],L,mid,l,r);24     else if (l>mid) return que(rs[x],rs[y],mid+1,R,l,r);25         else return que(ls[x],ls[y],L,mid,l,mid)+que(rs[x],rs[y],mid+1,R,mid+1,r);26 }27 28 void mdf(int y,int &x,int L,int R,int k){29     x=get(); ls[x]=ls[y]; rs[x]=rs[y]; v[x]=v[y]+1;30     if (L==R) return;31     int mid=(L+R)>>1;32     if (k<=mid) mdf(ls[y],ls[x],L,mid,k);33         else mdf(rs[y],rs[x],mid+1,R,k);34 }35 36 void del(int &x){37     if (!vis[x]) return;38     stk[++top]=x; vis[x]=0;39     del(ls[x]); del(rs[x]); v[x]=0; x=0;40 }41 42 void ins(int x,int y){43     ve[++tot].pb(mp(x,y)); mdf(0,rt[tot][1],1,M,y);44     while (tot>1 && ve[tot-1].size()==ve[tot].size()){45         int t1=0,t2=0,ed=ve[tot].size(); t.clear();46         rep(i,1,ed) del(rt[tot-1][i]);47         rep(i,1,ed) del(rt[tot][i]);48         while (t1<(int)ve[tot-1].size() || t2<(int)ve[tot].size()){49             if (t1<(int)ve[tot-1].size() && (t2==(int)ve[tot].size() || ve[tot-1][t1]
          
         
        
       
      

 

[CF710F]String Set Queries

没有插入删除就是AC自动机模板题。发现删除操作就是另维护一个AC自动机计算已删除的串的贡献，于是只用考虑插入。

CDQ分治或二进制分组均可。AC自动机是有向图（还可能存在自环），所以同样要注意删除和垃圾回收的实现。

平时只建一个AC自动机时，根是0，所以fail和son有时会不赋值。建多棵的时候就要注意把所有为0的指针都要指向rt。

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #define rep(i,l,r) for (int i=(l); i<=(r); i++)  7 #define pb push_back  8 using namespace std;  9  10 const int N=300100; 11 string s; 12 int m,op,top,nd,top1,top2,son[N][27],fail[N],v[N],stk[N],q[N]; 13  14 int get(){ return top ? stk[top--] : ++nd; } 15  16 void ins(int x,string s){ 17     int len=s.length(); 18     rep(i,0,len-1){ 19         if (!son[x][s[i]-'a']) son[x][s[i]-'a']=get(); 20         x=son[x][s[i]-'a']; 21     } 22     v[x]++; 23 } 24  25 void del(int x){ 26     if (!fail[x]) return; 27     fail[x]=v[x]=0; stk[++top]=x; 28     rep(i,0,25) del(son[x][i]),son[x][i]=0; 29 } 30  31 struct Gr{ 32     vector
           
            p; int tot,rt; 33 void ins(string s){ p.pb(s); tot++; } 34 void clear(){ del(rt); rt=get(); p.clear(); tot=0; } 35 void build(){ 36 del(rt); rt=get(); 37 rep(i,0,tot-1) ::ins(rt,p[i]); 38 int st=0,ed=0; fail[rt]=rt; 39 rep(i,0,25) if (son[rt][i]) q[++ed]=son[rt][i],fail[son[rt][i]]=rt; 40 while (st
            
             1 && A[top1].tot==A[top1-1].tot){ 69 rep(i,0,A[top1].tot-1) A[top1-1].ins(A[top1].p[i]); 70 A[top1--].clear(); 71 } 72 A[top1].build(); 73 } 74 75 void del(string s){ 76 top2++; B[top2].clear(); B[top2].ins(s); 77 while (top2>1 && B[top2].tot==B[top2-1].tot){ 78 rep(i,0,B[top2].tot-1) B[top2-1].ins(B[top2].p[i]); 79 B[top2--].clear(); 80 } 81 B[top2].build(); 82 } 83 84 int que(string s){ 85 int res=0; 86 rep(i,1,top1) res+=A[i].que(s); 87 rep(i,1,top2) res-=B[i].que(s); 88 return res; 89 } 90 91 int main(){ 92 freopen("710F.in","r",stdin); 93 freopen("710F.out","w",stdout); 94 for (scanf("%d",&m); m--; ){ 95 cin>>op>>s; 96 if (op==1) ins(s); 97 if (op==2) del(s); 98 if (op==3) cout<
             
              <