线段树分治小结

旧博客（算法竞赛）发表于 2020-02-04 原文更新于 2020-03-28

标记永久化

标记永久化是一种线段树上打标记的技巧，用来在某些场合代替 pushup 和 pusdown 操作，但无法处理标记在时间上的先后顺序和标记的叠加，具体可以见线段树标记永久化个人理解 & BZOJ 1513 [POI2006]Tet-Tetris 3D

顺便重写了一下这个题，可以留着做板子了：

int n=1000;
struct seg
{
    int val[MAXN],cov[MAXN];
    void docov(int v,int cnt)
    {
        val[cnt]=max(val[cnt],v);
        cov[cnt]=max(cov[cnt],v);
    }
    void down(int cnt)
    {
        if(cov[cnt])
            docov(cov[cnt],ls),
            docov(cov[cnt],rs),
            cov[cnt]=0;
    }
    bool update(int l,int r,int nl,int nr,int v,int cnt)
    {
        if(l==nl&&r==nr) return docov(v,cnt),0;
        down(cnt),val[cnt]=max(val[cnt],v);
        if(nr<=mid)return update(l,mid,nl,nr,v,ls);
        if(nl> mid)return update(mid+1,r,nl,nr,v,rs);
        return update(l,mid,nl,mid,v,ls),update(mid+1,r,mid+1,nr,v,rs);
    }
    int query(int l,int r,int nl,int nr,int cnt)
    {
        if(l==nl&&r==nr)return val[cnt];down(cnt);
        if(nr<=mid)return query(l,mid,nl,nr,ls);
        if(nl> mid)return query(mid+1,r,nl,nr,rs);
        return max(query(l,mid,nl,mid,ls),query(mid+1,r,mid+1,nr,rs));
    }
}val[MAXN],cov[MAXN];
int query(int l,int r,int nl,int nr,int y1,int y2,int cnt)
{
    int ans=cov[cnt].query(1,n,y1,y2,1);
    if(l==nl&&r==nr)return max(ans,val[cnt].query(1,n,y1,y2,1));
    if(nr<=mid)return max(ans,query(l,mid,nl,nr,y1,y2,ls));
    if(nl> mid)return max(ans,query(mid+1,r,nl,nr,y1,y2,rs));
    return max({ans,
        query(l,mid,nl,mid,y1,y2,ls),
        query(mid+1,r,mid+1,nr,y1,y2,rs)
    });
}
bool update(int l,int r,int nl,int nr,int y1,int y2,int v,int cnt)
{
    val[cnt].update(1,n,y1,y2,v,1);
    if(l==nl&&r==nr) return cov[cnt].update(1,n,y1,y2,v,1),0;
    if(nr<=mid)return update(l,mid,nl,nr,y1,y2,v,ls);
    if(nl> mid)return update(mid+1,r,nl,nr,y1,y2,v,rs);
    return update(l,mid,nl,mid,y1,y2,v,ls),update(mid+1,r,mid+1,nr,y1,y2,v,rs);
}
int work()
{
    int a,b,q;scanf("%d%d%d",&a,&b,&q);
    while(q--)
    {
        int d,s,w,x,y;
        scanf("%d%d%d%d%d",&d,&s,&w,&x,&y);
        int x1=x+1,x2=x+d,y1=y+1,y2=y+s;
        int h=query(1,n,x1,x2,y1,y2,1)+w;
        update(1,n,x1,x2,y1,y2,h,1);
    }
    return printf("%d\n",query(1,n,1,n,1,n,1));
}

线段树分治

线段树常用来维护顺序序列上的区间信息(如区间和，区间最大值等)，而线段树分治则利用线段树来维护时间轴(操作的先后关系)，并利用标记永久化的思想来解决一些需要撤销操作的数据结构问题。

例题1: BZOJ 4184 shallot

本题中需要你维护一个支持删除的线性基，脑补可知线性基的删除很麻烦(or不可做)。

我们把每次操作(包括询问在内)看作是一个时间点，那么每一个数 \(a_{i}\) 都有一个可用的时间区间。类似于线段树打标记的做法，我们将这个区间拆成 \(logn\) 个区间并覆盖在线段树上对应的节点上，具体来讲是线段树的每个节点维护一个 vector 来存这个标记。

然后我们考虑如何处理询问操作，每次询问可以看作是根节点到某个叶子节点的一条路径，我们只要将这条路径上的所有标记丢到一个线性基里做一次查询即可。

具体来讲就是递归处理到某个节点时先复制一份修改前的线性基(这一步O(logn))，然后把当前节点上的标记插入到线性基里，递归处理左右儿子，结束后再复制回来就实现了线性基的撤销操作。

复杂度的话，每个时间区间最多贡献 \(logn\) 个标记，线性基插入复杂度 \(logn\) 总复杂度 \(O(n*logn*logn)\)。

