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

· · 题解

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

挑战你谷最劣解（最慢的一次 27.65s

本人用线段树维护，主观难度上位绿（下位蓝）。

简要复述下题意：给定一颗有根树，q 次询问每次询问给定一个值 x，从根结点出发，每经过一个点需要加上这个点给定的值（也就是题目中的“将手中的数 x 变为 x \mathbin{\mathrm{op}_u} a_u”），到达一个点必须满足你现在的值处于给定的区间范围内，求每个询问的 x 能到达树上的哪些点。

我们很容易想到一个暴力：对于每一次询问都遍历一遍整棵树，直接模拟即可得出可以到达哪些点。时间复杂度 O(nq)，可以获得 15 分。

其实我们不太需要关注一些特殊性质，直接来考虑我们的暴力有什么地方有待改善。我们发现每次询问都遍历整棵树太繁琐了，而且每次询问都是独立的，各自间不会互相影响，因此可以考虑离线处理，扫一遍树就得出答案。

于是我们可以考虑怎样扫一遍树统计出所有情况。不难看出，题中改变权值的操作只有加减，因此可以考虑直接记录一个偏移量，这样我们就可以直接得出可以到达每个点的原本询问的数 x 的区间。很明显，在这个区间的所有数都可以到达这个点，也就是区间加，可以用数据结构维护（当然其他琳琅满目的办法也行）。最后每个 x 单点查询即可。这样就能通过此题了。

总结一下我们的思路：将所有询问离线处理，对整棵树进行遍历，遍历到一个结点便处理出在询问中可以到达这个点的区间，进行区间加。时间复杂度 O(n \log n+n \log q)，常数略大，但过掉这题是没问题的。

一些细节问题详见代码。

Code:

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
ll n,q,l[5000005],r[5000005],cg[5000005],b[5000005];
int tree[10000005],tag[10000005];
vector<ll> vt[1000005];
struct node
{
    ll cnt,id;
}a[5000005];
bool cmp(node u,node v)
{
    return u.cnt<v.cnt;
}
void pushdown(ll u,ll lo,ll ro)
{
    ll mid=(lo+ro)>>1;
    tree[(u<<1)]+=(mid-lo+1)*tag[u];
    tree[(u<<1)|1]+=(ro-mid)*tag[u];
    tag[(u<<1)]+=tag[u];
    tag[(u<<1)|1]+=tag[u];
    tag[u]=0;
    return ;
}
void modify(ll u,ll lo,ll ro,ll ql,ll qr)//因为每次区间加都是加1，故省略了加的数量
{
    if(ql<=lo&&ro<=qr)
    {
        tree[u]+=ro-lo+1;
        tag[u]++;
        return ;
    }
    pushdown(u,lo,ro);
    ll mid=(lo+ro)>>1;
    if(ql<=mid) modify((u<<1),lo,mid,ql,qr);
    if(qr>mid) modify((u<<1)|1,mid+1,ro,ql,qr); 
}
ll getl(ll x)//得到最小的在询问序列中大于等于这个数的位置，左端点
{
    if(x>a[q].cnt)//判越界
    {
        return q+1;
    }
    ll lo=1,ro=q;
    while(lo<ro)
    {
        ll mid=(lo+ro)>>1;
        if(a[mid].cnt>=x) ro=mid;
        else lo=mid+1;
    }
    return lo;
}
ll getr(ll x)//得到最大的在询问序列中小于等于这个数的位置，右端点
{
    if(x<a[1].cnt)//判越界
    {
        return 0;
    }
    ll lo=1,ro=q;
    while(lo<ro)
    {
        ll mid=(lo+ro+1)>>1;
        if(a[mid].cnt<=x) lo=mid;
        else ro=mid-1;
    }
    return lo;
}
void dfs(ll u,ll fa,ll lo,ll ro,ll pyl)//pyl是偏移量
{
    for(ll i=0;i<vt[u].size();i++)
    {
        ll v=vt[u][i];
        if(v==fa) continue;
        ll newl=max(lo,l[v]-pyl),newr=min(ro,r[v]-pyl);
        //一定要取max min，到达这个点前提就是要在前面所有点限定的区间内！
        //记得要减偏移量
        ll lpos=getl(newl);
        ll rpos=getr(newr);
        //获得区间加的左右端点
        if(lpos<=rpos) 
        {
            modify(1,1,q,lpos,rpos);
        }
        dfs(v,u,newl,newr,pyl+cg[v]);
    }
}
ll query(ll u,ll lo,ll ro,ll x)
{
    if(lo==ro)
    {
        return tree[u];
    }
    pushdown(u,lo,ro);
    ll mid=(lo+ro)>>1;
    if(x<=mid) return query((u<<1),lo,mid,x);
    return query((u<<1)|1,mid+1,ro,x);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    for(ll i=2;i<=n;i++)
    {
        ll x;
        cin>>x>>l[i]>>r[i];
        vt[x].push_back(i);
        vt[i].push_back(x);
        //建图
    }
    for(ll i=1;i<=n;i++) 
    {
        char c;
        ll x;
        cin>>c>>x;
        if(c=='+') cg[i]=x;
        else cg[i]=-x;
        //处理出操作
    }
    for(ll i=1;i<=q;i++)
    {
        cin>>a[i].cnt;
        a[i].id=i;
    }
    sort(a+1,a+q+1,cmp);//将询问离线下来排序形成单调递增的序列
    modify(1,1,q,1,q);//根结点每个数都能到，先加上
    dfs(1,0,-3e18-10,3e18+10,cg[1]);//这里最大值尽量取大点
    for(ll i=1;i<=q;i++) 
    {
        b[a[i].id]=query(1,1,q,i);
    }
    for(ll i=1;i<=q;i++) cout<<b[i]<<endl;
}

Tip: 考试的时候写了一个多小时代码，结果第三个大样例死活不出来，以为挂了结果过了，大概是因为第三个大样例是条链导致递归层数过多爆栈了。