专栏文章

题解：P14521 【MX-S11-T2】加减乘除

LLucyna_Kushinada
P14521题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min6zmew
此快照首次捕获于
2025/12/01 21:35
3 个月前
此快照最后确认于
2025/12/01 21:35
3 个月前
查看原文

Basic Observation

opiop_i 是干扰项，不妨在 opi=−op_i=- 时，令 ai←−aia_i\leftarrow -a_i。
走到节点 uu 时，从根到 uu 路径上所有的点都会走过，记 du=∑x∈path1→uaxd_u=\sum_{x\in path_{1\to u}} a_x，类似深度。
如果询问了一个 xx，在 uu 节点时手上的数就是 du+xd_u+x。
对于边 (u,v,l,r)(u,v,l,r)，其中 vv 是 uu 的儿子，要走到 vv 有限制 du+x∈[l,r]d_u+x\in [l,r]，进而得出 x∈[l−di,r−du]x\in [l-d_i,r-d_u]，为什么想到这么做，因为后者是固定的值，前者是随询问变化的。

Solution I

首先是重工业做法，将本题加强后也能做。
如果将 xx 看作时刻，那么可以将原问题转化为，给定一颗树，树边 (u,v,lx,rx)(u,v,l_x,r_x) 表示这条边仅在时刻 ∈[lx,rx]\in[l_x,r_x] 时出现，qq 次询问，查询某一时刻根节点所在的连通块大小，鉴定为动态图连通性问题，不难想到线段树分治。
维护连通块大小可以用并查集，用按秩合并并查集结合线段树分治的结构，可以实现连通性的撤销，时间复杂度 O(nlog⁡2n+qlog⁡n)O(n\log^2 n+q\log n)，能过。
CPP
#include<bits/stdc++.h>
using namespace std;

#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(r);i>=(l);--i)
#define pr pair<int,int>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define bg(x) (x).begin()
#define ed(x) (x).end()
#define sz(x) (int)(x).size()

#define N 500011
#define V 2000010
#define ll long long
// #define int long long

int n,m,fa[N],u[N],v[N];
ll a[N],d[N];

struct edge{
    int t;
    ll l,r;
};

struct node{
    int u,v;
    ll l,r;
};

vector<edge>e[N];
vector<ll>ve;
vector<node>ex;
vector<pair<ll,int>>g;

inline void dfs(int k){
    d[k]=d[fa[k]]+a[k];

    for(edge x:e[k]){
        ll l=x.l-d[k],r=x.r-d[k];
        if(l<=r){
            ve.pb(l);
            ve.pb(r);
            ex.pb({k,x.t,l,r});
        }

        dfs(x.t);
    }
}

int lim=0,ans[V];

namespace sol{
    #define mid ((l+r)>>1)

    vector<int>e[V<<2],que[V];
    
    inline void ins(int k,int l,int r,int L,int R,int id){
        if(L<=l&&R>=r){
            e[k].pb(id);
            return;
        }

        if(L<=mid){
            ins(k*2,l,mid,L,R,id);
        }
        if(R>mid){
            ins(k*2+1,mid+1,r,L,R,id);
        }
    }

    struct dsu{
        int fa[N],siz[N],tp;
        pr st[N];

        inline void init(){
            rep(i,1,n){
                fa[i]=i;
                siz[i]=1;
            }
        }

        inline int ask(int x){
            while(x!=fa[x]){
                x=fa[x];
            }
            return x;
        }

        inline bool mg(int x,int y){
            x=ask(x),y=ask(y);

            if(x==y){
                return 0;
            }

            if(siz[x]>siz[y]){
                swap(x,y);
            }

            fa[x]=y;
            siz[y]+=siz[x];
            st[++tp]={x,y};

            return 1;
        }

        inline void recall(int pos){
            while(tp>pos){
                auto [x,y]=st[tp];
                siz[y]-=siz[x];
                fa[x]=x;
                tp--;
            }
        }
    }d;

    inline void sol(int k,int l,int r){
        int now=d.tp;

        for(int i:e[k]){
            d.mg(ex[i].u,ex[i].v);
        }

        if(l==r){
            for(int i:que[l]){
                ans[i]=d.siz[d.ask(1)];
            }

            d.recall(now);
            
            return;
        }

        sol(k*2,l,mid);
        sol(k*2+1,mid+1,r);

        d.recall(now);
    }

    #undef mid
}

