[NOI2014]购票(斜率优化+线段树)

题目描述

今年夏天，NOI在SZ市迎来了她30周岁的生日。来自全国 n 个城市的OIer们都会从各地出发，到SZ市参加这次盛会。

全国的城市构成了一棵以SZ市为根的有根树，每个城市与它的父亲用道路连接。为了方便起见，我们将全国的 n 个城市用 1 到 n 的整数编号。其中SZ市的编号为 1。对于除SZ市之外的任意一个城市 v，我们给出了它在这棵树上的父亲城市 fv 以及到父亲城市道路的长度 sv。

从城市 v 前往SZ市的方法为：选择城市 v 的一个祖先 a，支付购票的费用，乘坐交通工具到达 a。再选择城市 a 的一个祖先 b，支付费用并到达 b。以此类推，直至到达SZ市。

对于任意一个城市 v，我们会给出一个交通工具的距离限制 lv。对于城市 v 的祖先 a，只有当它们之间所有道路的总长度不超过 lv 时，从城市 v 才可以通过一次购票到达城市 a，否则不能通过一次购票到达。对于每个城市 v，我们还会给出两个非负整数 pv,qv 作为票价参数。若城市 v 到城市 a 所有道路的总长度为 d，那么从城市 v 到城市 a 购买的票价为 dpv+qv。

每个城市的OIer都希望自己到达SZ市时，用于购票的总资金最少。你的任务就是，告诉每个城市的OIer他们所花的最少资金是多少。

题解

观察每个节点的答案表达式

dp[i]=min(dp[j]+(dis[i]-dis[j])*p[i]+q[i])

一个斜率一个常数，显然需要斜率优化。

先考虑树是一条链的情况

设i到根节点的两个祖先为j和k，且deep[k]>deep[j]

那么如果要保留j的话，要满足val(j)<val(k)

dp[j]+dis[i]*p[i]-dis[j]*p[i]+q[i]<dp[k]+dis[i]*p[i]-dis[k]*p[i]+q[i]。

dp[j]-dis[j]*p[i]<dp[k]-dis[k]*p[i]

(dp[k]-dp[j])/(dis[k]-dis[j])>=p[i]

这里dis是单调递增的，但p没有这种性质。

所以我们可以开一个单调栈，然后每次查询在栈内二分。

、

每次二份出来这个最优点就好了，插入一个数也一样，就是二分这个位置，把后面的都弹出。

然后这条链变成了一棵树。

可以先dfs这个树，然后对于一条链去维护这个栈。

我们虽然在dfs树，但是在计算机内部实现是一个栈在反复压栈弹栈。

所以我们需要支持维护这个栈，然后还需要支持撤销操作。

实现的话就维护一个以deep为下标的线段树，区间l-r的节点代表的是deep在l-r的范围内的所有点组成的单调栈，因为同一时刻合法的点深度各不相同。

所以我们要开O(n)单调栈，也可以提前开好，放在一个数组里。

每次dfs到一个节点时，就在线段树上找到包含自己的所有区间，然后对这些区间进行“加入一个数”这个操作，同时记录被改掉的信息，方便撤销。

对于一个查询，我们可以用树上倍增找出合法的深度区间，然后在线段树上查这个区间的最优解就好了，复杂度nlog²n

细节：把撤销写挂了，调了好久。

代码

#include<iostream>

#include<cstdio>

#define N 200009

#define int ll

using namespace std;

typedef long long ll;

ll n,q[N*],dis[N],dp[N],qi[N],pi[N],lim[N];

int tot,head[N],deep[N],remt[N][],remv[N][],p[N][],now=;

int ddf;

inline ll rd(){

    ll x=;char c=getchar();bool f=;

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

    while(isdigit(c)){x=(x<<)+(x<<)+(c^);c=getchar();}

    return f?-x:x;

}

struct SEG{int head,tail;}tr[N<<];

struct edge{int n,to,l;}e[N];

inline void add(int u,int v,int l){e[++tot].n=head[u];e[tot].to=v;head[u]=tot;e[tot].l=l;}

