HDU - 5306： Gorgeous Sequence （势能线段树）

There is a sequence aa of length nn. We use aiai to denote the ii-th element in this sequence. You should do the following three types of operations to this sequence.

0 x y t0 x y t: For every x≤i≤yx≤i≤y, we use min(ai,t)min(ai,t) to replace the original aiai's value.
1 x y1 x y: Print the maximum value of aiai that x≤i≤yx≤i≤y.
2 x y2 x y: Print the sum of aiai that x≤i≤yx≤i≤y.

InputThe first line of the input is a single integer TT, indicating the number of testcases.

The first line contains two integers nn and mm denoting the length of the sequence and the number of operations.

The second line contains nn separated integers a1,…,ana1,…,an (∀1≤i≤n,0≤ai<231∀1≤i≤n,0≤ai<231).

Each of the following mm lines represents one operation (1≤x≤y≤n,0≤t<2311≤x≤y≤n,0≤t<231).

It is guaranteed that T=100T=100, ∑n≤1000000, ∑m≤1000000∑n≤1000000, ∑m≤1000000.OutputFor every operation of type 11 or 22, print one line containing the answer to the corresponding query.
Sample Input

Sample Output

题意：三种操作，0区间min操作；1区间求max；2区间求和。

思路：segments tres beats模板题。因为都是区间操作，所以有很多相同的值，我们记录每个区间的最大值，最大值的数量，以及第二大值。然后就可以搞了，不用lazy，下推的时候如果mx[Now]比儿子还小，那么久自然的下推即可。

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn=;

int mx[maxn<<],mc[maxn<<],se[maxn<<];

ll sum[maxn<<];

void pushdown(int Now)

{

    if(mx[Now]<mx[Now<<]){

        sum[Now<<]-=(ll)(mx[Now<<]-mx[Now])*mc[Now<<];

        mx[Now<<]=mx[Now];

    }

    if(mx[Now]<mx[Now<<|]){

        sum[Now<<|]-=(ll)(mx[Now<<|]-mx[Now])*mc[Now<<|];

        mx[Now<<|]=mx[Now];

    }

}

void pushup(int Now)

{

    sum[Now]=sum[Now<<]+sum[Now<<|];

    mx[Now]=max(mx[Now<<],mx[Now<<|]);

    if(mx[Now<<]==mx[Now<<|]){

        mc[Now]=mc[Now<<]+mc[Now<<|];

        se[Now]=max(se[Now<<],se[Now<<|]);

    }

    else {

        if(mx[Now<<]>mx[Now<<|]){

            mc[Now]=mc[Now<<];

            se[Now]=max(mx[Now<<|],se[Now<<]);

        }

        else {

            mc[Now]=mc[Now<<|];

            se[Now]=max(mx[Now<<],se[Now<<|]);

        }

    }

}

void build(int Now,int L,int R)

{

    if(L==R){

        scanf("%d",&mx[Now]);

        sum[Now]=mx[Now]; se[Now]=;

        mc[Now]=;  return ;

    }

    int Mid=(L+R)>>;

    build(Now<<,L,Mid); build(Now<<|,Mid+,R);

    pushup(Now);

}

ll querysum(int Now,int L,int R,int l,int r){

    if(l<=L&&r>=R) return sum[Now];

    int Mid=(L+R)>>; ll res=;

    pushdown(Now);

    if(l<=Mid) res+=querysum(Now<<,L,Mid,l,r);

    if(r>Mid) res+=querysum(Now<<|,Mid+,R,l,r);

    return res;

}

int querymax(int Now,int L,int R,int l,int r){

    if(l<=L&&r>=R) return mx[Now];

    int Mid=(L+R)>>,res=-;

    pushdown(Now);

    if(l<=Mid) res=max(res,querymax(Now<<,L,Mid,l,r));

    if(r>Mid) res=max(res,querymax(Now<<|,Mid+,R,l,r));

    return res;

}

void update(int Now,int L,int R,int l,int r,int x)

{

    if(mx[Now]<=x) return ;

    if(l<=L&&r>=R){

        if(se[Now]<x){

            sum[Now]-=(ll)mc[Now]*(mx[Now]-x);

            mx[Now]=x;

            return ;

        }

    }

    int Mid=(L+R)>>;

    pushdown(Now);

    if(l<=Mid) update(Now<<,L,Mid,l,r,x);

    if(r>Mid) update(Now<<|,Mid+,R,l,r,x);

    pushup(Now);

}

int main()

{

    int T,N,M,L,R,opt,x;

    scanf("%d",&T);

    while(T--){

        scanf("%d%d",&N,&M);

        build(,,N);

        while(M--){

            scanf("%d%d%d",&opt,&L,&R);

            if(opt==) printf("%d\n",querymax(,,N,L,R));

            else if(opt==) printf("%lld\n",querysum(,,N,L,R));

            else {

                scanf("%d",&x);

                update(,,N,L,R,x);

            }

        }

    }

    return ;

}

巴特西

HDU - 5306： Gorgeous Sequence （势能线段树）

最新文章

热门文章