HDU 5306 吉司机线段树

思路：

后面nlogn的部分是伪证...

大家可以构造数据证明是这是nlog^2n的啊~

吉老司机翻车了

//By SiriusRen

#include <cstdio>

#include <algorithm>

using namespace std;

const int N=;

int cases,n,m,op,xx,yy,zz;

typedef long long ll;

struct SegTree{int max1,max2,maxnum,lazy;ll sum;}tr[N*];

void push_up(int pos){

    tr[pos].max2=;int lson=pos<<,rson=pos<<|;

    tr[pos].max1=max(tr[lson].max1,tr[rson].max1);

    if(tr[lson].max1==tr[rson].max1)

        tr[pos].maxnum=tr[lson].maxnum+tr[rson].maxnum,

        tr[pos].max1=tr[lson].max1,

        tr[pos].max2=max(tr[lson].max2,tr[rson].max2);

    else{

        tr[lson].max1>tr[rson].max1?tr[pos]=tr[lson]:tr[pos]=tr[rson];

        tr[pos].max2=max(tr[lson].max2,tr[rson].max2);

        if(tr[pos].max1==tr[lson].max1)tr[pos].max2=max(tr[pos].max2,tr[rson].max1);

        else tr[pos].max2=max(tr[pos].max2,tr[lson].max1);

    }tr[pos].sum=tr[lson].sum+tr[rson].sum;

}

void change(int pos,int wei){

    tr[pos].sum-=(1ll*tr[pos].max1-wei)*tr[pos].maxnum;

    tr[pos].max1=tr[pos].lazy=wei;

}

void push_down(int pos){

    int lson=pos<<,rson=pos<<|;

    if(tr[lson].max1>tr[pos].lazy)change(lson,tr[pos].lazy),tr[lson].lazy=tr[pos].lazy;

    if(tr[rson].max1>tr[pos].lazy)change(rson,tr[pos].lazy),tr[rson].lazy=tr[pos].lazy;

    tr[pos].lazy=-;

}

void build(int l,int r,int pos){

    tr[pos].lazy=-,tr[pos].max2=;

    if(l==r){scanf("%d",&tr[pos].max1),tr[pos].sum=tr[pos].max1,tr[pos].maxnum=;return;}

    int mid=(l+r)>>,lson=pos<<,rson=pos<<|;

    build(l,mid,lson),build(mid+,r,rson),push_up(pos);

}

void insert(int l,int r,int pos,int L,int R,int wei){

    if(~tr[pos].lazy)push_down(pos);

    int mid=(l+r)>>,lson=pos<<,rson=pos<<|;

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

        if(wei>=tr[pos].max1)return;

        else if(wei<tr[pos].max1&&wei>tr[pos].max2){change(pos,wei);return;}

        else insert(l,mid,lson,L,R,wei),insert(mid+,r,rson,L,R,wei);

    }

    if(mid<L)insert(mid+,r,rson,L,R,wei);

    else if(mid>=R)insert(l,mid,lson,L,R,wei);

    else insert(l,mid,lson,L,R,wei),insert(mid+,r,rson,L,R,wei);

    push_up(pos);

}

ll query_sum(int l,int r,int pos,int L,int R){

    if(~tr[pos].lazy)push_down(pos);

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

    int mid=(l+r)>>,lson=pos<<,rson=pos<<|;

    if(mid<L)return query_sum(mid+,r,rson,L,R);

    else if(mid>=R)return query_sum(l,mid,lson,L,R);

    else return query_sum(l,mid,lson,L,R)+query_sum(mid+,r,rson,L,R);

}

int query_max(int l,int r,int pos,int L,int R){

    if(~tr[pos].lazy)push_down(pos);

    if(l>=L&&r<=R)return tr[pos].max1;

    int mid=(l+r)>>,lson=pos<<,rson=pos<<|;

    if(mid<L)return query_max(mid+,r,rson,L,R);

    else if(mid>=R)return query_max(l,mid,lson,L,R);

    else return max(query_max(l,mid,lson,L,R),query_max(mid+,r,rson,L,R));

}

int read(){

    char p=getchar();int x=;

    while(p<''||p>'')p=getchar();

    while(p>=''&&p<='')x=x*+p-'',p=getchar();

    return x;

}

signed main(){

    scanf("%d",&cases);

    while(cases--){

        n=read(),m=read(),build(,n,);

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

            op=read(),xx=read(),yy=read();

            if(!op)zz=read(),insert(,n,,xx,yy,zz);

            else if(op==)printf("%d\n",query_max(,n,,xx,yy));

            else printf("%lld\n",query_sum(,n,,xx,yy));

        }

    }

}