给出一个长度为nn的序列aia_i

有qq次询问，每次给出[l,r][l, r]，求∑i=lr∑j=irmink=ijak\displaystyle \sum_{i=l}^{r}\sum_{j=i}^{r}\min_{k=i}^{j}a_k

n,q≤105,∣ai∣≤109n, q\le 10^5, |a_i|\le 10^9

LOJ 2051

Solution

考虑莫队，考虑从[l,r−1][l, r-1]转移到[l,r][l, r]答案的变化

新加进来的子串肯定都是以 结尾的子串，那么新加的答案就是

也就是要求区间 的最小值的和

考虑区间中每个值对答案的贡献，假设下标为 的数左边第一个比它小的数为 ，右边第一个比它小的数为 ，那么区间 的最小值都是它

先用单调栈求出xi,yix_i, y_i，设sumLisumL_i表示以11为左端点， 为右端点区间最小值的和

显然这个贡献是一段一段的，因此可以用前缀和优化

最后算答案的时候先用ST表求出区间[l,r][l, r]的最小值的位置pp，那么新加的答案就是ap∗(p−l+1)+sumLr−sumLpa_p * (p - l + 1) + sumL_{r} - sumL_{p}

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
154
155
156
157
158
159
160
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 100000 + 100;

int BLOCK;

int N, M;
int A[Maxn], Belong[Maxn];
pair <pii, int> Q[Maxn];

namespace ST
{
	int Log[Maxn];
	pii Min[20][Maxn];

	inline void init ()
	{
		for (int i = 2; i <= N; ++i) Log[i] = Log[i >> 1] + 1;
		for (int i = 1; i <= N; ++i) Min[0][i] = mp (A[i], i); 
		for (int j = 1; j <= Log[N]; ++j)
			for (int i = 1; i <= N - (1 << j) + 1; ++i)
				Min[j][i] = min (Min[j - 1][i], Min[j - 1][i + (1 << (j - 1))]);
	}

	inline int query (int l, int r)
	{
		int k = Log[r - l + 1];
		return min (Min[k][l], Min[k][r - (1 << k) + 1]).y;
	}
}

inline int cmp (pair <pii, int> a, pair <pii, int> b)
{
	if (Belong[a.x.x] == Belong[b.x.x]) return (Belong[a.x.x] & 1) ? (a.x.y < b.x.y) : (a.x.y > b.x.y);
	return Belong[a.x.x] < Belong[b.x.x];
}

int L[Maxn], R[Maxn], Stack[Maxn], top;
LL SumL[Maxn], SumR[Maxn];

inline void Init ()
{
	ST :: init ();

	for (int i = 1; i <= N; ++i) Belong[i] = (i - 1) / BLOCK + 1;
	sort (Q + 1, Q + M + 1, cmp);

	A[0] = -0x3f3f3f3f, Stack[++top] = 0;
	for (int i = 1; i <= N; ++i)
	{
		while (top && A[Stack[top]] >= A[i]) --top;
		L[i] = Stack[top];
		Stack[++top] = i;
	}

	top = 0;
	A[N + 1] = -0x3f3f3f3f, Stack[++top] = N + 1;
	for (int i = N; i >= 1; --i)
	{
		while (top && A[Stack[top]] >= A[i]) --top;
		R[i] = Stack[top];
		Stack[++top] = i;
	}

	for (int i = 1; i <= N; ++i) SumL[i] = SumL[L[i]] + (LL) A[i] * (i - L[i]);
	for (int i = N; i >= 1; --i) SumR[i] = SumR[R[i]] + (LL) A[i] * (R[i] - i);
}

LL ans;
int Vis[Maxn];

inline void Update (int l, int r, int op)
{
	int pos = ST :: query (l, r);
//	cout << l << ' ' << r << ' ' << pos << endl;
	if (op)
	{
		LL sum = (LL) A[pos] * (pos - l + 1) + SumL[r] - SumL[pos];
		if (!Vis[r]) ans += sum;
		else ans -= sum;
		Vis[r] ^= 1;
	}
	else
	{
		LL sum = (LL) A[pos] * (r - pos + 1) + SumR[l] - SumR[pos];
		if (!Vis[l]) ans += sum;
		else ans -= sum;
		Vis[l] ^= 1;
	}

}

LL Ans[Maxn];

inline void Solve ()
{
	Init ();

	int l = 1, r = 0;
	for (int i = 1; i <= M; ++i)
	{
		while (r < Q[i].x.y) Update (l, ++r, 1);
		while (l > Q[i].x.x) Update (--l, r, 0);
		while (r > Q[i].x.y) Update (l, r--, 1);
		while (l < Q[i].x.x) Update (l++, r, 0);
		Ans[Q[i].y] = ans;
	}

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

inline void Input ()
{
	N = read<int>(), M = read<int>(), BLOCK = sqrt(N);

	for (int i = 1; i <= N; ++i) A[i] = read<int>();
	for (int i = 1; i <= M; ++i) Q[i].x.x = read<int>(), Q[i].x.y = read<int>(), Q[i].y = i;
}

int main()
{

#ifndef ONLINE_JUDGE
	freopen("A.in", "r", stdin);
	freopen("A.out", "w", stdout);
#endif

	Input ();
	Solve ();

	return 0;
}