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

· · 题解

随机撒 B 个点，每次修改完毕之后立刻更新这 B 个点的答案。

查询直接暴力往上跳，如果遇到这 B 个点之一就直接加上，然后停止往上跳。

假装 n,q 同阶，则取 B=\sqrt n 得到最优复杂度 \Theta(n \sqrt n)。

实测窝的代码取 B=100\sim 200 都较优。

UPD : 说一下细节。

用珂朵莉树维护连续段。用值域分块支持 \Theta(B) 区间覆盖，\Theta(1) 单点查询。

更新答案的时候很像是拿出来关键点到根路径上所有编号在 l \sim r 之间的点，然后更新一些信息。所以提前跑一个前缀和。

然后就差不多了。代码里都有写，看代码吧。

#include <bits/stdc++.h>
#define FAST ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define TIAO cout << fixed << setprecision(15)
using namespace std;
/*
When we've done it all, Besides,
we've ever given all each other heart and faith
All the morning we will see
As ever, be my love, you'll ever be the one forevermore
oh,and this code is by qqqaaazzz.
*/
int n,q;
int l[100010],r[100010];
int L[100010],R[100010];//dfn区间
//注意：l,r 是左右儿子
int idx;
int x[100010];
int sz[100010];
int FA[100010];

void dfs(int d,int fa){
    FA[d]=fa;

    L[d]=++idx;
    sz[d]=1;
    if(l[d])dfs(l[d],d),sz[d]+=sz[l[d]];
    if(r[d])dfs(r[d],d),sz[d]+=sz[r[d]];
    R[d]=idx;
}
int w[100010][3];
int sp[100010];
int ans[100010];//特殊的
const int B = 100;
int g[100010];
int sum[340][3][100010];//畸形前缀和！！ 

struct Node{
    int l,r,v;
    bool operator < (const Node &x) const{
        return r<x.l;
    }
};
struct DS{
    //O(B)区间推平，O(1) 查询
    pair<int,int>my[100010];
    pair<int,int>G[600];
    int tmp;

    void cover(int l,int r,int col){
        ++tmp;
        if(l/B==r/B){
            for(int i=l;i<=r;i++)my[i]={tmp,col};
        }
        else{
            while(l/B==(l-1)/B)my[l]={tmp,col},++l;
            while(r/B==(r+1)/B)my[r]={tmp,col},--r;
            for(int i=l/B;i<=r/B;i++)G[i]={tmp,col};
        }
    }
    int cc(int x){return max(my[x],G[x/B]).second;}
}ds1;

void origin(int l,int r,int a,int b){
    for(int i=1;i<=min(n,B);i++){
        int val=g[i];
        int bonus=0;
        ans[g[i]]+=(sum[i][b][r]-sum[i][b][l-1])-(sum[i][a][r]-sum[i][a][l-1]);
    }
}
mt19937 rd(12357);
int K[3][100010];

void sums(int d){
    K[0][FA[d]]+=w[d][0];
    K[1][FA[d]]+=w[d][1];
    K[2][FA[d]]+=w[d][2];

    if(l[d])sums(l[d]);
    if(r[d])sums(r[d]);
    //来了
    if(sp[d]){
        for(int i=0;i<3;i++)for(int j=1;j<=n;j++)sum[sp[d]][i][j]=K[i][j]+sum[sp[d]][i][j-1];
    } 

    K[0][FA[d]]-=w[d][0];
    K[1][FA[d]]-=w[d][1];
    K[2][FA[d]]-=w[d][2];
}
int prv[500010];
void init(int d,int fa){
    prv[d]=prv[fa]+w[d][x[fa]];
    if(l[d])init(l[d],d);
    if(r[d])init(r[d],d);
}

signed main()
{
    FAST;
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>l[i]>>r[i];
    dfs(1,0);
    set<Node>all;
    all.insert({1,n,0});
    for(int i=1;i<=n;i++)x[i]=0;
    for(int i=2;i<=n;i++){
        if(l[FA[i]]==i){
            w[i][0]=1;
            w[i][1]=0;
            w[i][2]=0;
        }
        else{
            w[i][0]=1+sz[l[FA[i]]];
            w[i][1]=1+sz[l[FA[i]]];
            w[i][2]=sz[l[FA[i]]];
        }
    }
    init(1,0);
    for(int i=1;i<=n;i++)g[i]=i;
    for(int i=1;i<=n;i++)swap(g[i],g[rd()%n+1]);
    for(int i=1;i<=min(n,B);i++){
        sp[g[i]]=i;
        int val=g[i];
        ans[g[i]]=prv[g[i]];
    }
    sums(1);

    while(q--){
        int op;
        cin>>op;
        if(op==1){
            int l,r,k;
            cin>>l>>r>>k;++k;
            while(all.find({l,r,k})!=all.end()){
                Node E=*(all.find({l,r,k}));
                all.erase(E);
                if(E.l<l)all.insert({E.l,l-1,E.v});
                if(E.r>r)all.insert({r+1,E.r,E.v});
                origin(max(E.l,l),min(E.r,r),E.v,k); 
            }
            all.insert({l,r,k});
            ds1.cover(l,r,k);
        }
        else{
            int val;
            cin>>val;
            const int E=ds1.cc(val);
            int S=(E==0?0:(E==1?sz[l[val]]:sz[l[val]]+sz[r[val]]))+1;
            while(FA[val]){
                if(sp[val]){
                    S+=ans[val];
                    break;
                }
                S+=w[val][ds1.cc(FA[val])];
                val=FA[val];
            }
            cout<<S<<"\n";
        }
    }
    return 0;
}
//(<<) > (> < <= >=) > (== !=) > & > ^ > | > && > ||