二进制分组

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

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

离线算法：

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

　　(2) 有删除：

　　　　支持删除操作：CDQ分治。

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

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

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

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

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

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

二进制分组题表：

[BZOJ4140]共点圆加强版

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

#include<cstdio>
#include<vector>
#include<algorithm>
#define pb push_back
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
using namespace std;

const int N=500100;
double x,y;
int n,ans,top,op;
struct P{ double x,y; }a[N];
bool operator <(const P &a,const P &b){ return a.x==b.x ? a.y<b.y : a.x<b.x; }

double sl(P a,P b){
    if (a.x==b.x) return a.y>b.y ? 1e18 : -1e18;
    return (a.y-b.y)/(a.x-b.x);
}

struct Gr{
    vector<P>p,q; int tot,top;
    void ins(P x){ tot++; p.pb(x); }
    void clear(){ p.clear(); q.clear(); tot=top=0; }

    void build(){
        sort(p.begin(),p.end()); top=1; q.clear(); q.pb(p[0]);
        rep(i,1,tot-1){
            while (top>1 && sl(q[top-1],q[top-2])-sl(q[top-1],p[i])>=0) top--,q.pop_back();
            q.pb(p[i]); top++;
        }
    }

    bool que(double x,double y){
        double k=-x/y; int l=1,r=top-1,res=0;
        while (l<=r){
            int mid=(l+r)>>1;
            if (sl(q[mid],q[mid-1])<=k) l=mid+1,res=mid; else r=mid-1;
        }
        return 2*x*q[res].x+2*y*q[res].y>=x*x+y*y;
    }
}B[50];

void ins(double x,double y){
    B[++top].ins((P){x,y});
    while (top>1 && B[top].tot==B[top-1].tot){
        rep(i,0,B[top].tot-1) B[top-1].ins(B[top].p[i]);
        B[top--].clear();
    }
    B[top].build();
}

bool que(double x,double y){
    if (!top) return 0;
    rep(i,1,top) if (!B[i].que(x,y)) return 0;
    return 1;
}

int main(){
    scanf("%d",&n);
    rep(i,1,n){
        scanf("%d%lf%lf",&op,&x,&y); x+=ans; y+=ans;
        if (!op) ins(x,y);
        else if (que(x,y)) ans++,puts("Yes"); else puts("No");
    }
    return 0;
}

[BZOJ2989]数列

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

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

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

#include<cstdio>
#include<vector>
#include<algorithm>
#define mp make_pair
#define pb push_back
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
using namespace std;

const int N=200010,M=200000,K=65000,inf=1e9;
char op[10];
bool vis[N<<5];
int n,Q,top,tot,nd,a[N],rt[20][N],ls[N<<5],rs[N<<5],v[N<<5],stk[N<<5];
vector<pair<int,int> >t,ve[20];

int get(){
    if (top) { vis[stk[top]]=1; return stk[top--]; }
        else{ vis[++nd]=1; return nd; }
}

int que(int x,int y,int L,int R,int l,int r){
    if (L==l && r==R) return v[y]-v[x];
    int mid=(L+R)>>1;
    if (r<=mid) return que(ls[x],ls[y],L,mid,l,r);
    else if (l>mid) return que(rs[x],rs[y],mid+1,R,l,r);
        else return que(ls[x],ls[y],L,mid,l,mid)+que(rs[x],rs[y],mid+1,R,mid+1,r);
}

void mdf(int y,int &x,int L,int R,int k){
    x=get(); ls[x]=ls[y]; rs[x]=rs[y]; v[x]=v[y]+1;
    if (L==R) return;
    int mid=(L+R)>>1;
    if (k<=mid) mdf(ls[y],ls[x],L,mid,k);
        else mdf(rs[y],rs[x],mid+1,R,k);
}

void del(int &x){
    if (!vis[x]) return;
    stk[++top]=x; vis[x]=0;
    del(ls[x]); del(rs[x]); v[x]=0; x=0;
}

void ins(int x,int y){
    ve[++tot].pb(mp(x,y)); mdf(0,rt[tot][1],1,M,y);
    while (tot>1 && ve[tot-1].size()==ve[tot].size()){
        int t1=0,t2=0,ed=ve[tot].size(); t.clear();
        rep(i,1,ed) del(rt[tot-1][i]);
        rep(i,1,ed) del(rt[tot][i]);
        while (t1<(int)ve[tot-1].size() || t2<(int)ve[tot].size()){
            if (t1<(int)ve[tot-1].size() && (t2==(int)ve[tot].size() || ve[tot-1][t1]<ve[tot][t2])) t.pb(ve[tot-1][t1++]);
                else t.pb(ve[tot][t2++]);
            mdf(rt[tot-1][t1+t2-1],rt[tot-1][t1+t2],1,M,t[t1+t2-1].second);
        }
        ve[tot-1]=t; ve[tot].clear(); tot--;
    }
}

