bzoj 3672: [Noi2014]购票树链剖分+维护凸包

3672: [Noi2014]购票

Time Limit: 30 Sec Memory Limit: 512 MB
Submit: 480 Solved: 212
[Submit][Status][Discuss]

Description

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

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

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

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

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

Input

第
1 行包含2个非负整数 n,t，分别表示城市的个数和数据类型（其意义将在后面提到）。输入文件的第 2 到 n
行，每行描述一个除SZ之外的城市。其中第 v 行包含 5 个非负整数 f_v,s_v,p_v,q_v,l_v，分别表示城市 v
的父亲城市，它到父亲城市道路的长度，票价的两个参数和距离限制。请注意：输入不包含编号为 1 的SZ市，第 2 行到第 n 行分别描述的是城市 2
到城市 n。

Output

输出包含 n-1 行，每行包含一个整数。其中第 v 行表示从城市 v+1 出发，到达SZ市最少的购票费用。同样请注意：输出不包含编号为 1 的SZ市。

Sample Input

7 3
1 2 20 0 3
1 5 10 100 5
2 4 10 10 10
2 9 1 100 10
3 5 20 100 10
4 4 20 0 10

Sample Output

40
150
70
149
300
150

HINT

对于所有测试数据，保证 0≤p_v≤10⁶，0≤q_v≤10¹²，1≤f_v<v；保证 0<s_v≤l_v≤2×10¹¹，且任意城市到SZ市的总路程长度不超过 2×10¹¹。

输入的 t 表示数据类型，0≤t<4，其中：

当 t=0 或 2 时，对输入的所有城市 v，都有 f_v=v-1，即所有城市构成一个以SZ市为终点的链；

当 t=0 或 1 时，对输入的所有城市 v，都有 l_v=2×10¹¹，即没有移动的距离限制，每个城市都能到达它的所有祖先；

当 t=3 时，数据没有特殊性质。

n=2×10^5

　　首先提一下hja的做法orz，容易想出这道题只要能够实现凸包的快速加点撤点就行了，然后一般都会往可持久化平衡树那个方面去想，然而注意本体的特点，凸包其实可以用单调栈维护，每一次加点变的只有两个东西：栈顶指针，新站顶指针所在的那个地方的值，所以说我们强行把改变量存一下就可以轻松撤消了。

　　然而由于已经写好链剖，所以就没有写那个东西了。

　　咋个分析链剖也有问题啊，剖分O(log)，线段树O(log)，二分O(log)，总的O(nlog^3n)，过个毛线啊。然而，链剖就是过了QAQ

　　难道那两个log真的可以合并？知道证明的麻烦留言以下，谢谢。

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cassert>

#include<set>

#include<vector>

using namespace std;

#define MAXN 299990

#define MAXT MAXN*4

#define MAXV MAXN

#define MAXE MAXV*2

#define smid ((l+r)>>1)

#define lch (now<<1)

#define rch (now<<1^1)

#define INFL 0x3f3f3f3f3f3f3f3fLL

typedef long double real;

typedef long long qword;

struct point

{

        point(){}

        point(qword x,qword y):x(x),y(y){}

        qword x,y;

};

real xmul(point p1,point p2,point p3)

{

        return (real)(p2.x-p1.x)*(p3.y-p1.y) - (real)(p2.y-p1.y)*(p3.x-p1.x);

}

struct sgt_node

{

        vector<point> vec;

}sgt[MAXT];

void Add_convex(vector<point> &vec,point pt)

{

        while (vec.size()>= && xmul(vec[vec.size()-],vec[vec.size()-],pt)<)

                vec.pop_back();

        vec.push_back(pt);

}

qword Query_convex(vector<point> &vec,qword t,qword k)

{

        if (vec.size()==)return INFL;

        int l=,r=(int)vec.size();

        int mid;

    /*    printf("-----------------------------------\n{k=%lld,t=%lld}\n",k,t);

        for (int i=0;i<vec.size();i++)

                printf("(%lld,%lld) ",vec[i].x,vec[i].y);

        printf("\n");*/

        while (l+<r)

        {

                mid=(l+r)>>;

                if ((real)(vec[mid].y-vec[mid-].y)/(vec[mid].x-vec[mid-].x)<=k)

                        l=mid;

                else

                        r=mid;

        }

    //    printf("[%d]\n",l);

        return vec[l].y+k*(t-vec[l].x);

}

void Add_sgt(int now,int l,int r,int pos,point pt)

{

        Add_convex(sgt[now].vec,pt);

        if (l==r)return ;

        if (pos<=smid)

                Add_sgt(lch,l,smid,pos,pt);

        else

                Add_sgt(rch,smid+,r,pos,pt);

}

