2016年2月29日 星期一

[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);
    }
}

沒有留言:

張貼留言