题目

[AH2017/HNOI2017]影魔：https://www.luogu.com.cn/problem/P3722

做法

做法1（口胡）

这个做法估计会T

考虑每个数字连向后面第一个比他大的树，对一个区间建一颗树，对于 $i<j<k,a_i<a_j<a_k$ 的询问，即为树上每个点 $dep-2$ 之和，然后其余类似，用莫队维护，时间复杂度：$O(n\sqrt{n})$，常数和码量都巨大，于是没有打，膜了题解。

当然，至于为什么为 $dep-2$ 之和，因为我们默认 $i<j<k,a_i<a_j<a_k$ 是由 $(i,k)$ 区间中最大的数字来找到这个区间。

做法2

以下摘自此博客：https://www.luogu.com.cn/blog/AAAALL12138/solution-p3722

这个题可以采取离线处理的方式.先处理出每个点 $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$ 的贡献。③

所以我们离线排序处理好。

对于①情况，我们在扫到 $R[i]$ 时，更新点 $L[i]$ 的贡献。

对于②情况，我们在扫到 $R[i]$ 时，更新区间 $L[i]+1$ 到 $i-1$ 的贡献。

对于③情况，我们在扫到 $L[i]$ 时，更新区间 $i+1$ 到 $R[i]-1$ 的贡献。

我们对于每个询问 $[l,r]$，在扫到 $l-1$ 时，我们记录此时区间 $l$ 到 $r$ 的每个点的贡献和为 sum1，然后当我们扫到 $r$ 时，再次记录此时的区间 $l$ 到 $r$ 的每个点的贡献和为 sum2，显然答案就是 sum2 - sum1 了。

好，至于为什么吗，我来解释一下，为什么 $p1$ 的贡献只用 $L[i],R[i]$ 来统计呢？（当然，这也可以证明 $p1$ 区间个数实在 $O(n)$ 级别的）

  1. 为什么每个区间必定会被统计且只会被统计一次：首先，考虑这个 $(l,r)$ 是个合法的 $p1$ 区间，那么对于 $(l,r)$ 范围中最大的数字 $mid$，其 $L[i]=l,R[i]=r$，且对于这个区间其他数字，绝对不可能 $L[i]=l,R[i]=r$，因为 $mid$ 比他们都打，卡在中间挡住了他们。
  2. 为什么 $(L[i],R[i])$ 一定构成一个合法区间：这不废话？

对于 $p2$ 的 $a_ia_{j}>a_{k}$。

当然，别忘了 $(i,i+1)$ 固定有 $p1$ 的贡献。

时间复杂度：$O(n \log n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define  N  210000
#define  NN  410000
#define  NNN  610000
using  namespace  std;
typedef  long  long  LL;
struct  node
{
	int  l,r,d;
	LL  lazy,c;
}tr[NN];int  len,last[N];
inline  void  pushlazy(int  x,LL  k){tr[x].lazy+=k;tr[x].c+=k*tr[x].d;}
inline  void  updata(int  x){tr[x].c=tr[tr[x].l].c+tr[tr[x].r].c;}
inline  void  downdata(int  x)
{
	if(tr[x].lazy)
	{
		pushlazy(tr[x].l,tr[x].lazy);
		pushlazy(tr[x].r,tr[x].lazy);
		tr[x].lazy=0;
	}
}
void  bt(int  l,int  r)
{
	int  now=++len;tr[now].d=(r-l+1);
	if(l<r)
	{
		int  mid=(l+r)>>1;
		tr[now].l=len+1;bt(l,mid);
		tr[now].r=len+1;bt(mid+1,r);
	}
}
void  change(int  now,int  l,int  r,int  ll,int  rr,LL  k)
{
	if(l==ll  &&  r==rr){pushlazy(now,k);return  ;}
	int  mid=(l+r)>>1;
	downdata(now);
	if(rr<=mid)change(tr[now].l,l,mid,ll,rr,k);
	else  if(mid<ll)change(tr[now].r,mid+1,r,ll,rr,k);
	else  change(tr[now].l,l,mid,ll,mid,k),change(tr[now].r,mid+1,r,mid+1,rr,k);
	updata(now);
}
LL  findans(int  now,int  l,int  r,int  ll,int  rr)
{
	if(l==ll  &&  r==rr)return  tr[now].c;
	int  mid=(l+r)>>1;
	downdata(now);
	if(rr<=mid)return  findans(tr[now].l,l,mid,ll,rr);
	else  if(mid<ll)return  findans(tr[now].r,mid+1,r,ll,rr);
	else  return  findans(tr[now].l,l,mid,ll,mid)+findans(tr[now].r,mid+1,r,mid+1,rr);	
}
int  L[N],R[N],n,m,a[N];
LL  q1,q2;
int  sta[N],top;
struct  Query
{
	int  l,r;
	LL  *id,type;
};
struct  CHANGE
{
	int  l,r,k,id/*在访问到哪个人时会使用这个*/;
}ch[NNN];int  clen,cnow=1;
inline  bool  cmp(CHANGE  x,CHANGE  y){return  x.id<y.id;}
vector<Query> fuck[N];
LL  ans[N];
inline  void  solve(int  x/*加入第x个位置*/)
{
	while(cnow<=clen  &&  ch[cnow].id==x)
	{
		if(ch[cnow].l<=ch[cnow].r)change(1,1,n,ch[cnow].l,ch[cnow].r,ch[cnow].k);
		cnow++;
	}
	for(int  i=0;i<fuck[x].size();i++)
	{
		Query  y=fuck[x][i];
		(*y.id)+=y.type*findans(1,1,n,y.l,y.r);
	}
}
int  main()
{
	scanf("%d%d%d%d",&n,&m,&q1,&q2);
	for(int  i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int  i=1;i<=n;i++)
	{
		while(top  &&  a[sta[top]]<a[i])top--;
		L[i]=sta[top];
		sta[++top]=i;
	}
	top=0;
	for(int  i=n;i>=1;i--)
	{
		while(top  &&  a[sta[top]]<a[i])top--;
		R[i]=sta[top];
		sta[++top]=i;
	}
	for(int  i=1;i<=n;i++)
	{
		if(L[i]  &&  R[i])
		{
			ch[++clen].id=R[i];ch[clen].k=q1;ch[clen].l=L[i];ch[clen].r=L[i];
		}
		if(R[i])
		{
			ch[++clen].id=R[i];ch[clen].k=q2;ch[clen].l=L[i]+1;ch[clen].r=i-1;
		}
		if(L[i])
		{
			ch[++clen].id=L[i];ch[clen].k=q2;ch[clen].l=i+1;ch[clen].r=!R[i]?n:R[i]-1;
		}
	}
	bt(1,n);
	sort(ch+1,ch+clen+1,cmp);
	for(int  i=1;i<=m;i++)
	{
		int  l,r;scanf("%d%d",&l,&r);
		ans[i]=(r-l)*q1;
		Query  x;x.l=l;x.r=r;x.type=-1;x.id=&ans[i];
		fuck[l-1].push_back(x);
		x.type=1;x.id=&ans[i];
		fuck[r].push_back(x);
	}
	for(int  i=1;i<=n;i++)
	{
		solve(i);
	}
	for(int  i=1;i<=m;i++)printf("%lld\n",ans[i]);
	return  0;
}