CF2009G2 Yunli's Subarray Queries (hard version) Solution

对于一个满足条件的数组 $\{a\}$ ，我们对每个数加上 $n-i$ 那么就可以得到一个新数组 $\{b\}$ ，其中 $b_i=a_i+n-i$ ，因为 $a_i+1=a_{i+1}$ ，那么：

$\begin{aligned}b_i&=a_i+n-i,\\b_{i+1}=a_{i+1}+n-(i+1)&=a_i+1+n-i-1=a_i+n-i,\\ b_i=b_{i+1}\end{aligned}$

也就是 $b$ 数组完全相同。所以对于一个并不满足条件的长度为 $l$ 的数组，如果对它进行以上的变换之后，众数的个数是 $k$ ，则把它合法化的最少操作次数就是 $l-k$ 。

首先我们发现这道题是静态的。我们记

g_i

表示把子数组

a_i,a_{i+1},\cdots,a_{i+k-1}

这一段合法化的最小操作次数。这比较类似一个滑动窗口，根据上面引用内的性质，我们可以用一个 map 或者权值线段树

O(n\log n)

求出所有的

g_i

。所以题目定义的函数就是：

f([a_l,a_{l+1},\cdots,a_r])=\min_{i=l}^{r-k+1} g_i.

即取这么多子区间中最小的一个答案。所以对于一次询问

l, r

，要求的和式就是：

\text{Answer}=\sum_{i=l+k-1}^{r}\min_{j=l}^{i-k+1} g_j=\sum_{i=l}^{r-k+1}\min_{j=l}^i g_j.

即一个从

l

开始的前缀最小值连续和。我们发现这个并不好维护。我们考虑一个答案

g_i

能影响到的区间。首先我们发现，对于某一个

g_i

，它能影响到的区间最远可以到达下一个比他小的

g_j

之前（或者数组结尾）。那么我们处理一个

\{p\}

数组，

p_i

表示下一个小于

g_i

的数的位置（如果没有则为

n+1

），这个可以单调栈

O(n)

求出。然后思考如何求答案。

设当前询问左右端点分别为

x,y

，而前缀求值的右端点是

y-k+1

，我们不妨把

y

赋值为它。我们使用一个变量

t

，表示当前位置，一开始为

x

。那么前缀最小值为它的区间就是从

t

到

p_t-1

的区间，对答案的贡献是

g_t\times (p_t-t)

，然后把

t:= p_t

向后跳。直到跳到右端点

y

。然后贡献直接累加后输出即可。

暴力跳是

O(n)

的，可以使用倍增变成预处理

O(n\log n)

，查询

O(\log n)

。

总时间复杂度是

O(n\log n)

。

CPP

#include <bits/stdc++.h>
#define LL long long
#define int long long
using namespace std;
const int N = 5e5 + 10;
int n, K, Q, A[N], ret[N];
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
int tree[N << 2];
void pushup(int p) { tree[p] = max(tree[ls(p)], tree[rs(p)]); }
void build(int p, int l, int r) {
	tree[p] = -1e9; if (l == r) return ;
	int mid = (l + r) >> 1; build(ls(p), l, mid); build(rs(p), mid + 1, r);
	return ;
}
void update(int p, int l, int r, int x, int k) {
	if (x > r || x < l) return ;
	if (l == r) { 
		if (tree[p] == -1e9) tree[p] = 0; 
		tree[p] += k; 
		if (tree[p] == 0) tree[p] = -1e9;
		return ;
	}
	int mid = (l + r) >> 1; update(ls(p), l, mid, x, k); update(rs(p), mid + 1, r, x, k);
	pushup(p); return ;
}
int stk[N], tp = 0, fa[N][20]; LL sum[N][20];
signed main() {
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int _; cin >> _;
	while (_ --) {
		cin >> n >> K >> Q;
		for (int i = 1; i <= n; A[i] += n - i, i ++) cin >> A[i];
		build(1, 1, n * 2);
		for (int i = 1; i < K; i ++) update(1, 1, n * 2, A[i], 1);
		for (int i = 1; i <= n - K + 1; i ++) {
			update(1, 1, n * 2, A[i + K - 1], 1); ret[i] = K - tree[1]; update(1, 1, n * 2, A[i], -1);
		} tp = 0; ret[n - K + 2] = -1;
		for (int i = 1; i <= n - K + 2; i ++) {
			while (tp && ret[stk[tp]] >= ret[i]) {
				fa[stk[tp]][0] = i; sum[stk[tp]][0] = 1ll * (i - stk[tp]) * ret[stk[tp]]; tp --;
			} stk[++ tp] = i;
		}fa[n - K + 2][0] = n - K + 2; sum[n - K + 2][0] = 0;
		for (int k = 1; k <= 19; k ++) for (int i = 1; i <= n - K + 2; i ++)
			fa[i][k] = fa[fa[i][k - 1]][k - 1], sum[i][k] = sum[i][k - 1] + sum[fa[i][k - 1]][k - 1];
		int x, y;
		while (Q --) {
			cin >> x >> y;
			LL Ans = 0; int cur = x; y = y - K + 1;
			for (int i = 19; i >= 0; i --) if (fa[cur][i] <= y)
				Ans += sum[cur][i], cur = fa[cur][i];
			Ans += (y - cur + 1) * ret[cur]; cout << Ans << "\n";
		}
	}
	return 0;
}

CF2009G2 Yunli's Subarray Queries (hard version) Solution

文章操作

相关推荐

评论

CF2009G2 Yunli's Subarray Queries (hard version) Solution