[SDOI2016]游戏（树剖+李超树）

淡淡的烟草味﹌ 2021-11-01 08:46 241阅读 0赞

趁着我把李超树忘个一干二净的时候来复习一下吧，毕竟马上NOI了。

题解：看着那个dis就很不爽，直接把它转换成深度问题，然后一条直线x->y，假设其lca为z，可以拆分成x->z和z->y两条路径，然后将函数分成两段即可，把式子转换为以节点深度为变量的一次函数，求解最值，树链剖分+李超树求解，保留函数最小值即可。其实也挺裸的，但码量有点大（毕竟我写code一贯行数少+紧凑，写122行算大了），不过都很套路。

然后下面讲一下李超树：

首先覆盖还是原样覆盖，对于修改的区间\[l,r\]，假设函数是kx+b，可以如下求解：初始化函数y=123456789123456789，然后开始覆盖区间。如果左右端点都比原函数小，说明可以直接覆盖。如果左右端点都比原函数大，说明此函数无用，直接退出即可。反之，保留在函数中以最小值出现较长的函数，然后把较短的在其左/右半部分递归处理。

至于查询操作，如果该区间已经被线段覆盖，则直接取询问左右端点的最小值即可，写法上，与普通的线段树有一些不同（根据我的代码习惯）。

注意保留区间最小值，方便查询。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    #define lson l,mid,rt<<1
    #define rson mid+1,r,rt<<1|1
    using namespace std;
    typedef long long ll;
    const int N=1e5+7;
    const ll inf=123456789123456789ll;
    int n,m,cnt,hd[N],v[N<<1],nxt[N<<1],w[N<<1],sz[N],son[N],fa[N],pos[N],id[N],top[N],lk[N<<2];
    ll ans,d[N],val[N<<2],lb[N<<2];
    bool lazy[N<<2];
    void adde(int x,int y,int z){v[++cnt]=y,nxt[cnt]=hd[x],w[cnt]=z,hd[x]=cnt;}
    void dfs(int u)
    {
        sz[u]=1;
        for(int i=hd[u];i;i=nxt[i])
        if(v[i]!=fa[u])
        {
            fa[v[i]]=u,d[v[i]]=d[u]+w[i],dfs(v[i]),sz[u]+=sz[v[i]];
            if(sz[v[i]]>sz[son[u]])son[u]=v[i];
        }
    }
    void dfs2(int u,int tp)
    {
        id[pos[u]=++cnt]=u,top[u]=tp;
        if(son[u])dfs2(son[u],tp);
        for(int i=hd[u];i;i=nxt[i])if(v[i]!=fa[u]&&v[i]!=son[u])dfs2(v[i],v[i]);
    }
    int lca(int x,int y)
    {
        while(top[x]!=top[y])
        {
            if(d[top[x]]<d[top[y]])swap(x,y);
            x=fa[top[x]];
        }
        return d[x]<d[y]?x:y;
    }
    void build(int l,int r,int rt)
    {
        val[rt]=inf;
        if(l==r)return;
        int mid=l+r>>1;
        build(lson),build(rson);
    }
    void pushdown(int l,int r,int rt)
    {
        if(l<r)val[rt]=min(val[rt<<1],val[rt<<1|1]);else val[rt]=inf;
        if(lazy[rt])val[rt]=min(val[rt],min(d[id[l]]*lk[rt],d[id[r]]*lk[rt])+lb[rt]);
    }
    void modify(int l,int r,int rt,int u,ll v)
    {
        if(!lazy[rt])lazy[rt]=1,lk[rt]=u,lb[rt]=v;
        else{
            ll x1=d[id[l]]*u+v,y1=d[id[r]]*u+v;
            ll x2=d[id[l]]*lk[rt]+lb[rt],y2=d[id[r]]*lk[rt]+lb[rt];
            int mid=l+r>>1;
            if(x1<=x2&&y1<=y2)lk[rt]=u,lb[rt]=v;
            else if(x1>=x2&&y1>=y2)return;
            else if(u<lk[rt])
            {
                ll tmp=(v-lb[rt])/(lk[rt]-u)+1;
                if(tmp<=d[id[mid]])swap(u,lk[rt]),swap(v,lb[rt]),modify(lson,u,v);
                else modify(rson,u,v);
            }
            else{
                ll tmp=(lb[rt]-v-1)/(u-lk[rt]);
                if(tmp>d[id[mid]])swap(u,lk[rt]),swap(v,lb[rt]),modify(rson,u,v);
                else modify(lson,u,v);
            }
        }
        pushdown(l,r,rt);
    }
    void insert(int L,int R,int u,ll v,int l,int r,int rt)
    {
        if(L<=l&&r<=R){modify(l,r,rt,u,v);return;}
        int mid=l+r>>1;
        if(L<=mid)insert(L,R,u,v,lson);
        if(R>mid)insert(L,R,u,v,rson);
        pushdown(l,r,rt);
    }
    void query(int L,int R,int l,int r,int rt)
    {
        if(L==l&&r==R){ans=min(ans,val[rt]);return;}
        if(lazy[rt])ans=min(ans,min(d[id[L]]*lk[rt],d[id[R]]*lk[rt])+lb[rt]);
        int mid=l+r>>1;
        if(R<=mid)query(L,R,lson);
        else if(L>mid)query(L,R,rson);
        else query(L,mid,lson),query(mid+1,R,rson);
    }
    int main()
    {
        scanf("%d%d",&n,&m);
        for(int i=1,x,y,z;i<n;i++)scanf("%d%d%d",&x,&y,&z),adde(x,y,z),adde(y,x,z);
        dfs(1),cnt=0,dfs2(1,1);
        build(1,n,1);
        while(m--)
        {
            int op,x,y,z,u,v;scanf("%d%d%d",&op,&x,&y);
            if(op==1)
            {
                scanf("%d%d",&u,&v);
                z=lca(x,y);
                ll tmp=d[x]*u+v;
                while(top[x]!=top[z])insert(pos[top[x]],pos[x],-u,tmp,1,n,1),x=fa[top[x]];
                insert(pos[z],pos[x],-u,tmp,1,n,1);
                tmp-=(d[z]<<1)*u;
                while(top[y]!=top[z])insert(pos[top[y]],pos[y],u,tmp,1,n,1),y=fa[top[y]];
                insert(pos[z],pos[y],u,tmp,1,n,1);
            }
            else{
                ans=inf;
                while(top[x]!=top[y])
                {
                    if(d[top[x]]<d[top[y]])swap(x,y);
                    query(pos[top[x]],pos[x],1,n,1);
                    x=fa[top[x]];
                }
                if(d[x]>d[y])swap(x,y);
                query(pos[x],pos[y],1,n,1);
                printf("%lld\n",ans);
            }
        }
    }

转载于:https://www.cnblogs.com/hfctf0210/p/11148810.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211101/97ef91b8f804492bb85961440255a319.png