ZR 集训 Day 6 – 可持久化、虚树

ooliver 发布于 15 小时前 70 次阅读 OI

AI 摘要

标记永久化如何让可持久化线段树轻松驾驭区间修改？树剖+可持久化竟让情报传递在线做法比离线还猛？KMP 匹配条件改成排名，可持久化 Trie 配合堆优雅取出前 k 大…… 这些硬核技巧，都在 ZR 集训 Day6 一一拆解。

ZR 集训 Day 6 - 可持久化、虚树

SP11470 TTM - To the moon

可持久化线段树题。

会发现对于区间修改我们是需要懒标记的，但是对一个版本打了懒标记后下传可能会影响其他版本。这里用到了标记永久化的思想，打上懒标记后不下传，而是在统计答案时递归作为参数下传。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define lc(p) tr[p].ls
#define rc(p) tr[p].rs

const int N=1e5+5;
int n,m,idx,t,now;
int rt[N],a[N];
struct tree{
    int l,r,ls,rs,sum,lz;
    void tag(int k){
        sum+=(r-l+1)*k;
        lz+=k;
    }
}tr[N*32];

void pushup(int p){
    tr[p].sum=tr[lc(p)].sum+tr[rc(p)].sum;
}

void build(int &p,int l,int r){
    p=++idx,tr[p].l=l,tr[p].r=r;
    if(l==r){
        tr[p].sum=a[l];
        return;
    }
    int mid=l+r>>1;
    build(lc(p),l,mid);
    build(rc(p),mid+1,r);
    pushup(p);
}

void add(int f,int &p,int x,int y,int k){
    p=++idx,tr[p]=tr[f];
    if(tr[p].l>=x&&tr[p].r<=y){
        tr[p].tag(k);
        return;
    }
    tr[p].sum+=(min(y,tr[p].r)-max(x,tr[p].l)+1)*k;
    int mid=tr[p].l+tr[p].r>>1;
    if(x<=mid) add(lc(f),lc(p),x,y,k);
    if(y>mid) add(rc(f),rc(p),x,y,k);
}

int qry(int p,int x,int y,int tag){
    if(tr[p].l>=x&&tr[p].r<=y) return tr[p].sum+tag*(tr[p].r-tr[p].l+1);
    int mid=tr[p].l+tr[p].r>>1,res=0;
    if(x<=mid) res+=qry(lc(p),x,y,tag+tr[p].lz);
    if(y>mid) res+=qry(rc(p),x,y,tag+tr[p].lz);
    return res;
}

signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(rt[0],1,n);
    while(m--){
        char op;
        int l,r,x;
        cin>>op;
        if(op=='C'){
            cin>>l>>r>>x;
            p[++now]=++t;
            add(rt[t-1],rt[t],l,r,x);
        }
        if(op=='Q'){
            cin>>l>>r;
            cout<<qry(rt[t],l,r,0)<<"\n";
        }
        if(op=='H'){
            cin>>l>>r>>x;
            cout<<qry(rt[x],l,r,0)<<"\n";
        }
        if(op=='B'){
            cin>>t;
        }
    }
    return 0;
}

P4216 [SCOI2015] 情报传递

这道题大部分人应该都是写的对树上每颗节点为版本建主席树的离线 $O(n\log n)$ 做法，但是个人认为树剖+以时间为历史版本建主席树似乎更好想也更好写一点，并且这种方法是在线的，虽然复杂度是 $O(n\log ^2 n)$ 的，但是实测比大部分 $O(n\log n)$ 做法还要快。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define fi first
#define sc second
#define lc(p) tr[p].ls
#define rc(p) tr[p].rs

const int N=2e5+5;
int n,q,t0,idx,now;
int rt[N],a[N],tag[N],son[N],dfn[N],siz[N],top[N],dep[N],fa[N];
vector<int> t[N];
struct tree{
    int ls,rs,sum;
}tr[N*32];

void dfs1(int u,int f){
    siz[u]=1,dep[u]=dep[f]+1;
    for(int v:t[u]){
        dfs1(v,u);
        if(siz[v]>siz[son[u]]) son[u]=v;
        siz[u]+=siz[v];
    }
}

void dfs2(int u,int topf){
    top[u]=topf,dfn[u]=++idx;
    if(son[u]) dfs2(son[u],topf);
    for(int v:t[u]){
        if(v==son[u]) continue;
        dfs2(v,v);
    }
}

void add(int f,int &p,int l,int r,int x){
    p=++idx,tr[p]=tr[f],tr[p].sum++;
    if(l==x&&r==x) return;
    int mid=(l+r)>>1;
    if(x<=mid) add(lc(f),lc(p),l,mid,x);
    else add(rc(f),rc(p),mid+1,r,x);
}

int qry(int p,int x,int y,int l,int r){
    if(l>=x&&r<=y) return tr[p].sum;
    int mid=(l+r)>>1,res=0;
    if(x<=mid) res+=qry(lc(p),x,y,l,mid);
    if(y>mid) res+=qry(rc(p),x,y,mid+1,r);
    return res;
}

