【HDU 6973】Bookshop 树剖+平衡树

【引言】

平衡树的题做得比较少，难得补一次神题，记录一下供以后学习。

【题意】

给出一棵 $n$ 个结点的树，每个结点有一个价值为 $p_i$ 的商品。

有 $m$ 次询问，每次问如果一个人带着 $w$ 块钱，从 $x$ 结点出发到达 $y$ 结点结束，在路上遇到能买的东西就买，不能买就继续往前走，等他走完这段路之后，还剩多少钱？（询问之间相互独立。）

数据范围： $n,m\le 10^5$ ， $p_i,w\le 10^9$

【分析】

容易想到树剖把一个询问的问题分段。

假设可以把 $x\to y$ 分成 $x\to z,z_{next}\to y$ 这连续的两段，那么钱的剩余值 $remain(x,y,w) =remain(z_{next},y,remain(x,z,w))$

也就是说分段之后，只要能按顺序解决每一段的问题，就能解决整个询问的问题。

那么树剖就可以把一个询问分成 $O(\log n)$ 段，我们还可以让重链上的 $dfs$ 序连续。

对每个询问，一定都是先从 $x$ 走若干逆 $dfs$ 序的连续段，然后到达 $LCA$ ，再从 $LCA$ 走若干顺 $dfs$ 序的连续段到达 $y$ 。

于是，我们把每个询问剖出来的每个连续段分为正逆两类。

然后，一起做所有询问的逆 $dfs$ 序部分，也就是说按照逆 $dfs$ 序扫描每个商品，遇到了一个询问的起点，就把这个询问对应的起始金钱丢入一个数据结构中，过了一个询问的中点，就把这个询问对应的剩余金钱从数据结构中取出来。然后每扫过一个 $p_i$ ，数据结构都要对内部 $[p_i,+\infin)$ 的键值进行减 $p_i$ 。

可以用平衡树做这个数据结构。

区间减的时候分为两部分，对于 $[p_i,2p_i)$ 的键值，暴力取出来然后改值之后塞进去，均摊每个值最多操作 $O(\log w)$ 次。

对于 $[2p_i,+\infin)$ 直接打 tag 维护，因为减掉之后互不影响相对位置。

逆 $dfs$ 序部分做完之后，类似的做一遍顺 $dfs$ 序就行了。

总复杂度可以这么计算，每个询问变成了 $O(\log n)$ 段，但是题目性质保证我们在扫描的时候平衡树的 $size$ 是 $O(n)$ ，平衡树的操作还是 $O(\log n)$ 的，再算上每个询问有 $O(\log w)$ 次平衡树上的暴力修改，总复杂度大致是 $O(n\log^2 n +n\log n\log w )$

最后我用的 $\text{FHQ Treap}$ 实现的，代码长度有点窒息。

要注意一下 $\text{FHQ Treap}$ 的插入，需要硬拆开再合并。

#include <queue>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAXN 100011
#define LL long long
using namespace std;
int n,m;
int tot,pre[MAXN],lin[MAXN*2],to[MAXN*2];
int fa[MAXN],son[MAXN],dep[MAXN],siz[MAXN],dfn[MAXN],anti_dfn[MAXN];
int num;
int top[MAXN];
int p[MAXN];
struct Query{
    int st,ed;
    int w,id,tree_node;
}q[MAXN];
struct WALK{
    bool is_st;
    int loc;
    int belong;
    WALK(){}
    WALK(int _is_st,int _loc,int _belong):is_st(_is_st),loc(_loc),belong(_belong){}
};
bool cmp(WALK x,WALK y)
{
    return x.loc==y.loc?x.is_st > y.is_st : x.loc < y.loc;
}
bool rev_cmp(WALK x,WALK y)
{
    return x.loc==y.loc?x.is_st > y.is_st : x.loc > y.loc;
}
vector<WALK > vec,rev_vec;

