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

· · 题解

没有乘除法？纯粹大糖题。

Solution P14521

下文记点权为到这个点的加减值，其中减法以加负数代替；准许区间为题中的 [l,r]。

由于点权只有加减，对于从点 1 出发的值 val，其可以通过第 i 条边的 val 一定在一个区间内。

可以这么理解：从第 i 条边向上走，准许通过的最小值和最大值都会根据点权变化。

具体来说，关系是：设 u 为深度更小的点，则 l_i\leftarrow l_i-sum_u，其中 sum_u 为 1 到 u 的路径上的点权和。r_i\leftarrow r_i-sum_u，与 l_i 同理。

能到达一个点的充要条件是初始权值属于从点 1 到该点上所有准许区间之交。

但是你直接暴力做是 \operatorname{O}(nq) 的，过不了。

考虑先把从点 1 到所有点的路径上的准许区间之交求出来。然后把询问离线下来，按照 x 排个序。

那么对于点 i，设其从点 1 到该点上所有准许区间之交为 [L,R]，那么它只会对 x\in[L,R] 的询问产生贡献。

显然 x\in[L,R] 的询问是一段区间，这个直接差分做区间加法就好了。至于如何找到这段区间呢？使用 lower_bound 即可。

复杂度 \operatorname{O}(n \log n)。

::::success[Code]

#include<bits/stdc++.h>
#define ll long long
#define i128 __int128
#define fi first
#define se second
#define fastio ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define ls (now<<1)
#define rs ((now<<1)|1)
using namespace std;
const int N=1000005;
const int intinf=0x3f3f3f3f;
const ll llinf=0x3f3f3f3f3f3f3f3f;
int n;
struct node{
    int u,v;
    i128 l,r;int nxt;
}e[N<<2];
int head[N],cnt;
ll val[N];
void add(int u,int v,ll l,ll r){
    e[++cnt].u=u;
    e[cnt].v=v;
    e[cnt].l=l;
    e[cnt].r=r;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
ll pl[N],pr[N];
void dfs(int now,int fa,i128 sum,i128 l,i128 r){
    sum+=val[now];
    pl[now]=l;pr[now]=r;
    for(int i=head[now],v;i;i=e[i].nxt){
        v=e[i].v;
        if(v==fa)continue;
        e[i].l-=sum;e[i].r-=sum;
        dfs(v,now,sum,max(l,e[i].l),min(r,e[i].r));
    }
}
struct query{
    int id;ll x;
    friend bool operator <(query _,query __){
        return _.x<__.x;
    }
}q[N];
int Q;
ll t[N];
int cha[N],ans[N];
void print(i128 x){
//  cout<<"check:"<<(int)x<<'\n';
    if(x<0){
        cout<<"-";
        print(-x);
        return;
    }
    if(x==0)return;
    print(x/10);
    cout<<(int)(x%10);
}
signed main(){
    fastio;
    cin>>n;
    cin>>Q;
    ll l,r;
    for(int i=2,u;i<=n;i++){
        cin>>u>>l>>r;
        add(i,u,l,r);
        add(u,i,l,r);
    }
    char opt;
    for(int i=1;i<=n;i++){
        cin>>opt>>val[i];
        if(opt=='-')val[i]=-val[i];
    }
    dfs(1,0,0,-llinf,llinf);
    for(int i=1;i<=Q;i++){
        cin>>q[i].x;
        q[i].id=i;
    }
    sort(q+1,q+Q+1);
    for(int i=1;i<=Q;i++){
        t[i]=q[i].x;
    }
    for(int i=1;i<=n;i++){
        if(pl[i]>pr[i])continue;
        int l=lower_bound(t+1,t+Q+1,pl[i])-t,r=upper_bound(t+1,t+Q+1,pr[i])-t;
        cha[l]++;cha[r]--;
    }
    int sum=0;
    for(int i=1;i<=Q;i++){
        sum+=cha[i];
        ans[q[i].id]=sum;
    }
    for(int i=1;i<=Q;i++){
        cout<<ans[i]<<'\n';
    }
    return 0;
}

::::