题解：P11127 [ROIR 2024] 二叉树的遍历 (Day 2)

· · 题解

[ROIR 2024] 二叉树的遍历 (Day 2) 题解

博客园连接：[ROIR 2024] 二叉树的遍历 (Day 2) 题解 - Add_Catalyst - 博客园 (cnblogs.com)。

知识点

分块。

分析

首先考虑对查询 u 有影响的操作：

  1. 子孙节点：

    • 当 c_u = 0 时，它的左子树需要计入。
    • 当 c_u = 1 时，它的左右子树都需要计入。

  2. 祖先节点：

    设某个祖先为 anc。

    • 当 c_{anc} = -1，它需要计入。
    • 当 c_{anc}=0 且 u 在 anc 的右子树中，它需要计入。

  3. 其他：

    • 与 u 无祖孙关系的，需要把在它前面的计入。

发现对于 u，除了祖先节点的影响，其余都是可以预处理然后 O(1) 解决的，那么我们考虑维护祖先节点的影响。

首先对于数据结构，我们非常清楚的知道不太可能用 polylog 做法，因为下标不连续，一般的 polylog 数据结构都做不到。那么我们会联想到分块、bitset、树分块（实际上这些算法在本题都有相应解法）。我们这里选用传统的分块。

对于修改，在树上可以想到转 DFS 序，因为这样便于区间修改。

考虑分块的修改影响，发现由于操作是赋值操作，且值域极小，所以整块的赋值后都是相等，而且情况只有三种，那么我们可以考虑预处理整块的部分。转为 DFS 序之后，对于每块差分预处理一个 F_{j} 表示整体赋值为 -1 后，对 DFS 序为 j 的点的影响（加多少）；同理 G_j 表示赋值为 0 时；而赋值为 1 时其实无影响，所以可以不处理。这些在一开始用差分解决即可。

再考虑散块的维护，可以从最暴力的重构来想，因为每次修改只有两块受到修改。仿照整块维护对 DFS 为 j 的点的影响，那么只要再加一个 O(1) 修改 O(\sqrt{n}) 查询的序列分块即可解决。

代码

constexpr int N(1e5+10),BN(330);

int n,Q,idx;
int c[N],ls[N],rs[N],dl[N],siz[N],lef[N];

void DFS(int u) {
    dl[u]=++idx,siz[u]=1;
    if(ls[u])lef[ls[u]]=lef[u],DFS(ls[u]),siz[u]+=siz[ls[u]];
    if(rs[u])lef[rs[u]]=lef[u]+siz[ls[u]],DFS(rs[u]),siz[u]+=siz[rs[u]];
}

int Bl,Bn;
int st[BN],en[BN],bel[N];
int F[BN][N],G[BN][N];

void Init_F(int l,int r,int *F) {
    FOR(i,1,n)F[i]=0;
    FOR(u,l,r)++F[dl[u]+1],--F[dl[u]+siz[u]];
    FOR(i,1,n)F[i]+=F[i-1];
}

void Init_G(int l,int r,int *G) {
    FOR(i,1,n)G[i]=0;
    FOR(u,l,r)if(rs[u]) {
        int v(rs[u]);
        ++G[dl[v]],--G[dl[v]+siz[v]];
    }
    FOR(i,1,n)G[i]+=G[i-1];
}

struct DB {
    int sum[BN],cnt[N];

    void Plus(int x,int d) { sum[bel[x]]+=d,cnt[x]+=d; }

    void Plus(int l,int r,int d) { Plus(l,d),Plus(r+1,-d); }

    int Sum(int x) {
        int bx(bel[x]),res(0);
        FOR(i,1,bx-1)res+=sum[i];
        FOR(i,st[bx],x)res+=cnt[i];
        return res;
    }
} db;

void update(int x,int d) {
    if(!~c[x])db.Plus(dl[x]+1,dl[x]+siz[x]-1,d);
    if(!c[x]&&rs[x])db.Plus(dl[rs[x]],dl[rs[x]]+siz[rs[x]]-1,d);
}

bool cov[BN];
int C[BN];

void cover(int l,int r,int _c) {
    int bx(bel[l]);
    if(!cov[bx]) {
        FOR(i,l,r)if(c[i]!=_c)update(i,-1),c[i]=_c,update(i,1);
        return;
    }
    cov[bx]=false;
    FOR(i,st[bx],en[bx])c[i]=(l<=i&&i<=r?_c:C[bx]),update(i,1);
}

void Cover(int l,int r,int _c) {
    int bl(bel[l]),br(bel[r]);
    if(bl==br)return cover(l,r,_c);
    cover(l,en[bl],_c),cover(st[br],r,_c);
    FOR(i,bl+1,br-1) {
        if(!cov[i]) {
            FOR(j,st[i],en[i])update(j,-1);
            cov[i]=true;
        }
        C[i]=_c;
    }
}

int Query(int x) {
    int sum(1+db.Sum(dl[x])+lef[x]),_c(cov[bel[x]]?C[bel[x]]:c[x]);
    if(_c>0)sum+=siz[x]-1;
    if(!_c&&ls[x])sum+=siz[ls[x]];
    FOR(i,1,Bn)if(cov[i]) {
        if(!~C[i])sum+=F[i][dl[x]];
        if(!C[i])sum+=G[i][dl[x]];
    }
    return sum;
}

signed main() {
    /*DE("Input");*/
    I(n,Q);
    FOR(i,1,n)c[i]=-1;
    FOR(i,1,n)I(ls[i],rs[i]);
    /*DE("Build");*/
    DFS(1);
    Bl=ceil(sqrt(n)),Bn=(n-1)/Bl+1;
    FOR(i,1,Bn) {
        st[i]=en[i-1]+1,en[i]=min(en[i-1]+Bl,n);
        FOR(j,st[i],en[i])bel[j]=i;
        Init_F(st[i],en[i],F[i]),Init_G(st[i],en[i],G[i]);
        cov[i]=true,C[i]=-1;
    }
    /*DE("Query");*/
    while(Q--) {
        int t,l,r,x;
        I(t);
        if(t==1)I(l,r,x),Cover(l,r,x);
        else I(x),O(Query(x),'\n');
    }
    return 0;
}