[HNOI/AHOI2017]影魔

题目大意：

有一排\(n(n\le2\times10^5)\)个数\(k_{1\sim n}\)。对于点对\((i,j)\)，若不存在\(k_s(i<s<j)\)大于\(k_i\)或\(k_j\)， 则对答案造成\(p_1\)的贡献；若\(c=\max_{s\in(i,j)}\{k_s\}\)满足\(k_i<c<k_j\)或\(k_j<c<k_i\)则对答案造成\(p_2\)的贡献。\(m(m\le2\times10^5)\)次询问，每次询问区间\([l,r]\)内所有点对对答案贡献之和。其中\(k_i\)为\(1\sim n\)的全排列。

思路：

首先预处理出对于每个点\(i\)，其左侧第一个权值大于它的点\(left[i]\)和其右侧第一个权值大于它的点\(right[i]\)。显然这个点\(i\)对答案的贡献有\(3\)种情况：

1. 对于点对\((left[i],right[i])\)，贡献为\(p_1\)；
2. 对于所有点对\((l\in(left[i],i),right[i])\)，贡献为\(p_2\)；
3. 对于所有点对\((left[i],r\in(i,right[i]))\)，贡献为\(p_2\)。

我们可以离线处理所有询问。将询问和贡献分别排序，用树状数组维护答案即可。

源代码：

#include
    
     #include
     
      #include
      
       typedef long long int64;inline int getint() {    register char ch;    while(!isdigit(ch=getchar()));    register int x=ch^'0';    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');    return x;}const int N=2e5+2,M=2e5;int64 ans[M];int n,m,p1,p2,w[N],left[N],right[N];struct Query {    int p,id,sgn,l,r;    bool operator < (const Query &rhs) const {        return p
       
        >1;            if(x<=mid) modify(p _left,b,mid,x,v);            if(x>mid) modify(p _right,mid+1,e,x,v);            push_up(p);        }        int query(const int &p,const int &b,const int &e,const int &x) const {            if(b==e) return b;            const int mid=(b+e)>>1;            if(max[p _right]>x) return query(p _right,mid+1,e,x);            return query(p _left,b,mid,x);        }    #undef _left    #undef _right};SegmentTree1 st1;class SegmentTree2 {    #define _left <<1    #define _right <<1|1    private:        int max[N<<2];        void push_up(const int &p) {            max[p]=std::max(max[p _left],max[p _right]);        }    public:        void modify(const int &p,const int &b,const int &e,const int &x,const int &v) {            if(b==e) {                max[p]=v;                return;            }            const int mid=(b+e)>>1;            if(x<=mid) modify(p _left,b,mid,x,v);            if(x>mid) modify(p _right,mid+1,e,x,v);            push_up(p);        }        int query(const int &p,const int &b,const int &e,const int &x) const {            if(b==e) return b;            const int mid=(b+e)>>1;            if(max[p _left]>x) return query(p _left,b,mid,x);            return query(p _right,mid+1,e,x);        }    #undef _left    #undef _right};SegmentTree2 st2;int main() {    n=getint(),m=getint(),p1=getint(),p2=getint();    for(register int i=1;i<=n;i++) w[i]=getint();    for(register int i=1,pos=0;i<=n;i++) {        left[i]=w[i]
        
         w[pos]) pos=i;        st1.modify(1,1,n,i,w[i]);    }    for(register int i=n,pos=n+1;i>=1;i--) {        right[i]=w[i]
         
          w[pos]) pos=i; st2.modify(1,1,n,i,w[i]); } for(register int i=0;i