int que(int x,int y,int d){
    int res=0;
    rep(i,1,tot){
        int k1=lower_bound(ve[i].begin(),ve[i].end(),mp(x+d,inf))-ve[i].begin();
        int k2=lower_bound(ve[i].begin(),ve[i].end(),mp(x-d,0))-ve[i].begin();
        res+=que(rt[i][k2],rt[i][k1],1,M,max(1,y-d),min(y+d,M));
    }
    return res;
}

int main(){
    freopen("bzoj2989.in","r",stdin);
    freopen("bzoj2989.out","w",stdout);
    scanf("%d%d",&n,&Q);
    rep(i,1,n) scanf("%d",&a[i]),ins(a[i]+i,a[i]-i+K);
    while (Q--){
        scanf("%s",op); int x,y; scanf("%d%d",&x,&y);
        if (op[0]=='Q') printf("%d
",que(a[x]+x,a[x]-x+K,y));
            else a[x]=y,ins(a[x]+x,a[x]-x+K);
    }
    return 0;
}

[CF710F]String Set Queries

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

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

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

#include<cstdio>
#include<string>
#include<vector>
#include<iostream>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
#define pb push_back
using namespace std;

const int N=300100;
string s;
int m,op,top,nd,top1,top2,son[N][27],fail[N],v[N],stk[N],q[N];

int get(){ return top ? stk[top--] : ++nd; }

void ins(int x,string s){
    int len=s.length();
    rep(i,0,len-1){
        if (!son[x][s[i]-'a']) son[x][s[i]-'a']=get();
        x=son[x][s[i]-'a'];
    }
    v[x]++;
}

void del(int x){
    if (!fail[x]) return;
    fail[x]=v[x]=0; stk[++top]=x;
    rep(i,0,25) del(son[x][i]),son[x][i]=0;
}

struct Gr{
    vector<string>p; int tot,rt;
    void ins(string s){ p.pb(s); tot++; }
    void clear(){ del(rt); rt=get(); p.clear(); tot=0; }
    void build(){
        del(rt); rt=get();
        rep(i,0,tot-1) ::ins(rt,p[i]);
        int st=0,ed=0; fail[rt]=rt;
        rep(i,0,25) if (son[rt][i]) q[++ed]=son[rt][i],fail[son[rt][i]]=rt;
        while (st<ed){
            int x=q[++st];
            rep(i,0,25){
                int c=son[fail[x]][i];
                if (son[x][i]) fail[son[x][i]]=c?c:rt,q[++ed]=son[x][i];
                    else son[x][i]=c?c:rt;
            }
            v[x]+=v[fail[x]];
        }
    }
    int que(string s){
        int res=0,x=rt,len=s.length();
        rep(i,0,len-1){
            int c=s[i]-'a';
            if (son[x][c]) x=son[x][c];
            else{
                int p=fail[x];
                while (p!=rt && !son[p][c]) p=fail[p];
                if (son[p][c]) x=son[p][c];
            }
            res+=v[x];
        }
        return res;
    }
}A[20],B[20];

void ins(string s){
    top1++; A[top1].clear(); A[top1].ins(s);
    while (top1>1 && A[top1].tot==A[top1-1].tot){
        rep(i,0,A[top1].tot-1) A[top1-1].ins(A[top1].p[i]);
        A[top1--].clear();
    }
    A[top1].build();
}

void del(string s){
    top2++; B[top2].clear(); B[top2].ins(s);
    while (top2>1 && B[top2].tot==B[top2-1].tot){
        rep(i,0,B[top2].tot-1) B[top2-1].ins(B[top2].p[i]);
        B[top2--].clear();
    }
    B[top2].build();
}

int que(string s){
    int res=0;
    rep(i,1,top1) res+=A[i].que(s);
    rep(i,1,top2) res-=B[i].que(s);
    return res;
}

int main(){
    freopen("710F.in","r",stdin);
    freopen("710F.out","w",stdout);
    for (scanf("%d",&m); m--; ){
        cin>>op>>s;
        if (op==1) ins(s);
        if (op==2) del(s);
        if (op==3) cout<<que(s)<<endl;
    }
    return 0;
}