hdu6521 吉司机线段树

http://acm.hdu.edu.cn/showproblem.php?pid=6521
待填
代码

#include<bits/stdc++.h>

#define ls o<<1

#define rs o<<1|1

#define ll long long

using namespace std;

const int MAXN = 5e5+5;

int Mx[MAXN<<2],Mx2[MAXN<<2],Mn[MAXN<<2],ly[MAXN<<2];

ll V[MAXN<<2];

int n,m,l,r;

void push_up(int o){

    Mx[o]=max(Mx[ls],Mx[rs]);

    Mx2[o]=0;

    if(Mx[ls]==Mx[rs]){

        Mn[o]=Mn[ls]+Mn[rs];

        Mx2[o]=max(Mx2[ls],Mx2[rs]);

    }else{

        if(Mx[ls]>Mx[rs]){

            Mx[o]=Mx[ls];Mn[o]=Mn[ls];V[o]=V[ls];Mx2[o]=Mx2[ls];ly[o]=ly[ls];

        }else{

            Mx[o]=Mx[rs];Mn[o]=Mn[rs];V[o]=V[rs];Mx2[o]=Mx2[rs];ly[o]=ly[rs];

        }

        Mx2[o]=max(Mx2[ls],Mx2[rs]);

        if(Mx[o]==Mx[ls])Mx2[o]=max(Mx2[o],Mx[rs]);

        else Mx2[o]=max(Mx2[o],Mx[ls]);

    }

    V[o]=V[ls]+V[rs];

}

void ch(int o,int x){

    V[o]-=(1ll*Mx[o]-x)*Mn[o];

    Mx[o]=ly[o]=x;

}

void push_down(int o){

    if(Mx[ls]>ly[o]){ch(ls,ly[o]);ly[ls]=ly[o];}

    if(Mx[rs]>ly[o]){ch(rs,ly[o]);ly[rs]=ly[o];}

    ly[o]=-1;

}

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

    ly[o]=-1;Mx2[o]=0;

    if(l==r){V[o]=Mx[o]=l;Mn[o]=1;return;}

    int mid=(l+r)/2;

    build(ls,l,mid);

    build(rs,mid+1,r);

    push_up(o);

}

void ud(int o,int l,int r,int L,int R,int x){

    if(~ly[o])push_down(o);

    int mid=(l+r)/2;

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

        if(x>=Mx[o])return;

        else if(x>Mx2[o]){ch(o,x);return;}

        else{

            ud(ls,l,mid,L,R,x);ud(rs,mid+1,r,L,R,x);

            //return;  //没有return;

        }

    }

    if(L<=mid)ud(ls,l,mid,L,R,x);

    if(R>mid)ud(rs,mid+1,r,L,R,x);

    push_up(o);

}

ll qSum(int o,int l,int r,int L,int R){

    if(~ly[o])push_down(o);

    if(L<=l&&r<=R)return V[o];

    int mid=(l+r)/2;

    ll ans=0;

    if(L<=mid)ans+=qSum(ls,l,mid,L,R);

    if(R>mid)ans+=qSum(rs,mid+1,r,L,R);

    push_up(o);

    return ans;

}

int main(){

    while(~scanf("%d%d",&n,&m)){

        build(1,1,n);

        while(m--){

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

            ll tp=qSum(1,1,n,l,r);

            ud(1,1,n,l,r,l);

            printf("%lld\n",tp-qSum(1,1,n,l,r));

        }

    }

}
巴特西

hdu6521 吉司机线段树

代码

最新文章

热门文章