qword Qry_sgt(int now,int l,int r,int x,int y,qword t,qword k)

{

        if (l==x && r==y)

                return Query_convex(sgt[now].vec,t,k);

        if (y<=smid)

                return Qry_sgt(lch,l,smid,x,y,t,k);

        else if (smid<x)

                return Qry_sgt(rch,smid+,r,x,y,t,k);

        else

                return min(Qry_sgt(lch,l,smid,x,smid,t,k),Qry_sgt(rch,smid+,r,smid+,y,t,k));

}

struct Edge

{

        int np,val;

        Edge *next;

}E[MAXE],*V[MAXV];

int tope=-;

void addedge(int x,int y,int z)

{

        E[++tope].np=y;

        E[tope].val=z;

        E[tope].next=V[x];

        V[x]=&E[tope];

}

int v1[MAXN];

qword v2[MAXN];

qword l[MAXN];

int pnt[MAXN],pdis[MAXN];

int son[MAXN],siz[MAXN];

int n,m;

int q[MAXN];

qword rdis[MAXN];

void bfs(int now)

{

        int head=-,tail=;

        Edge *ne;

        q[]=now;

        while (head<tail)

        {

                now=q[++head];

                for (ne=V[now];ne;ne=ne->next)

                {

                        q[++tail]=ne->np;

                        rdis[ne->np]=rdis[now]+pdis[ne->np];

                }

        }

        int mxsiz=;

        for (int i=tail;i>=;i--)

        {

                now=q[i];

                siz[now]=;

                mxsiz=;

                for (ne=V[now];ne;ne=ne->next)

                {

                        siz[now]+=siz[ne->np];

                        if (mxsiz<siz[ne->np])

                        {

                                mxsiz=siz[ne->np];

                                son[now]=ne->np;

                        }

                }

        }

}

int stack[MAXN],tops=-;

int top[MAXN];

int pos[MAXN],dfstime;

void dfs(int now)

{

        Edge *ne;

        stack[++tops]=now;

        top[now]=now;

        while (~tops)

        {

                now=stack[tops--];

                pos[now]=++dfstime;

                for (ne=V[now];ne;ne=ne->next)

                {

                        if (ne->np==son[now])continue;

                        stack[++tops]=ne->np;

                        top[ne->np]=ne->np;

                }

                if (son[now])

                {

                        stack[++tops]=son[now];

                        top[son[now]]=top[now];

                }

        }

}

qword dp[MAXN];

int jump[][MAXN];

qword jdis[][MAXN];

void init_lca()

{

        pnt[]=;

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

                jump[][i]=pnt[i],jdis[][i]=pdis[i];

        for (int j=;j<;j++)

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

                {

                        jump[j][i]=jump[j-][jump[j-][i]];

                        jdis[j][i]=jdis[j-][jump[j-][i]]+jdis[j-][i];

                }

}

int swim(int now,qword len)

{

        for (int i=;i>=;i--)

        {

                if (jdis[i][now]<=len)

                        len-=jdis[i][now],now=jump[i][now];

        }

        return now;

}

int main()

{

        freopen("input.txt","r",stdin);

        //freopen("output.txt","w",stdout);

        int x,y,z;

        scanf("%d%d",&n,&x);

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

        {

                scanf("%d%d%d%lld%lld",pnt+i,pdis+i,v1+i,v2+i,l+i);

                addedge(pnt[i],i,pdis[i]);

        }

        bfs();

        dfs();

        init_lca();

        dp[]=;

        Add_sgt(,,n,pos[],point(rdis[],dp[]));

        int a;

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

        {

                x=i;

                a=swim(x,l[i]);

                qword ans=INFL;

                while (x)

                {

                        if (top[x]==top[a])

                        {

                                ans=min(ans,Qry_sgt(,,n,pos[a],pos[x],rdis[i],v1[i])+v2[i]);

                                break;

                        }

                        ans=min(ans,Qry_sgt(,,n,pos[top[x]],pos[x],rdis[i],v1[i])+v2[i]);

                        x=pnt[top[x]];

                }

                assert(ans!=INFL);

                dp[i]=(qword)ans;

                Add_sgt(,,n,pos[i],point(rdis[i],dp[i]));

                printf("%lld\n",dp[i]);

        }

        return ;

}

秒客网

bzoj 3672: [Noi2014]购票树链剖分+维护凸包

3672: [Noi2014]购票

Description

Input

Output

Sample Input

Sample Output

HINT

相关文章

bzoj 3672: [Noi2014]购票 树链剖分+维护凸包

3672: [Noi2014]购票

Description

Input

Output

Sample Input

Sample Output

HINT

相关文章

bzoj 3672: [Noi2014]购票树链剖分+维护凸包