inline double get_k(int j,int k){return (double)((double)dp[j]-dp[k])/((double)dis[j]-dis[k]);}

inline int get_ans(int cnt,double p){

    int l=tr[cnt].head,r=tr[cnt].tail-,ans=-;

    if(tr[cnt].head>=tr[cnt].tail)return q[tr[cnt].tail];

    while(l<=r){

        int mid=(l+r)>>;

        if(get_k(q[mid],q[mid+])>=p){ans=mid;r=mid-;}else l=mid+;

    }

    if(ans<)ans=tr[cnt].tail;

    return q[ans];

}

int query(int cnt,int l,int r,int L,int R,double p){

    if(l>=L&&r<=R)return get_ans(cnt,p);

    int mid=(l+r)>>;

    if(mid>=L&&mid<R){

        int x=query(cnt<<,l,mid,L,R,p),y=query(cnt<<|,mid+,r,L,R,p);

        if(get_k(x,y)>=p)return x;else return y;

    }

    else if(mid>=L)return query(cnt<<,l,mid,L,R,p);

    else return query(cnt<<|,mid+,r,L,R,p);

}

inline int findqueue(int cnt,int u){

    if(tr[cnt].head>=tr[cnt].tail)return tr[cnt].tail;

    int l=tr[cnt].head,r=tr[cnt].tail-,ans=-;

    while(l<=r){

        int mid=(l+r)>>;

        if(get_k(q[mid],q[mid+])>get_k(q[mid],u))ans=mid,r=mid-;

        else l=mid+;

    }

    if(ans<)ans=tr[cnt].tail;

    return ans;

}

void build(int cnt,int l,int r){

    tr[cnt].tail=now-;tr[cnt].head=now;

    now+=(r-l+)+;

    if(l==r)return;int mid=(l+r)>>;

    build(cnt<<,l,mid);build(cnt<<|,mid+,r);

}

void insert(int cnt,int l,int r,int u,int x,int dep){

    int pos=findqueue(cnt,u)+;

    remt[u][dep]=tr[cnt].tail;

    remv[u][dep]=q[pos];

    q[pos]=u;tr[cnt].tail=pos;

    if(l==r)return;

    int mid=(l+r)>>;

    if(mid>=x)insert(cnt<<,l,mid,u,x,dep+);

    else insert(cnt<<|,mid+,r,u,x,dep+);

}

void del(int cnt,int l,int r,int u,int x,int dep){

    q[tr[cnt].tail]=remv[u][dep];

    tr[cnt].tail=remt[u][dep];

    if(l==r)return;

    int mid=(l+r)>>;

    if(mid>=x)del(cnt<<,l,mid,u,x,dep+);

    else del(cnt<<|,mid+,r,u,x,dep+);

}

inline int jump(int x,int l){

    int now=x;

    for(int i=;i>=;--i)if(p[now][i]&&dis[x]-dis[p[now][i]]<=l)now=p[now][i];

    return now;

}

void dfs(int u){

    for(int i=;(<<i)<=deep[u];++i)p[u][i]=p[p[u][i-]][i-];

    if(u!=){

        int x=jump(u,lim[u]);

        ddf=u;

        int y=query(,,n,deep[x],deep[p[u][]],pi[u]);

        dp[u]=dp[y]+(dis[u]-dis[y])*pi[u]+qi[u];

    }

    insert(,,n,u,deep[u],);

    for(int i=head[u];i;i=e[i].n){

       int v=e[i].to;dis[v]=dis[u]+e[i].l;

       deep[v]=deep[u]+;p[v][]=u;dfs(v);

    }

    del(,,n,u,deep[u],);

}

signed main(){

    n=rd();int t=rd();int father;int l;

    for(int i=;i<=n;++i){

        father=rd();l=rd();pi[i]=rd();qi[i]=rd();lim[i]=rd();

        add(father,i,l);

    }

    build(,,n);

    deep[]=;dfs();

    for(int i=;i<=n;++i)printf("%lld\n",dp[i]);

    return ;

}

巴特西

[NOI2014]购票(斜率优化+线段树)

最新文章

热门文章