BZOJ 4540: [Hnoi2016]序列

Description

给定长度为n的序列:a1,a2,…,an,记为a[1:n]。类似地,a[l:r](1≤l≤r≤N)是指序列:al,al+1,…,ar-1,ar。若1≤l≤s≤t≤r≤n,则称a[s:t]是a[l:r]的子序列。现在有q个询问,每个询问给定两个数l和r,1≤l≤r≤n,求a[l:r]的不同子序列的最小值之和。例如,给定序列5,2,4,1,3,询问给定的两个数为1和3,那么a[1:3]有6个子序列a[1:1],a[2:2],a[3:3],a[1:2],a[2:3],a[1:3],这6个子序列的最小值之和为5+2+4+2+2+2=17。

Input

输入文件的第一行包含两个整数n和q,分别代表序列长度和询问数。接下来一行,包含n个整数,以空格隔开,第i个整数为ai,即序列第i个元素的值。接下来q行,每行包含两个整数l和r,代表一次询问。

Output

对于每次询问,输出一行,代表询问的答案。

Sample Input

5 5
5 2 4 1 3
1 5
1 3
2 4
3 5
2 5

Sample Output

28
17
11
11
17

HINT

1 ≤N,Q ≤ 100000,|Ai| ≤ 10^9

Solution

莫队,然后考虑向右移动r时答案的变化,显然答案新增了以r为右端点,l…r-1为左端点的许多区间。

定义left[i]表示i左边第一个小于i的数,定义sl[i]表示从i开始一直向左走走到1的代价(最小值之和)。设区间l…r最小值在p处,那么答案就多了sl[r]-sl[p]+(p-l+1)*val[p]。前面的是从i走到最小值位置的代价,后面是按照最小值走l到p这一段的代价。

left[i]可以用单调栈推出,sl[i]可以用left和l到r的最小值位置推出,最小值位置p可以用RMQ求出。

然后左端点移动也是一样的,用right表示i右边第一个小于i的数,sr表示从i考试向右走到n的代价。用一样的方法推出这两个数组,对答案的贡献也是相似的。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int INF = 1009999999;
int getint() {
    int r = 0, k = 1; char c = getchar();
    for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
    for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
    return r * k;
}
int stack[100005], tail, n, F[100005][30];
int l2k[100005];
LL A[100005];
void RMQ() {
	for (int i = 1; i <= n; ++i) {
		F[i][0] = i;
		for (int x = i; x; x >>= 1)
			++l2k[i];
		--l2k[i];
	}
	for (int k = 1; k <= l2k[n]; ++k) {
		int len = 1 << k;
		for (int i = 1; i <= n; ++i) {
			if (i + len - 1 > n) break;
			if (A[F[i][k - 1]] < A[F[i + (len >> 1)][k - 1]])
				F[i][k] = F[i][k-1];
			else
				F[i][k] = F[i+(len>>1)][k-1];
		}
	}
}
int getmin(int l, int r) {
	int len = r - l + 1, k = l2k[len];
	if (A[F[l][k]] < A[F[r - (1 << k) + 1][k]])
		return F[l][k];
	return F[r - (1 << k) + 1][k];
}
int L, R, Q, left[100005], right[100005];
int qx[100005], qy[100005], id[100005];
LL sr[100005], sl[100005];
LL Ans[100005];
const int size = 316;
bool cmp(int x, int y) {
	if (qx[x] / size == qx[y] / size)
		return qy[x] < qy[y];
	return qx[x] / size < qx[y] / size;
}
LL LM() {
	int minpos = getmin(L, R);
	return A[minpos] * (R - minpos + 1) + sr[L] - sr[minpos];
}
LL RM() {
	int minpos = getmin(L, R);
	return A[minpos] * (minpos - L + 1) + sl[R] - sl[minpos];
}
int main() {
	n = getint(); Q = getint();
	for (int i = 1; i <= n; ++i) {
		A[i] = getint();
		while (tail && A[i] <= A[stack[tail]])
			--tail;
		left[i] = stack[tail];
		stack[++tail] = i;
	}
	for (int i = 1; i <= n; ++i)
		sl[i] = sl[left[i]] + A[i] * (i - left[i]);
	tail = 0;
	stack[0] = n + 1;
	for (int i = n; i; --i) {
		while (tail && A[i] <= A[stack[tail]])
			--tail;
		right[i] = stack[tail];
		stack[++tail] = i;
	}
	for (int i = n; i; --i)
		sr[i] = sr[right[i]] + A[i] * (right[i] - i);
	RMQ();
	for (int i = 1; i <= Q; ++i) {
		qx[i] = getint();
		qy[i] = getint();
		id[i] = i;
	}
	sort(id + 1, id + Q + 1, cmp);
	LL ans = A[1];
	L = R = 1;
	for (int i = 1; i <= Q; ++i) {
		int now = id[i];
		while (R < qy[now]) {
			++R;
			ans += RM();
		}
		while (L < qx[now]) {
			ans -= LM();
			++L;
		}
		while (R > qy[now]) {
			ans -= RM();
			R--;
		}
		while (L > qx[now]) {
			--L;
			ans += LM();
		}
		Ans[now] = ans;
	}
	for (int i = 1; i <= Q; ++i)
		printf("%lld\n", Ans[i]);
	return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据