pii path(int x,int y,int t){
    int sum=0,res=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        res+=qry(rt[t],dfn[top[x]],dfn[x],1,n);
        sum+=dfn[x]-dfn[top[x]]+1;
        x=fa[top[x]];
    }
    if(dfn[x]>dfn[y]) swap(x,y);
    res+=qry(rt[t],dfn[x],dfn[y],1,n);
    sum+=dfn[y]-dfn[x]+1;
    return {sum,res};
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>fa[i];
        if(fa[i]) t[fa[i]].push_back(i);
        else t0=i;
    }
    dfs1(t0,0);
    dfs2(t0,t0);
    idx=0;
    cin>>q;
    for(int i=1,op,x,y,z;i<=q;i++){
        cin>>op;
        if(op==1){
            cin>>x>>y>>z;
            pii ans=path(x,y,max(i-z-1,0));
            cout<<ans.fi<<" "<<ans.sc<<"\n";
            rt[i]=rt[i-1];
        }
        else{
            cin>>x;
            if(!tag[x]) add(rt[i-1],rt[i],1,n,dfn[x]),tag[x]=1;
            else rt[i]=rt[i-1];
        }
    }
    return 0;
}

P10634 BZOJ2372 music

不难想到 KMP，只是把配对的相等条件换为了排名相等，树状数组维护即可。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

#define lowbit(x) x&-x
const int N=5e5+5;
int n,m,s,idx;
int a[N],b[N],nxt[N],ans[N];

struct BIT{
    int t[N];
    void add(int x,int k){
        for(int i=x;i<N;i+=lowbit(i)) t[i]+=k;
    }
    int get(int x){
        if(x==0) return 0;
        int res=0;
        for(int i=x;i>0;i-=lowbit(i)) res+=t[i];
        return res;
    }
    void clear(){
        memset(t,0,sizeof t);
    }
}A,B;

int main(){
    cin>>n>>m>>s;
    for(int i=0;i<n;i++) cin>>b[i];
    for(int i=0;i<m;i++) cin>>a[i];
    int i=1,j=0;
    while(i<m){
        if(A.get(a[j]-1)==B.get(a[i]-1)&&A.get(a[j])==B.get(a[i])){
            B.add(a[i],1),A.add(a[j],1);
            j++,nxt[i++]=j;
        }
        else{
            if(j==0){
                nxt[i++]=0;
                continue;
            }
            int len=j-nxt[j-1];
            for(int k=0;k<len;k++){
                A.add(a[j-1-k],-1);
                B.add(a[i-j+k],-1);
            }
            j=nxt[j-1];
        }
    }
    A.clear(),B.clear();
    i=0,j=0;
    while(i<n){
        if(A.get(a[j]-1)==B.get(b[i]-1)&&A.get(a[j])==B.get(b[i])){
            B.add(b[i],1),A.add(a[j],1);
            i++,j++;
        }
        else{
            if(j==0){
                i++;
                continue;
            }
            int len=j-nxt[j-1];
            for(int k=0;k<len;k++){
                A.add(a[j-1-k],-1);
                B.add(b[i-j+k],-1);
            }
            j=nxt[j-1];
        }
        if(j==m){
            int len=m-nxt[m-1];
            for(int k=0;k<len;k++){
                A.add(a[m-1-k],-1);
                B.add(b[i-m+k],-1);
            }
            ans[++idx]=i-j+1;
            j=nxt[j-1];
        }
    }
    cout<<idx<<"\n";
    for(int i=1;i<=idx;i++) cout<<ans[i]<<"\n";
    return 0;
}

P5283 [十二省联考 2019] 异或粽子

可持久化 01-Trie（话说 01-Trie 和权值线段树没什么区别）。

看到区间异或考虑先求出异或前缀和，就变成了两点问题。

对每个 $i$ 求出最与其异或和大的 $j(j<i)$，放在优先队列里。之后枚举 $k$ 次，每次取出一个最大的二元对，并将那个 $i$ 的次大贡献加入优先队列。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=5e5+5;
int n,k,idx;
int a[N],b[N],rt[N],ch[N*40][2],sz[N*40];
priority_queue<pair<int,int>> q;

int newu(int u){
    ++idx,sz[idx]=sz[u],ch[idx][0]=ch[u][0],ch[idx][1]=ch[u][1];
    return idx;
}

int insert(int u,int x,int d=31){
    if(d==-1){
        int u2=newu(u);
        sz[u2]++;
        return u2;
    }
    int u2=newu(u);
    ch[u2][x>>d&1]=insert(ch[u2][x>>d&1],x,d-1);
    sz[u2]++;
    return u2;
}

int query(int u,int x,int rk,int d=31){
    if(d==-1) return 0;
    int xd=x>>d&1;
    if(rk<=sz[ch[u][xd]]) return query(ch[u][xd],x,rk,d-1)^(xd<<d);
    else return query(ch[u][xd^1],x,rk-sz[ch[u][xd]],d-1)^((xd^1)<<d);
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>k;
    rt[0]=insert(rt[0],0);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]^=a[i-1];
        rt[i]=insert(rt[i-1],a[i]);
    }
    for(int i=1;i<=n;i++){
        int x=a[i]^query(rt[i-1],a[i],sz[rt[i-1]]);
        q.push({x,i});
        b[i]=sz[rt[i-1]];
    }
    int ans=0;
    while(k--){
        auto u=q.top();
        q.pop();
        ans+=u.first;
        int id=u.second;
        b[id]--;
        if(b[id]){
            int x=a[id]^query(rt[id-1],a[id],b[id]);
            q.push({x,id});
        }
    }
    cout<<ans<<"\n";
    return 0;
}

P2839 [国家集训队] middle