标签：线段树

题解：

　　首先对于题目的条件进行分析，p1的条件是一个区间的两个端点必须是这一个区间的最大与次大值。p2的条件是一个区间的一个端点是最大值，而另一个端点不是次大值。显然，他们都需要两个条件（对于两个端点都有要求，这样的话不太好操作）。感受一下，p1的条件更为严苛，于是我们这样考虑：

　　一个区间的一个端点是最大值（两个条件的公共部分），另一个不管，此时加上p2的贡献。

　　我们可以通过线段树求解出这一个东西。对于i，找到右边大于他的第一个数，如果没有，自然是最后一个数，但是这样不好，于是我们加一个第n+1个数为+∞。然后设ri为右边大于他的第一个数，那么[i,i+1]、[i,i+2]、......[i,ri]都符合条件，于是在线段树中对于[i+1,ri]都+=p2。对于全部询问排序，给以i为左端点的区间加上贡献，查询[i+1,R]的和。反过来再搞一遍，注意询问区间也要反过来。

　　然后我们发现题目中的对另一个端点的限制是互补的，我们的区间[i,ri]满足p1，而[i,i+1~ri-1]满足p2。因为只有一个满足p1，而且一个i对应一个ri，于是我们在ri处+p1-p2-p2即可，完美解决这一个问题。

小结：此题关键在于两个条件有一半相同，而另一半互补，所以可以不管互补的那一半到时候再考虑。

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #define ls k*2  6 #define rs (k*2+1)  7 #define LL long long  8 using namespace std;  9 const int MAXN=210000; 10 int n,m,p1,p2,tp; 11 int v[MAXN],aft[MAXN],st[MAXN]; 12 LL ans[MAXN],sum[MAXN*5],lz[MAXN*5]; 13 struct ed 14 { 15   int L,R,id; 16 }ask[MAXN]; 17 #define down()\ 18 {\ 19   sum[ls]+=lz[k]*(mid-ll+1);\ 20   sum[rs]+=lz[k]*(rr-mid);\ 21   lz[ls]+=lz[k];\ 22   lz[rs]+=lz[k];\ 23   lz[k]=0;\ 24 } 25 inline int gi() {
   int res; scanf("%d",&res); return res;} 26 bool comp(ed x,ed y){
   return x.L
         
          =1;i--) 77     { 78       while(tp && v[st[tp]]
          
           =1;i--) 85 { 86 if(aft[i]>i) 87 { 88 add(1,1,n+1,i+1,aft[i],p2); 89 add(1,1,n+1,aft[i],aft[i],p1-2*p2); 90 } 91 int p=find(i); 92 while(ask[p].L==i) 93 { 94 ans[ask[p].id]+=query(1,1,n+1,i+1,ask[p].R); 95 p++; 96 } 97 } 98 } 99 int main()100 {101 n=gi();m=gi();p1=gi();p2=gi();102 for(int i=1;i<=n;i++) v[i]=gi();103 for(int i=1;i<=m;i++) ask[i].L=gi() , ask[i].R=gi() , ask[i].id=i;104 sort(ask+1,ask+1+m,comp);105 work();106 reverse(v+1,v+1+n);107 for(int i=1;i<=m;i++)108 {109 swap(ask[i].L,ask[i].R);110 ask[i].L=n-ask[i].L+1;111 ask[i].R=n-ask[i].R+1;112 }113 sort(ask+1,ask+1+m,comp);114 work();115 for(int i=1;i<=m;i++)116 printf("%lld\n",ans[i]);117 return 0;118 }