Description

影魔,奈文摩尔,据说有着一个诗人的灵魂。事实上,他吞噬的诗人灵魂早已成千上万。千百年来,他收集了各式各样

的灵魂,包括诗人、牧师、帝王、乞丐、奴隶、罪人,当然,还有英雄。每一个灵魂,都有着自己的战斗力,而影魔,靠

这些战斗力提升自己的攻击。奈文摩尔有 n 个灵魂,他们在影魔宽广的体内可以排成一排,从左至右标号 1 到 n。

第 i个灵魂的战斗力为 k[i],灵魂们以点对的形式为影魔提供攻击力,对于灵魂对 i,j(i<j)来说,若不存在 k[s](i

<s<j)大于 k[i]或者 k[j],则会为影魔提供 p1 的攻击力(可理解为:当 j=i+1 时,因为不存在满足 i<s<j 的 s,从

而 k[s]不存在,这时提供 p1 的攻击力;当 j>i+1 时,若max{k[s]|i<s<j}<=min{k[i],k[j]} , 则 提 供 p1 的 攻

 击 力 ); 另 一 种 情 况 , 令 c 为k[i+1],k[i+2],k[i+3]......k[j-1]的最大值,若 c 满足:k[i]<c<k[j],或

者 k[j]<c<k[i],则会为影魔提供 p2 的攻击力,当这样的 c 不存在时,自然不会提供这 p2 的攻击力;其他情况的

点对,均不会为影魔提供攻击力。影魔的挚友噬魂鬼在一天造访影魔体内时被这些灵魂吸引住了,他想知道,对于任

意一段区间[a,b],1<=a<b<=n,位于这些区间中的灵魂对会为影魔提供多少攻击力,即考虑 所有满足a<=i<j<=b 的灵

魂对 i,j 提供的攻击力之和。顺带一提,灵魂的战斗力组成一个 1 到 n 的排列:k[1],k[2],...,k[n]。

Solution

单调栈可求出位置i左边第一个比它大的位置L[i]和右边第一个比它大的位置R[i]

可以知道点对(L[i],R[i])提供p1的攻击力

L[i]+1~i-1与R[i]组成的点对提供p2的攻击力

L[i]与i+1~R[i]-1组成的点对提供p2的攻击力

于是用主席树维护，新加入一个点作为左端点或右端点时的攻击力

还要加上相邻的每两个点对的攻击力p1

WA调了好久，还怀疑是有些地方没开LL，后来发现是数组越界了…开大一点就好了//话说为什么不是RE

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define MAXN 200005#define INF 0x3f3f3f3ftypedef long long LL;using namespace std;int n,m,p1,p2,k[MAXN];int s[MAXN],top,L[MAXN],R[MAXN],head1[MAXN],cnt1=0,head2[MAXN],cnt2=0;struct Node{    int l,r,w,next;}x[MAXN*4],y[MAXN*4];void add1(int u,int l,int r,int w){    x[++cnt1].next=head1[u];    head1[u]=cnt1;    x[cnt1].l=l,x[cnt1].r=r,x[cnt1].w=w;}void add2(int u,int l,int r,int w){    y[++cnt2].next=head2[u];    head2[u]=cnt2;    y[cnt2].l=l,y[cnt2].r=r,y[cnt2].w=w;}struct fotile_tree{    int rt[MAXN],ls[MAXN*50],rs[MAXN*50],tot;    LL atk[MAXN*50],val[MAXN*50];    fotile_tree(){tot=0;}    void build(int &idx,int l,int r)    {        ++tot,idx=tot;        atk[idx]=val[idx]=0;        if(l==r)return;        int mid=(l+r)>>1;        build(ls[idx],l,mid);        build(rs[idx],mid+1,r);    }    void insert(int &idx,int last,int l,int r,int x,int y,int v)    {        if(x>y)return;        ++tot,idx=tot;        atk[idx]=atk[last]+1LL*(y-x+1)*v,val[idx]=val[last];        ls[idx]=ls[last],rs[idx]=rs[last];        if(l==x&&r==y){val[idx]+=v;return;}        int mid=(l+r)>>1;        if(y<=mid)insert(ls[idx],ls[last],l,mid,x,y,v);        else if(x>mid)insert(rs[idx],rs[last],mid+1,r,x,y,v);        else {insert(ls[idx],ls[last],l,mid,x,mid,v);insert(rs[idx],rs[last],mid+1,r,mid+1,y,v);}    }    LL query(int s,int t,int l,int r,int x,int y)    {        if(x>y)return 0;         if(l==x&&r==y)return atk[t]-atk[s];        int mid=(l+r)>>1;        LL calc=1LL*(y-x+1)*(val[t]-val[s]);        if(y<=mid){
   return calc+query(ls[s],ls[t],l,mid,x,y);}        else if(x>mid)return calc+query(rs[s],rs[t],mid+1,r,x,y);        else return calc+query(ls[s],ls[t],l,mid,x,mid)+query(rs[s],rs[t],mid+1,r,mid+1,y);    }}trL,trR;int read(){    int x=0,f=1;char c=getchar();    while(c<'0'||c>'9'){        if(c=='-')f=-1;c=getchar();    }    while(c>='0'&&c<='9'){        x=x*10+c-'0';c=getchar();    }    return x*f;}int main(){    memset(head1,-1,sizeof(head1));    memset(head2,-1,sizeof(head2));    n=read(),m=read(),p1=read(),p2=read();    for(int i=1;i<=n;i++)k[i]=read();    top=0;    for(int i=1;i<=n;i++)    {        while(top&&k[s[top]]
          
           0;i--) { while(top&&k[s[top]]
           
            0;i--) { trR.rt[i]=trR.rt[i+1]; for(int j=head2[i];~j;j=y[j].next) trR.insert(trR.rt[i],trR.rt[i],1,n,max(1,y[j].l),min(n,y[j].r),y[j].w); } for(int i=1;i<=m;i++) { int a=read(),b=read(); if(a>b)swap(a,b); LL ans=1LL*(b-a)*p1; ans+=trL.query(trL.rt[a-1],trL.rt[b],1,n,a,b); ans+=trR.query(trR.rt[b+1],trR.rt[a],1,n,a,b); printf("%lld\n",ans); } return 0;}