来自FallDream的博客，未经允许，请勿转载，谢谢。

---

 

影魔,奈文摩尔,据说有着一个诗人的灵魂。事实上,他吞噬的诗人灵魂早已成千上万。千百年来,他收集了各式各样的灵魂,包括诗人、牧师、帝王、乞丐、奴隶、罪人,当然,还有英雄。每一个灵魂,都有着自己的战斗力,而影魔,靠这些战斗力提升自己的攻击。奈文摩尔有 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]。

n,m<=2*10^5

 

题面剧毒...看错了几次

考虑枚举中间那一段的最值是啥，那么对于每个枚举的值，显然需要找到的是左右第一个大于它的。这个可以单调栈实现。

然后假设左右两边第一个大于它的是l,r 那么

l和r贡献p1

[l+1,i-1]和r贡献p2

l和[i+1,r-1]贡献p3

另外 对于每个i<n  i和i+1有贡献p1

查询可以看作是查矩形  修改是改线段 那么主席树维护即可。

复杂度nlogn

#include
      
       #include
       
        #include
        
         #define MN 200000#define ll long long#define getchar() (*S++)char B[1<<26],*S=B;using namespace std;inline int read(){    int x = 0; char ch = getchar();    while(ch < '0' || ch > '9')ch = getchar();    while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}    return x;}int a[MN+5],n,m,p1,p2,cnt=0,L[MN+5],R[MN+5],rt[MN+5];struct Tree{
    int l,r,x;ll val;}T[MN*80];struct data{
    int l,r,x;};vector
          v[MN+5];struct MyQue{    int q[MN+5],top;    void clear(int x){q[top=0]=x;}    int ins(int i)    {        while(top&&a[q[top]]
          
           >1;ll sum=1LL*(r-l+1)*T[x].x;    if(r<=mid) return sum+Query(T[x].l,l,r,lt,mid);    else if(l>mid) return sum+Query(T[x].r,l,r,mid+1,rt);    else return sum+Query(T[x].l,l,mid,lt,mid)+Query(T[x].r,mid+1,r,mid+1,rt);}void Modify(int x,int l,int r,int lt,int rt,int ad){    T[x].val+=1LL*(r-l+1)*ad;    if(l==lt&&r==rt)    {        T[x].x+=ad;        return;    }    int mid=lt+rt>>1;    if(r<=mid) Modify(T[x].l=NewNode(T[x].l),l,r,lt,mid,ad);    else if(l>mid) Modify(T[x].r=NewNode(T[x].r),l,r,mid+1,rt,ad);    else Modify(T[x].l=NewNode(T[x].l),l,mid,lt,mid,ad),         Modify(T[x].r=NewNode(T[x].r),mid+1,r,mid+1,rt,ad);}int main(){    fread(B,1,1<<26,stdin);    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) L[i]=Q.ins(i);    Q.clear(n+1);    for(int i=n;i;--i) R[i]=Q.ins(i);    for(int i=1;i<=n;++i)    {        if(i
           
            =L[i]+2) v[R[i]].push_back((data){L[i]+1,i-1,p2}); } for(int i=1;i<=n;++i) { rt[i]=rt[i-1]; for(int j=0;j