Trouble of Tyrant （固定圖邊加長最短路 轉 直線群最小值）

題目來源

2018 ACM-ICPC 中國大學生程式設計競賽線上賽

Tyrant has a private island on the Pacific Ocean. He has built many luxury villas on the island. He flies here every vacation to enjoy life. He will drive his sports car between his villas. Tyrant has n villas on the island and the last villa which is numbered by n is his favorite. His money is only allowed to build one airpor located at the first villa which is numbered by 1 so every time he come to the island, he will land at the villa numbered 1. What's more Tyrant build 2*n-3 roads on the island. For every villa except the first island, there is a two-way street connecting this villa and the first villa. For every villa numbered by i (i >= 3) there is a two-way street connecting this villa and the villa numbered by i - 1. Tyrant is not satisfied, he think the road is not long enough. He asks q problems, every problem has a non negative integer d. He want to know if the length of each road is increaced by d what is the shortest distance between the first villa and his favorite villa. Notice that the increment in each problem is not cumulative -- in other words it doesn't take effect on the real road after query.

Input:

The first integer indicate the number of test cases T (T <= 10).

In each test cases the first line contains two integers n and q -- the number of villas and the number of queries (3 <= n <= 100000, 1 <= q <= 100000).

The second line contains n - 1 non-negative integers -- ai describe a road with length ai connecting villa 1 and i (2 <= i <= n)

The third line contains n - 2 non-negative integers -- bi describe a road with length bi connecting villa i - 1 and i (3 <= i <= n)

The next line contains q non-negative integers -- di means Tyrant want to know what is the shortest distance between the first villa ans his favorite villa when the length of each road is increaced by di.

All integers are 32-bit signed integer.

Output:

For each test case you should output q integers in one line means the answer for each problem.

樣例輸入

1
3 3
1 5
2
0 2 4      

樣例輸出

3 7 9      

【題意】

一個無向圖，n個點，從1至n都有一條邊，從3~n每一個點都與前一個點有條邊。

然後q次詢問，每次輸入一個d，問假如把圖的每條邊都增加d，那麼從1->n的最短路是多少

【分析】

這是昨天甯夏網絡賽的一道題，當時二分查找沒處理好就是不對，今天二分查找後面加了句l--，踢掉了原來那句，奇迹般的過了。

通過畫圖很容易發現從1->n的路徑隻有兩條，要麼直達，要麼先一步去2~n-1中的一個，再往後一步步走到n。

那麼就可以算一算，對于每一個點i，1->i ->n的初始路長是多少（這是一個定值），存在數組c[]中

當詢問時，對于每個點的路長為 c[i] + (n-i+1)*d ，那麼就需要求出可以作為最小值得i，即某個點滿足這個式子是最小值。

令斜率a=n-i+1，截距b=c[i]，令自由變量x=d，就會發現這是一個一進制一次直線，而把每一個點i對應的那條直線，都畫出來，大概是這樣：

直線群相交形成的下邊沿，就隻能取到最小值的地方，對于不同的d，取最小值的直線不同，即圖上的點不同。

接下來就要就出這個邊沿，對于不同的d，選直線就行了。方法與bzoj 1007一樣，題解。

将直線按斜率大小排序，斜率相同的按b小大排序，然後開始掃描，儲存下能在下方的直線及其與前一直線的交點，便于二分找到d所在的位置。

【代碼】

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
const int INF=0x3f3f3f3f;
struct node {
    ll x,y;
}e[N];
ll a[N],b[N],c[N];

struct line{//存直線
    ll a,b;
    double x1;
    int dex;
}l[502020],s[502020];//l存直線，s模拟棧
bool cmp(line l1,line l2)//按斜率
{
    if(l1.a==l2.a)return l1.b<l2.b;
    return l1.a>l2.a;
}
double getx(line l1,line l2)//求兩直線交點的x坐标
{
    return 1.0*(l2.b-l1.b)/(l1.a-l2.a);
}
int main()
{
    int T,n,m,u,v,q,d;
    cin>>T;
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(int i=2;i<=n;i++) scanf("%d",&a[i]);
        for(int i=3;i<=n;i++) scanf("%d",&b[i]);
        c[n]=0;
        for(int i=n-1;i>=2;i--) c[i]=c[i+1]+b[i+1];
        for(int i=2;i<=n;i++) c[i]+=a[i];

        for(int i=2;i<=n;i++)l[i]=line{n-i+1,c[i]}; //step, len
        sort(l+2,l+n+1,cmp);

        int top=0;//s的下标
        s[++top]=l[2];
        s[top].x1=0;
        s[top].dex=2;

        for(int i=3;i<=n;i++)//周遊直線
        {
            if(l[i].a==l[i-1].a)continue;//會被覆寫
            while(top>1&&getx(l[i],s[top])<getx(s[top],s[top-1]))top--;//可以覆寫上一條直線
            s[++top]=l[i];
            s[top].x1=getx(s[top],s[top-1]);
            s[top].dex=i;
        }
        for(int i=0;i<m;i++)
        {
            scanf("%d",&d);
            int l=1,r=top+1,mid;
            while(l<r)
            {
                mid=(l+r)/2;
                if(s[mid].x1>d)r=mid;
                else l=mid+1;
            }
            l--;
            int dex=s[l].dex;
            ll ans=c[dex]+1ll*(n-dex+1)*d;

            if(i)printf(" ");
            printf("%lld",ans);
        }
        printf("\n");
    }
}