题目链接：传送门

Description

给你一个NN的排列，对于区间[l,r][l,r]，若ll和rr为区间最大值与次大值，则对区间有p1p1的贡献；

若ll和rr中一个为最大值，一个不为次大值，则有p2p2的贡献。有mm个查询[l,r][l,r]，查询区间[l,r][l,r]内的贡献

Constraints

1≤n,m≤200000,1≤p1,p2≤10001 \le n,m \le 200000,1 \le p1,p2 \le 1000

Solution

先把每个位置它左边比它第一个大和右边比它第一个大的位置（分别记为L[i], R[i]）找出来

别人都是用的单调栈搞，但实际上直接暴力跳就可以了（见AGC005B）

复杂度能保证（证起来有点麻烦就不写了）

然后那么对于区间L[i]到R[i]有p1的贡献.

对于左端点在L[i]+1到i-1,右端点为R[i]的区间有p2的贡献.

对于左端点为L[i],右端点为i+1到R[i]-1的区间也有p2的贡献.

并且[i - 1, i]也有p1的贡献（开始没想到这一点，然后死活过不了样例）

然后我们就可以把询问离线，用扫描线+线段树去做了（剩下的都是套路。。。）

Code

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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include <bits/stdc++.h>
#define LL long long

using namespace std;

const int Maxn = 200000 + 100;

int N, M, p1, p2;
int A[Maxn];
int L[Maxn], R[Maxn];

struct Pair
{
	int x, y;
};

struct Triple
{
	int x, y, z;
};

vector <Pair> vec_query1[Maxn];
vector <Pair> vec_query2[Maxn];
vector <Triple> vec_modify[Maxn];

LL Ans[Maxn], Sum[Maxn];

struct tree
{
	LL sum, tag;
}Tree[Maxn << 2];

inline void push_up (int x)
{
	Tree[x].sum = Tree[x << 1].sum + Tree[x << 1 | 1].sum;
}

inline void push_down (int x, int l, int r)
{
	if (!Tree[x].tag) return ;
	Tree[x << 1].tag += Tree[x].tag;
	Tree[x << 1 | 1].tag += Tree[x].tag;
	LL mid = (l + r) >> 1;
	Tree[x << 1].sum += Tree[x].tag * (mid - l + 1);
	Tree[x << 1 | 1].sum += Tree[x].tag * (r - mid);
	Tree[x].tag = 0ll;
}

inline void Update (int root, int l, int r, int x, int y, int z)
{
	if (y < l || x > r) return ;
	if (x <= l && r <= y)
	{
		Tree[root].sum += 1ll * (r - l + 1) * z;
		Tree[root].tag += 1ll * z;
		return ;
	}
	push_down(root, l, r);
	LL mid = (l + r) >> 1;
	if (x <= mid) Update(root << 1, l, mid, x, y, z);
	if (y > mid) Update(root << 1 | 1, mid + 1, r, x, y, z);
	push_up(root);
}

inline LL Query (int root, int l, int r, int x, int y)
{
	if (y < l || x > r) return 0ll;
	if (x <= l && r <= y) return Tree[root].sum;
	push_down(root, l, r);
	LL mid = (l + r) >> 1;
	LL ans = 0ll;
	if (x <= mid) ans += Query(root << 1, l, mid, x, y);
	if (y > mid) ans += Query(root << 1 | 1, mid + 1, r, x, y);
	return ans;
}

int main()
{
#ifdef hk_cnyali
	freopen("A.in", "r", stdin);
	freopen("A.out", "w", stdout);
#endif

	scanf("%d%d%d%d", &N, &M, &p1, &p2);
	for (int i = 1; i <= N; ++i)
		scanf("%d", &A[i]);

	A[0] = A[N + 1] = 0x3f3f3f3f;
	for (int i = 2; i <= N; ++i)
	{
		int now = i - 1;
		while (A[now] < A[i])
			now = L[now];
		L[i] = now;
	}

	R[N] = N + 1;
	for (int i = N - 1; i >= 1; --i)
	{
		int now = i  + 1;
		while (A[now] < A[i])
			now = R[now];
		R[i] = now;
	}

	/*
	for (LL i = 1; i <= N; ++i) cout<<L[i]<<" ";
	cout<<endl;
	for (LL i = 1; i <= N; ++i) cout<<R[i]<<" ";
	cout<<endl;
	*/

/*
   R[i]  + L[i] -> p1
   L[i]  + (i + 1 ... R[i] - 1) -> p2
   R[i]  + (L[i] + 1 ... i - 1) -> p2
 */

	for (int i = 1; i <= N; ++i)
	{
		vec_modify[R[i]].push_back((Triple){L[i], L[i], p1});
		//vec_modify[R[i]].push_back((Triple){R[i], R[i], p1});
		vec_modify[i].push_back((Triple){i - 1, i - 1, p1});
		vec_modify[L[i]].push_back((Triple){i + 1, R[i] - 1, p2});
		vec_modify[R[i]].push_back((Triple){L[i] + 1, i - 1, p2});
	}

	int x, y;
	for (int i = 1; i <= M; ++i)
	{
		scanf("%d%d", &x, &y);
		vec_query1[x].push_back((Pair){y, i});
		vec_query2[y].push_back((Pair){x, i});
	}

	for (int i = 0; i <= N; ++i)
	{
		for (int j = 0; j < vec_modify[i].size(); ++j)
			//cout<<vec_modify[i][j].x<<" "<<vec_modify[i][j].y<<" "<<vec_modify[i][j].z<<endl,
			Update(1, 1, N, vec_modify[i][j].x, vec_modify[i][j].y, vec_modify[i][j].z);
		for (int j = 0; j < vec_query1[i + 1].size(); ++j)
			//cout<<vec_query1[i + 1][j].y<<" ",
			Ans[vec_query1[i + 1][j].y] = Query(1, 1, N, i + 1, vec_query1[i + 1][j].x);
		for (int j = 0; j < vec_query2[i].size(); ++j)
			//cout<<vec_query2[i][j].y<<" ",
			Ans[vec_query2[i][j].y] = Query(1, 1, N, vec_query2[i][j].x, i) - Ans[vec_query2[i][j].y];
	}
	//cout<<endl;

	for (int i = 1; i <= M; ++i)
		printf("%lld\n", Ans[i]);
	return 0;
}