void add(int x,int y)
{
    tot++;lin[tot]=pre[x];pre[x]=tot;to[tot]=y;
}
void dfs1(int x)
{
    siz[x]=1;
    for(int i=pre[x];i;i=lin[i])
    {
        int v=to[i];
        if(v==fa[x])continue;
        fa[v]=x;
        dep[v]=dep[x]+1;
        dfs1(v);
        siz[x]+=siz[v];
        if(siz[son[x]]<siz[v])
            son[x]=v;
    }
}
void dfs2(int x)
{
    dfn[x]=++num;
    anti_dfn[num]=x;
    if(x==son[fa[x]])
        top[x]=top[fa[x]];
    else
        top[x]=x;
    if(son[x])
        dfs2(son[x]);
    for(int i=pre[x];i;i=lin[i])
    {
        int v=to[i];
        if(v==fa[x]||v==son[x])continue;
        dfs2(v);
    }
}
void LCA(int x,int y,int belong)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]] > dep[top[y]])
        {
            rev_vec.push_back(WALK(true,dfn[x],belong));
            rev_vec.push_back(WALK(false,dfn[top[x]],belong));
            x=fa[top[x]];
        }
        else
        {
            vec.push_back(WALK(true,dfn[top[y]],belong));
            vec.push_back(WALK(false,dfn[y],belong));
            y=fa[top[y]];
        }
    }
    if(dep[x] > dep[y])
    {
        rev_vec.push_back(WALK(true,dfn[x],belong));
        rev_vec.push_back(WALK(false,dfn[y],belong));
    }
    else
    {
        vec.push_back(WALK(true,dfn[x],belong));
        vec.push_back(WALK(false,dfn[y],belong));
    }   
}
struct QUEUE{
    int q[MAXN],head,tail;
    QUEUE(){head=tail=0;}
    bool empty(){return tail==head;}
    void pop(){head++;if(head==MAXN)head=0;}
    void push(int x){q[tail++]=x;if(tail==MAXN)tail=0;}
    int front(){return q[head];}
    void clear(){head=tail=0;}
};
struct FHQ_Treap{
    static const int Null = 0;
    QUEUE que;
    int num,root;
    struct node{
        int l,r,fa;
        int rnd,val,belong,siz,tag;
        node(){siz=tag=0;}
    }tr[MAXN*2];

    void init(){num=0;root=Null;que.clear();}
    void pushup(int x)
    {
        tr[x].siz=tr[tr[x].l].siz+tr[tr[x].r].siz+1;
        tr[tr[x].l].fa=tr[tr[x].r].fa=x;
    }
    void pushdown(int x)
    {
        if(tr[x].tag)
        {
            int L=tr[x].l,R=tr[x].r;
            if(L)
            {
                tr[L].val+=tr[x].tag;
                tr[L].tag+=tr[x].tag;
            }
            if(R)
            {
                tr[R].val+=tr[x].tag;
                tr[R].tag+=tr[x].tag;
            }
            tr[x].tag=0;
        }
    }
    inline int rnd(){return rand();}
    int add(int val,int belong)
    {
        int now;
        if(!que.empty())
        {
            now=que.front();
            que.pop();
        }
        else
            now = ++num;
        q[belong].tree_node=now;
        tr[now].l=tr[now].r=Null;
        tr[now].rnd=rnd();
        tr[now].siz=1;tr[now].val=val;tr[now].belong=belong;
        return now;
    }
    void split_val(int x,int k,int &l,int &r)
    {
        if(!x){l=r=Null;return;}
        pushdown(x);
        if(tr[x].val<=k){l=x;split_val(tr[x].r,k,tr[x].r,r);}
        else {r=x;split_val(tr[x].l,k,l,tr[x].l);}
        pushup(x);
    }
    void split_rank(int x,int k,int &l,int &r)
    {
        if(!x){l=r=Null;return;}
        pushdown(x);
        if(tr[tr[x].l].siz+1<=k)
        {l=x;split_rank(tr[x].r,k-tr[tr[x].l].siz-1,tr[x].r,r);}
        else
        {r=x;split_rank(tr[x].l,k,l,tr[x].l);}
        pushup(x);
    }
    int merge(int x,int y)
    {
        if(!x||!y)return x|y;
        if(tr[x].rnd < tr[y].rnd)
        {
            pushdown(x);
            tr[x].r=merge(tr[x].r,y);pushup(x);return x;
        }
        else
        {
            pushdown(y);
            tr[y].l=merge(x,tr[y].l);pushup(y);return y;
        }
    }

