csuoj 2316 Joined Vessels

Description

John is doing physics practice at school. Today he is studying the law of communicating vessels. This law states that if we have a set of communicating containers with a homogeneous liquid, when the liquid settles, it balances out to the same level in all of the containers regardless of their shape and volume.

In the lab, John has a set of n cylindrical vessels with a base area of one square decimeter and a height that we consider to be infinite. The vessels are numbered from 1 to n, and vessels i and i + 1 are communicating via a very thin bridge at a height of hi decimeters. All these heights are pairwise distinct.

The practice work contains t independent experiments. In each experiment, all vessels are initially empty. In the i-th experiment, water is slowly put into vessel ai, and the experiment finishes when any amount of water appears in vessel bi. The result of the experiment is the total volume of water put into vessel ai, measured in liters (or, equivalently, cubic decimeters).

Note that the law of communicating vessels can only be applied to vessels i and i + 1 when the water level is at least hi in both of them. Until then, if the water level reaches hi in just one of them, it stays constant and any excess water coming into this vessel flows through the bridge into the other one.

Help John check his results!

Input

The first line of the input contains an integer n --- the number of vessels (2 ≤ n ≤ 2 ⋅ 105).

The second line contains n − 1 integers h1, h2, …, hn − 1 --- the heights of communication bridges between consecutive vessels, in decimeters (1 ≤ hi ≤ 109). These heights are pairwise distinct.

The third line contains an integer t --- the number of experiments (1 ≤ t ≤ 2 ⋅ 105).

Each of the following t lines contains two integers ai and bi --- the numbers of the starting vessel and the target vessel in the i-th experiment (1 ≤ ai ≤ n; 1 ≤ bi ≤ n; ai ≠ bi).

Output

For each experiment, in the order of input, output a single integer --- the required volume of water, in liters.

Sample Input

6

1 4 2 3 5

4

1 6

6 1

2 5

5 2

Sample Output

25

18

14

12

題意:n個桶,第i個桶和第i+1個桶有高度為hi的導管連通，m個詢問，問将水不斷導入桶a,要倒多少才會有水流入桶b。n,m<=2e5

分析:考慮a<b時的情況(a>b時逆序處理)，每次将水倒入a，有水流入b時，則桶a到桶b-1的水準面呈階梯形下降，且不管将水從a左邊哪個桶倒入，桶a到桶b-1的水準高度都不會變。這樣可以用字首和，sum[i]表示從第一個桶開始倒水，水溢過第i根管子時需倒入的水量。同時還要考慮将水倒入a時，水往左流的情況，假設[a,b-1]導管的最大高度為max，則水會不斷往左流直到遇到高度大于max的管子k,這樣答案即為sum[b-1]-sum[k];

是以單調棧+RMQ。。。。

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<math.h>
using namespace std;
int st[200010],l1[200010],l2[200010];
long long sum1[200010],sum2[200010],A[2][200010],ma[2][1000010];

void update(int root,int l,int r,int k,int v,int id){
     if(l==r) ma[id][root]=l;
     else{
         int mid=(l+r)/2;
         if(k>mid) update(root*2+1,mid+1,r,k,v,id);
         else update(root*2,l,mid,k,v,id);
         if(A[id][ma[id][root*2]]>=A[id][ma[id][root*2+1]]) ma[id][root]=ma[id][root*2];
         else ma[id][root]=ma[id][root*2+1];
     }
}
int qmax(int root,int l,int r,int L,int R,int id){
     if(l==L&&r==R) return ma[id][root];
     int mid=(l+r)/2;
     if(R<=mid) return qmax(root*2,l,mid,L,R,id);
     else if(L>mid) return qmax(root*2+1,mid+1,r,L,R,id);
     else{
         int a=qmax(root*2,l,mid,L,mid,id),b=qmax(root*2+1,mid+1,r,mid+1,R,id);
         if(A[id][a]>=A[id][b]) return a;
         else return b;
     }
}


int main(){
    int a,b,c,d,m,i,n,top;
    scanf("%d",&n);
    for(i=1;i<n;i++){
        scanf("%lld",&A[0][i]);
        A[1][n-i]=A[0][i];    //逆序處理
    }
    for(i=1;i<n;i++){
        update(1,1,n-1,i,A[0][i],0);
        update(1,1,n-1,i,A[1][i],1);
    }
        
    top=0;          //單調棧處理左邊第一個大于它的數
    for(i=1;i<n;i++){
        while(top&&A[0][st[top]]<=A[0][i]) top--;
        if(top) l1[i]=st[top];
        else l1[i]=0;
        st[++top]=i;
    }
    for(i=1;i<n;i++) sum1[i]=sum1[l1[i]]+(i-l1[i])*A[0][i];

    top=0;
    for(i=1;i<n;i++){
        while(top&&A[1][st[top]]<=A[1][i]) top--;
        if(top) l2[i]=st[top];
        else l2[i]=0;
        st[++top]=i;
    }
    for(i=1;i<n;i++) sum2[i]=sum2[l2[i]]+(i-l2[i])*A[1][i];

    long long ans;
    scanf("%d",&m);
    while(m--){
        scanf("%d%d",&a,&b);
        if(a<b){
             b--;
             c=qmax(1,1,n-1,a,b,0);
             ans=sum1[b]-sum1[l1[c]];
        }
        else{
            a=n-a+1;
            b=n-b+1;
            b--;
            c=qmax(1,1,n-1,a,b,1);
            ans=sum2[b]-sum2[l2[c]];
        }
        printf("%lld\n",ans);
    }
    return 0;
}