计蒜课：Trouble of Tyrant（单调栈）

Description:

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

题目来源

2018 ACM-ICPC 中国大学生程序设计竞赛线上赛

思路：从1到n只需要考虑这样的n-1条路径，即从1->i->i+1->i+2->.....->n(1<=i<=n)，其它的路径都会有重复的部分，是没有意义的。记d[i]为一条这样的路径，则这条路径上有n-i+1条路，那么当每条路的长度增加dis时，ans=min(d[i]+(n-i+1)*dis)。那么化简一下d[i]=-(n-i+1)*dis+ans。即可利用斜率来维护一个单调栈。然后按照dis从大到小的顺序依次利用栈来更新答案即可。

#include<bits/stdc++.h>
using namespace std;
const int MAX=2e5+10;
const double PI=acos(-1.0);
typedef long long ll;
struct lenka
{
    ll dis;
    int index;
}c[MAX];
int cmp(const lenka& x,const lenka& y){return x.dis>y.dis;}
ll a[MAX],b[MAX],d[MAX],ans[MAX];
int q[MAX];
ll X(ll x1,ll x2){return -x1+x2;}
ll Y(ll y1,ll y2){return d[y1]-d[y2];}
int main()
{
    memset(a,0,sizeof a);
    memset(b,0,sizeof b);
    int T;
    cin>>T;
    while(T--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=2;i<=n;i++)scanf("%lld",&b[i]);
        for(int i=3;i<=n;i++)
        {
            scanf("%lld",&a[i]);
            a[i]+=a[i-1];
        }
        for(int i=n,j=2;i>=2;i--,j++)d[i-1]=b[j]+a[n]-a[j];
        for(int i=1;i<=m;i++)
        {
            scanf("%lld",&c[i].dis);
            c[i].index=i;
        }
        sort(c+1,c+m+1,cmp);
        int R=0;
        for(int i=n-1;i>=1;i--)
        {
            while(R>=2&&Y(i,q[R-1])*X(i,q[R])>=Y(i,q[R])*X(i,q[R-1]))R--;
            q[++R]=i;
        }
        for(int i=1;i<=m;i++)
        {
            while(R>=2&&d[q[R-1]]+q[R-1]*c[i].dis<=d[q[R]]+q[R]*c[i].dis)R--;
            ans[c[i].index]=d[q[R]]+q[R]*c[i].dis;
        }
        for(int i=1;i<=m;i++)printf("%lld%c",ans[i],i==m?'\n':' ');
    }
    return 0;
}