BZOJ 4826: [Hnoi2017]影魔 单调栈+可持久化线段树

#include <cstring> 
#include <cstdio> 
#include <stack>  
#include <string> 
#include <vector>  
#include <algorithm>  
#define N 200005 
#define ll long long      
using namespace std;   
void setIO(string s) {
    string in=s+".in"; 
    string out=s+".out"; 
    freopen(in.c_str(),"r",stdin);   
    // freopen(out.c_str(),"w",stdout);   
}              
int n,m,tp,edges;    
int p1,p2;    
int val[N];         
int sta[N]; 
int L[N],R[N];                
int hd[N];   
int tot;   
int rtl[N]; 
int rtr[N];   
struct Edge {          
    int x; 
    int l; 
    int r;  
    int v;   
    int nex; 
}e[N*3];   
struct node {
    int ls; 
    int rs;  
    ll tag;  
    ll sum;  
}t[N*80];   
void add(int u,int l,int r,int v) {
    e[++edges].nex=hd[u];  
    hd[u]=edges;   
    e[edges].l=l; 
    e[edges].r=r;  
    e[edges].x=u; 
    e[edges].v=v;  
}
int newnode() {
    return ++tot; 
}      
int update(int x,int l,int r,int L,int R,int v) {   
    if(L>R) {
        return x;   
    }
    int now=newnode();              
    t[now]=t[x];                                                      
    t[now].sum+=(ll)(min(r,R)-max(l,L)+1)*v; 
    if(l>=L&&r<=R) {            
        t[now].tag+=v;                
        return now;  
    }
    int mid=(l+r)>>1;   
    if(L<=mid) {
        t[now].ls=update(t[x].ls,l,mid,L,R,v); 
    }
    if(R>mid)  {
        t[now].rs=update(t[x].rs,mid+1,r,L,R,v);   
    }    
    return now;        
}
ll query(int x,int l,int r,int L,int R) {           
    if(!x) {
        return 0;  
    }
    if(l>=L&&r<=R) {
        return t[x].sum; 
    }
    int mid=(l+r)>>1;    
    ll re=(ll)t[x].tag*(min(r,R)-max(l,L)+1);                                     
    if(L<=mid)  {
        re+=query(t[x].ls,l,mid,L,R); 
    }
    if(R>mid) {
        re+=query(t[x].rs,mid+1,r,L,R); 
    }
    return re;  
}       
int main() { 
    // setIO("input");   
    int i,j;                 
    scanf("%d%d%d%d",&n,&m,&p1,&p2);    
    for(i=1;i<=n;++i) {
        scanf("%d",&val[i]); 
    }             
    for(i=1;i<=n;++i) {
        while(tp&&val[sta[tp]]<val[i]) {
            --tp;   
        }
        L[i]=sta[tp];   
        sta[++tp]=i;  
    }      
    sta[tp=0]=n+1;   
    for(i=n;i>=1;--i) {
        while(tp&&val[sta[tp]]<val[i]) {
            --tp;  
        }
        R[i]=sta[tp];  
        sta[++tp]=i; 
    }              
    for(i=1;i<=n;++i) {    
        add(L[i],R[i],R[i],p1);                    
        add(L[i],i+1,R[i]-1,p2);   
        add(R[i],L[i]+1,i-1,p2);  
    }           
    // 向右   
    for(i=1;i<=n;++i) {
        rtl[i]=rtl[i-1];   
        for(j=hd[i];j;j=e[j].nex) {
            if(e[j].l>i) {  
                rtl[i]=update(rtl[i],1,n,max(1,e[j].l),min(n,e[j].r),e[j].v);                
            }
        }
        if(i!=n) {  
            rtl[i]=update(rtl[i],1,n,i+1,i+1,p1);  
        }
    }
    for(i=n;i>=1;--i) {
        rtr[i]=rtr[i+1];   
        for(j=hd[i];j;j=e[j].nex) {
            if(e[j].r<i) {    
                rtr[i]=update(rtr[i],1,n,max(1,e[j].l),min(n,e[j].r),e[j].v);   
            }
        }
    }        
    while(m--) {
        int x,y; 
        scanf("%d%d",&x,&y);    
        ll ans=0ll;   
        ans+=query(rtl[y],1,n,x,y); 
        ans-=query(rtl[x-1],1,n,x,y); 
        ans+=query(rtr[x],1,n,x,y); 
        ans-=query(rtr[y+1],1,n,x,y);    
        printf("%lld\n",ans);   
    }    
    return 0; 
}