[AH2017/HNOI2017]影魔（主席树+单调栈）

设\(l[i]\)为i左边第一个比i大的数的下标。\(r[i]\)为i右边第一个比i大的数的下标。
我们把\(p1,p2\)分开考虑。
当产生贡献为\(p1\)时\(i\)和\(j\)一定满足，分别为\(l[x],r[x]\)枚举每一个值为\(i\)，\(j\)之间最大值可证。
党产生贡献为\(p2\)时\(i\)和\(j\)满足分别为\(l[x],[x+1,r[x]-1]\)或\([l[x]+1,x-1],r[x]\)，此时\(a[x]\)为\(i\)，\(j\)之间最大值，\(i\)，\(j\)一个比\(a[x]\)大，一个比\(a[x]\)小。
然后就把问题转化为二维数点问题。产生贡献的点对对应坐标系中的一个点（为了避免重复计数如\((r[x],l[x])\)和\((l[x],r[x])\)，可以把小的作为横坐标，大的作为纵坐标）。然后我们每一次询问就是横坐标在\([l,r]\)之间，纵坐标在\([l,r]\)之间的权值和。
然后就可以用主席树做了。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
#define int long long
const int N=201000; 
struct line{ int l,r,w; }; 
vector<line> vec[N]; 
int tot,root[N],lazy[N*70],ch[N*70][2],sum[N*70]; 
int n,m,p1,p2,a[N],stack[N],top,l[N],r[N]; 
void add(int l,int r,int L,int R,int w,int pre,int &now){ 
    now=++tot;
    ch[now][0]=ch[pre][0]; 
    ch[now][1]=ch[pre][1]; 
    lazy[now]=lazy[pre]; 
    sum[now]=sum[pre]+(R-L+1)*w; 
    if(l==L&&r==R){ 
        lazy[now]+=w; 
        return; 
    } 
    int mid=(l+r)>>1; 
    if(L>mid)add(mid+1,r,L,R,w,ch[pre][1],ch[now][1]); 
    else if(R<=mid)add(l,mid,L,R,w,ch[pre][0],ch[now][0]); 
    else{ 
        add(l,mid,L,mid,w,ch[pre][0],ch[now][0]); 
        add(mid+1,r,mid+1,R,w,ch[pre][1],ch[now][1]); 
    } 
} 
int check(int l,int r,int L,int R,int pre,int now){ 
    if(l==L&&r==R)return sum[now]-sum[pre]; 
    int mid=(l+r)>>1; 
    if(L>mid)return (lazy[now]-lazy[pre])*(R-L+1)+check(mid+1,r,L,R,ch[pre][1],ch[now][1]);
    else if(R<=mid)return (lazy[now]-lazy[pre])*(R-L+1)+check(l,mid,L,R,ch[pre][0],ch[now][0]); 
    else return (lazy[now]-lazy[pre])*(R-L+1) 
    +check(l,mid,L,mid,ch[pre][0],ch[now][0]) 
    +check(mid+1,r,mid+1,R,ch[pre][1],ch[now][1]);
} 
int read(){ 
    int sum=0,f=1;char ch=getchar(); 
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 
    while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();} 
    return sum*f; 
} 
signed main(){ 
    n=read(),m=read(),p1=read(),p2=read(); 
    for(int i=1;i<=n;i++)a[i]=read(); 
    for(int i=1;i<=n;i++){ 
        while(a[i]>a[stack[top]]&&top)r[stack[top--]]=i; 
        stack[++top]=i; 
    } 
    while(top)r[stack[top--]]=n+1; 
    for(int i=n;i>=1;i--){ 
        while(a[i]>a[stack[top]]&&top)l[stack[top--]]=i; 
        stack[++top]=i; 
    } 
    while(top)l[stack[top--]]=0; 
    for(int i=1;i<=n;i++){
        line x; 
        if(i!=n&&i+1<=r[i]-1){ 
            x.l=i+1;x.r=r[i]-1;x.w=p2; 
            vec[l[i]].push_back(x); 
        } 
        if(l[i]+1<=i-1&&i!=1){ 
            x.l=l[i]+1;x.r=i-1;x.w=p2; 
            vec[r[i]].push_back(x); 
        } 
        x.l=i;x.r=i;x.w=p1; 
        vec[l[i]].push_back(x);
        vec[r[i]].push_back(x);
    } 
    for(int i=1;i<=n;i++){ 
        root[i]=root[i-1]; 
        for(int j=0;j<vec[i].size();j++)
            add(1,n,vec[i][j].l,vec[i][j].r,vec[i][j].w,root[i],root[i]);
    } 
    for(int i=1;i<=m;i++){ 
        int l=read(),r=read(); 
        printf("%lld\n",check(1,n,l,r,root[l-1],root[r])); 
    } 
    return 0; 
}

[AH2017/HNOI2017]影魔（主席树+单调栈）

原文：https://www.cnblogs.com/Xu-daxia/p/10165769.html