signed main(){
    // freopen("calc.in","r",stdin);
    // freopen("calc.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>n>>m;

    rep(i,2,n){
        ll l,r;
        cin>>fa[i]>>l>>r;
        e[fa[i]].pb({i,l,r});
    }

    rep(i,1,n){
        char o;
        cin>>o>>a[i];
        if(o=='-'){
            a[i]=-a[i];
        }
    }

    dfs(1);

    rep(i,1,m){
        ll x;
        cin>>x;
        ve.pb(x);
        g.pb({x,i});
    }

    sort(all(ve));
    ve.erase(unique(all(ve)),ed(ve));

    lim=sz(ve);

    for(auto [x,i]:g){
        x=lower_bound(all(ve),x)-bg(ve)+1;
        sol::que[x].pb(i);
    }

    g.clear();

    rep(i,0,sz(ex)-1){
        auto [u,v,l,r]=ex[i];
        l=lower_bound(all(ve),l)-bg(ve)+1;
        r=lower_bound(all(ve),r)-bg(ve)+1;
        sol::ins(1,1,lim,l,r,i);
    }

    ve.clear();

    sol::d.init();
    sol::sol(1,1,lim);

    rep(i,1,m){
        cout<<ans[i]<<'\n';
    }

    return 0;
}

Solution II

在树上维护动态图连通性还是太魔怔了，现在是正常做法。
注意到询问的是根节点，只需要关于某个节点与根的连通性。
注意到树上两个节点之间的路径只有一条，那么走到 uu 就需要，询问的 xx 满足从根结点出发到 uu 路径上所有节点关于 xx 大小的限制，限制是可以预处理的。
注意到限制是区间，限制之间的合并就是区间求交，将根到 uu 路径上的所有限制求交作为 uu 的新限制，那么 xx 满足这个限制意味着根一定能到 uu，而不仅仅只是 uu 与 faufa_u 之间的边在当前 xx 下存在。
那么可以对每个节点 ii 求出 [pi,qi][p_i,q_i] 表示 xx 的取值范围，使得 ii 能与根连通。
离散化后做用差分实现区间加即可，时间复杂度 O((n+q)log⁡n)O((n+q)\log n)，瓶颈在于排序。
CPP
#include<bits/stdc++.h>
using namespace std;

#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(r);i>=(l);--i)
#define pr pair<int,int>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define bg(x) (x).begin()
#define ed(x) (x).end()
#define sz(x) (int)(x).size()

#define N 500011
#define V 2000010
#define int __int128

int n,m,fa[N],u[N],v[N];
int a[N],d[N],ad[V];
pr b[N];

inline int rd(){
    int x=0,f=1;
    char c=0;

    while(!isdigit(c)){
        c=getchar_unlocked();
        if(c=='-'){
            f=-1;
        }
    }

    while(isdigit(c)){
        x=10*x+c-'0';
        c=getchar_unlocked();
    }

    return x*f;
}

inline void out(int x){
    if(x<0){
        putchar_unlocked('-');
        out(-x);
        return;
    }

    if(x>9){
        out(x/10);
    }
    putchar_unlocked(x%10+'0');
}

struct edge{
    int t;
    int l,r;
};

vector<edge>e[N];
vector<int>ve,que;
vector<pr>g;
bitset<N>f;

inline void dfs(int k,int L,int R){
    d[k]=d[fa[k]]+a[k];

    for(edge x:e[k]){
        int l=max(x.l-d[k],L),r=min(x.r-d[k],R);

        if(l<=r){
            f[x.t]=1;
            b[x.t].fi=l;
            b[x.t].se=r;
            ve.pb(l);ve.pb(r);

            dfs(x.t,l,r);
        }
    }
}

int lim=0,ans[V];

signed main(){
    // freopen("calc.in","r",stdin);
    // freopen("calc.out","w",stdout);
    // ios::sync_with_stdio(0);
    // cin.tie(0);cout.tie(0);

    n=rd(),m=rd();

    rep(i,2,n){
        int l,r;

        fa[i]=rd();
        l=rd();r=rd();

        e[fa[i]].pb({i,l,r});
    }

    rep(i,1,n){
        char o;
        cin>>o;

        a[i]=rd();
        if(o=='-'){
            a[i]=-a[i];
        }
    }

    dfs(1,-1e30,1e30);

    rep(i,1,m){
        int x=rd();

        ve.pb(x);
        que.pb(x);
    }

    sort(all(ve));
    ve.erase(unique(all(ve)),ed(ve));

    lim=sz(ve);

    rep(i,1,n){
        if(f[i]){
            auto [l,r]=b[i];
            l=lower_bound(all(ve),l)-bg(ve)+1;
            r=lower_bound(all(ve),r)-bg(ve)+1;
            ad[l]++;
            ad[r+1]--;
        }
    }

    rep(i,1,lim){
        ad[i]+=ad[i-1];
    }

    for(int x:que){
        x=lower_bound(all(ve),x)-bg(ve)+1;
        out(ad[x]+1);
        putchar_unlocked('\n');
    }

    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...