void solve(int l,int r,linearbase s=linearbase(),int cnt=1)
{
    for(auto x:cov[cnt])s.insert(x);
    if(l==r){ans[l]=s.query();return;}
    solve(l,mid,s,ls),solve(mid+1,r,s,rs);
}

完整代码:

struct linearbase
{
    int a[35];
    linearbase(){mst(a,0);}
    void insert(int x)
    {
        fd(i,30,0)if(x&(1<<i))
        {
            if(!a[i]){a[i]=x;break;}
            else x^=a[i];
        }
    }
    int query(int ans=0)
    {
        fd(i,30,0)if((ans^a[i])>ans)ans^=a[i];
        return ans;
    }
    void print()
    {
        fd(i,30,0)cout<<dbgs2(i,a[i])<<endl;
    }
};

int n;
int a[MAXN],ans[MAXN];
vector<int> cov[MAXN*4];
map<int,int> tim,cnt;
void cover(int l,int r,int nl,int nr,int val,int cnt)
{
    if(l==nl&&r==nr){cov[cnt].pb(val);return;}
    if(nr<=mid)cover(l,mid,nl,nr,val,ls);
    else if(nl>mid)cover(mid+1,r,nl,nr,val,rs);
    else cover(l,mid,nl,mid,val,ls),cover(mid+1,r,mid+1,nr,val,rs);
}
void solve(int l,int r,linearbase s=linearbase(),int cnt=1)
{
    for(auto x:cov[cnt])s.insert(x);
    if(l==r){ans[l]=s.query();return;}
    solve(l,mid,s,ls),solve(mid+1,r,s,rs);
}

int work()
{
    scanf("%d",&n);
    fp(i,1,n)
    {
        scanf("%d",&a[i]);
        if(a[i]>0)
        {
            if(cnt[a[i]]==0)tim[a[i]]=i;
            cnt[a[i]]++;
        }
        else 
        {
            cnt[-a[i]]--;
            if(cnt[-a[i]]==0)
                cover(1,n,tim[-a[i]],i-1,-a[i],1);
        }
    }
    for(auto x:cnt)if(x.se!=0)
        cover(1,n,tim[x.fi],n,x.fi,1);
    solve(1,n);
    fp(i,1,n)printf("%d\n",ans[i]);
    return 0;
}

例题2：LOJ121 「离线可过」动态图连通性

类似于上一题，将每条边的存活的时间区间覆盖到线段树上，搞一个并查集，进入某个节点时合并一下当前节点上的标记，递归结束时倒着撤销掉合并操作即可。

int n,m;
int f[MAXN],siz[MAXN];
vector<pr> cov[N*4];
struct query{int t,x,y,ans;}q[N];

int  find(int x){return x==f[x]?x:find(f[x]);}
void merge(int x,int y,vector<pr> &a)
{
    x=find(x),y=find(y);if(x==y)return;
    if(siz[x]>siz[y])swap(x,y);
    f[x]=y,siz[y]+=siz[x],a.pb({x,y});
}
void undo(pr opt)
{
    int x=opt.fi,y=opt.se;
    f[x]=x,siz[y]-=siz[x];
}

#define ls (cnt<<1)
#define rs (cnt<<1|1)
void cover(int l,int r,int nl,int nr,pr e,int cnt)
{
    if(l==nl&&r==nr){cov[cnt].pb(e);return;}
    if(nr<=mid)cover(l,mid,nl,nr,e,ls);
    else if(nl>mid)cover(mid+1,r,nl,nr,e,rs);
    else cover(l,mid,nl,mid,e,ls),cover(mid+1,r,mid+1,nr,e,rs);
}
void solve(int l,int r,int cnt)
{
    vector<pr> seq; for(auto e:cov[cnt])merge(e.fi,e.se,seq);
    if(l==r)q[l].ans=(find(q[l].x)==find(q[l].y));
    if(l!=r)solve(l,mid,ls),solve(mid+1,r,rs);
    reverse(all(seq));for(auto x:seq)undo(x);
}

map<pr,int> tim;
int work()
{
    scanf("%d%d",&n,&m);
    fp(i,1,n)siz[i]=1,f[i]=i;
    fp(i,1,m)
    {
        scanf("%d%d%d",&q[i].t,&q[i].x,&q[i].y);
        if(q[i].x>q[i].y)swap(q[i].x,q[i].y); pr t={q[i].x,q[i].y}; 
        if(q[i].t==0)tim[t]=i;
        if(q[i].t==1)cover(1,m,tim[t],i,t,1),tim.erase(t);
    }
    for(auto p:tim)cover(1,m,p.se,m,p.fi,1);
    solve(1,m,1);
    fp(i,1,m)if(q[i].t==2)puts(q[i].ans?"Y":"N");
    return 0;
}

最大流&&费用流板子整理 Solution for ZZQ's Catforces