[Codeforces Round #333 (Div. 1) pB][Stack] Lipshitz Sequence

原題連結
一開始看形式以為是要做凸包之類的優化....結果一直想下去還是沒有活路......


本題最重要的一點：題目要求的最大值只會發生在相鄰點。

有了這個性質之後就變得很簡單的....至於要怎麼想到這點呢.....
.
.
.
其實我也沒想到orz
是看了別人題解的第一句話驚呆了之後才去證明的.....結果非常好證orz
枚舉一下相鄰3個點的高低位置，就會發現不管怎麼擺，相鄰點的斜率絕對玩爆非相鄰點的斜率......

有了上面那個性質之後，我們把原序列先轉為相鄰兩項的絕對值，那麼我們就變成要求某段區間的最大值。

例如：

1 5 2 9 1 3 4 2 1 7
會變成
4 3 7 8 2 1 2 1 6

那要怎麼做呢？假設我們現在要詢問上面整個序列的答案(L=1,R=10)
由於我們是讓i從左往右遞增，對於每個i，我們只需要計算所有以i結尾的序列就好(想一想，為什麼XD)

觀察一下，如果i=10，所有以i為結尾的答案會是多少呢？

答案是：
8 8 8 8 6 6 6 6 6
沒錯！樸素作法就是對於每個結尾往前枚舉，每當遇到更大的值時就更新，加總起來就是答案。

怎麼加速呢？
觀察到，如果某個a[i]<a[j]且i<j，那麼這個i就是個廢物(?，i已經不可能再變成最大值了，所以可以直接拿掉。
然後作法就有如一般的單調堆疊一樣了。
(如果想不到如何均攤O(1)更新答案，可以參考code)

#define LL long long
#include<algorithm>
#include<cstdio>
#include<stack>
using namespace std;
const int maxn=100000+5;
int a[maxn];
stack<int> S;
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) {scanf("%d",a+i); a[i-1]=abs(a[i]-a[i-1]);}
    while(m--)
    {
        int L,R;
        LL ans=0,add=0;
        scanf("%d%d",&L,&R);
        while(!S.empty()) S.pop();
        for(int i=L;i<R;i++)
        {
            while(!S.empty() && a[i]>a[S.top()])
            {
                int x=S.top();
                S.pop();
                if(S.empty()) add-=(LL)(x-L+1)*a[x];
                else add-=(LL)(x-S.top())*a[x];
            }
            if(S.empty()) add+=(LL)(i-L+1)*a[i];
            else add+=(LL)(i-S.top())*a[i];
            ans+=add;
            S.push(i);
        }
        printf("%I64d\n",ans);
    }
}