    void insert(int val,int belong)
    {
        int l,r;
        split_val(root,val,l,r);
        root = merge(l,merge(add(val,belong),r));
    }

    int find_node_rank(int x)
    {
        int ans = tr[tr[x].l].siz+1;
        while(x!=root)
        {
            int fa=tr[x].fa;
            if(x==tr[fa].r)ans+=tr[tr[fa].l].siz+1;
            x=fa;
        }
        return ans;
    }

    int Delete_node(int x)
    {
        int rk=find_node_rank(x);
        int l,r,mid;
        split_rank(root,rk-1,l,r);
        split_rank(r,1,mid,r);
        que.push(mid);
        root=merge(l,r);
        return mid;
    }

    void dfs_mid(int x,int val,int &l)
    {
        pushdown(x);
        if(tr[x].l)dfs_mid(tr[x].l,val,l);
        if(tr[x].r)dfs_mid(tr[x].r,val,l);
        tr[x].l=tr[x].r=Null;
        tr[x].siz=1;tr[x].val-=val;//tag?
        int L,R;
        split_val(l,tr[x].val,L,R);
        l=merge(L,merge(x,R));
    }

    void modify(int val)
    {
        int l,mid,r;
        split_val(root,val-1,l,r);
        split_val(r,val+val-1,mid,r);
        if(r)
        {
            tr[r].val-=val;
            tr[r].tag-=val;
        }
        if(mid)dfs_mid(mid,val,l);
        root=merge(l,r);
    }

}treap;
void init()
{
    vec.clear();rev_vec.clear();
    for(int i=1;i<=n;i++)
    {
        pre[i]=0;
        son[i]=fa[i]=0;
    }
    tot=0;
    num=0;
    treap.init();
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        init();
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)scanf("%d",&p[i]);
        for(int i=1;i<n;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            add(x,y);
            add(y,x);
        }
        dfs1(1);dfs2(1);
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&q[i].st,&q[i].ed,&q[i].w);
            LCA(q[i].st,q[i].ed,i);
        }
        sort(vec.begin(),vec.end(),cmp);
        sort(rev_vec.begin(),rev_vec.end(),rev_cmp);
        for(int i=n,j=0;i>=1;i--)
        {
            while(j<rev_vec.size() && rev_vec[j].loc == i && rev_vec[j].is_st)
            {
                treap.insert(q[rev_vec[j].belong].w,rev_vec[j].belong);
                j++;
            }
            treap.modify(p[anti_dfn[i]]);
            while(j<rev_vec.size() && rev_vec[j].loc == i && !rev_vec[j].is_st)
            {
                int nd=treap.Delete_node(q[rev_vec[j].belong].tree_node);
                q[treap.tr[nd].belong].w = treap.tr[nd].val;
                j++;
            }
        }

        for(int i=1,j=0;i<=n;i++)
        {
            while(j<vec.size() && vec[j].loc == i && vec[j].is_st)
            {
                treap.insert(q[vec[j].belong].w,vec[j].belong);
                j++;
            }
            treap.modify(p[anti_dfn[i]]);
            while(j<vec.size() && vec[j].loc == i && !vec[j].is_st)
            {
                int nd=treap.Delete_node(q[vec[j].belong].tree_node);
                q[vec[j].belong].w = treap.tr[nd].val;
                j++;
            }
        }

        for(int i=1;i<=m;i++)
        {
            printf("%d\n",q[i].w);
        }
    }
    return 0;
}