CodeForces 601B Lipshitz Sequence

Lipshitz Sequence

题解：

可以通过观察得到，对于任意一个区间来说，只有相邻的2个点的差值才会是区间的最大值。

具体观察方法，可以用数学分析，我是通过画图得到的。

那么基于上面的观察结果。

对于一次询问，我们可以枚举右端点，然后，不断的把右端点往右边移动，然后把新的值加进来，更新这个值所管理的区间。

用单调栈去维护每个差值所管辖的区间，然后在这个值出栈的时候，计算答案。

好久没用单调栈了，然后就干脆忘了这个东西..... 想用线段树去维护，显然会T就尬住了。。。。

代码：

#include<bits/stdc++.h>

using namespace std;

#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);

#define LL long long

#define ULL unsigned LL

#define fi first

#define se second

#define pb push_back

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define lch(x) tr[x].son[0]

#define rch(x) tr[x].son[1]

#define max3(a,b,c) max(a,max(b,c))

#define min3(a,b,c) min(a,min(b,c))

typedef pair<int,int> pll;

const int inf = 0x3f3f3f3f;

const int _inf = 0xc0c0c0c0;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const LL _INF = 0xc0c0c0c0c0c0c0c0;

const LL mod =  (int)1e9+;

const int N = 1e5 + ;

int a[N];

int b[N];

int sta[N];

int cnt[N];

LL solve(int l, int r){

    LL ret = ;

    int top = ;

    sta[] = l - ;

    for(int i = l; i < r; ++i){

        while(top && b[sta[top]] < b[i]){

            ret +=  1ll * cnt[top] *  b[sta[top]] * (i-sta[top]);

            top--;

        }

        sta[++top] = i;

        cnt[top] = i - sta[top-];

    }

    while(top){

        ret += 1ll * cnt[top] * b[sta[top]] * (r - sta[top]);

        top--;

    }

    return ret;

}

int main(){

    int n, q;

    scanf("%d%d", &n, &q);

    for(int i = ; i <= n; ++i)

        scanf("%d", &a[i]);

    for(int i = ; i < n; ++i)

        b[i] = abs(a[i+] - a[i]);

    int l, r;

    for(int i = ; i <= q; ++i){

        scanf("%d%d", &l, &r);

        printf("%lld\n", solve(l, r));

    }

    return ;

}

巴特西

CodeForces 601B Lipshitz Sequence

最新文章

热门文章