BZOJ 4262 Sum | 2018 Asia Jiaozuo Regional Online C Password

最新推荐文章于 2020-08-14 11:57:17 发布

原创最新推荐文章于 2020-08-14 11:57:17 发布 · 1.1k 阅读

0 ·

CC 4.0 BY-SA版权

文章标签：

#数据结构 #分治

BZOJ 同时被 3 个专栏收录

22 篇文章

订阅专栏

线上比赛

12 篇文章

订阅专栏

Jisuanke

1 篇文章

订阅专栏

本文介绍了一种处理区间查询问题的有效算法，通过预处理和数据结构优化实现快速响应。该算法适用于特定类型的序列查询，能够有效地解决最大值和最小值的求和问题。

文章目录

题目链接

BZOJ 4642 Sum 和计蒜客 31712 Password

题目大意

给定长度为 $n$ 的序列 $A_1, A_2, \cdots, A_n$ ，以及 $m$ 组形如 $l_1, r_1, l_2, r_2)$ 的询问，请你对于每组询问，求出 $\sum_{i = l_1}^{r_1} \sum_{j = \max\{i, l_2\}}^{r_2} {f(i, j)}$ 的值，其中：

对于 BZOJ 4642，有 $\max\limits_{i \leq p \leq j}\{A_p\} - \min\limits_{i \leq q \leq j}\{A_q\}$ ( $\leq i \leq j \leq n$ )
对于 Jiaozuo Online C，有 $1)\max\limits_{i \leq p \leq j}\{A_p\}$ ( $\leq i \leq j \leq n$ )

数据范围

对于 BZOJ 4642，有 $n = 10^5$ , $A_i = ({1023}^{i} \bmod {10}^9)~\mathrm{xor}~({1025}^{i} \bmod {10}^9)$ ( $\ldots, n$ ), $\leq m \leq 4 \cdot 10^4$ , $\leq l_1 \leq r_1 \leq n$ , $\leq l_2 \leq r_2 \leq n$
对于 Jiaozuo Online C，有 $\leq n, m, A_i \leq 10^5$ ( $\ldots, n$ ), $\leq l_1 \leq r_1 \leq n$ , $\leq l_2 \leq r_2 \leq n$

题目解法

补充定义 $\leq j < i \leq n$ 时 $f (i, j) = 0$ ，则询问的值等于 $\sum_{i = l_1}^{r_1} \sum_{j = l_2}^{r_2} {f(i, j)}$ 。若将 $f (i, j)$ 看成二维矩阵，则询问需要计算一个子矩阵的和。

尝试考虑如何用 $\mathcal{O}(n)$ 的信息表示出所有的 $f (i, j)$ ( $\leq i, j \leq n$ )。不难注意到 $f (i, j)$ 只和 $i, j, A_p, A_q$ 有关。

对于每个 $A_p$ ，我们可以利用单调栈的技巧找到最小的 $x$ 和最大的 $y$ 使得 $\leq i \leq p \leq j \leq y$ 时 $A_p$ 都是 $f (i, j)$ 中对应的最大值。不过 $f (i, j)$ 对应的 $A_p, A_q$ 可能有很多个，为了避免重复统计，在这里我们约定当 $p$ 是 $f (i, j)$ 中最靠左的最大值出现位置时， $A_p$ 才对 $f (i, j)$ 产生贡献。 $A_q$ 的分析过程同理可得。注意到每个 $A_p$ （或 $A_q$ ）的影响区域也是 $f (i, j)$ 的子矩阵。

注意到统计信息是求和得出的，子矩阵 $[l_1, r_1] \times [l_2, r_2]$ 的统计值，可以表示成四个子矩阵 $r_1] \times [1, r_2]$ , $l_1 - 1] \times [1, r_2]$ , $r_1] \times [1, l_2 - 1]$ , $l_1 - 1] \times [1, l_2 - 1]$ 的统计值的组合。

同样地， $A_p$ （或 $A_q$ ）对一个子矩阵 $[x_1, y_1] \times [x_2, y_2]$ 产生贡献，也可以表示成它对四个子矩阵 $[x_1, n] \times [x_2, n]$ , $[y_1 + 1, n] \times [x_2, n]$ , $[x_1, n] \times [y_2 + 1, n]$ , $[y_1 + 1, n] \times [y_2 + 1, n]$ 分别产生贡献。

经过上述等价改写后，我们只需要考虑每个产生贡献的矩阵 $[x_1, n] \times [x_2, n]$ 对每个询问统计值的矩阵 $r_1] \times [1, r_2]$ 产生了多少相应的贡献，这里的贡献是 $f (i, j)$ 中不属于最值的那部分信息，举例来说：

对于 BZOJ 4262，最大值的贡献是 $1$ ，最小值的贡献是 $- 1$
对于 Jiaozuo Online C，最大值的贡献是 $(j - i + 1)$

其中 $x_1 \leq i \leq r_1$ , $x_2 \leq j \leq r_2$ 。

问题化简为在二维偏序上容易统计的信息，我们可以将这些信息，即 $x_1, x_2)$ 或 $r_1, r_2)$ ，首先关于第一维进行排序，然后用类似归并排序的过程将其重新关于第二维排序。在归并排序合并每个区间划分的两个子区间分别排序后的有序表过程中，统计前面区间中贡献矩阵（数点）对后面区间中询问矩阵（数点）的贡献。具体来说：

对于 BZOJ 4262，贡献矩阵和询问矩阵交集部分所产生的最大值贡献中贡献的系数是 $\sum_{i = x_1}^{r_1} \sum_{j = x_2}^{r_2}{1} = (r_1 + 1)(r_2 + 1) - (r_2 + 1) x_1 - (r_1 + 1) x_2 + x_1 x_2$ ，那么维护前面区间中第二维取值不超过 $k$ 的所有贡献矩阵对应的 $\sum{v}$ , $\sum{x_1 v}$ , $\sum{x_2 v}$ , $\sum{x_1 x_2 v}$ 就能方便地求出后面区间中每个询问矩阵获得的贡献，其中 $v$ 是相应的最大值、最小值或者它们的相反数
对于 Jiaozuo Online C，相应的系数是 $\sum_{i = x_1}^{r_1} \sum_{j = x_2}^{r_2}{(j - i + 1)}$ ，是一个关于 $v$ , $x_1 v$ , $x_2 v$ , $x_1^2 v$ , $x_2^2 v$ , $x_1 x_2 v$ , $x_1^2 x_2 v$ , $x_1 x_2^2 v$ 的多项式，分别维护即可。

代码实现

由于解法的部分内容留给读者推导，为了不做出剧透，这里仅给出 BZOJ 4262 的实现。对于 Jiaozuo Online C，还需要注意答案可能超过 $2^{63}$ ，但不会超过 $2^{64} - 1)$ 。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = (int)1e5 + 1, maxm = maxn << 4 | 1;
int m, low, upp, etot, ord[maxm], que[maxm];
LL ans[maxn];
struct Event {
	int typ, x, y;
	LL v;
} eve[maxm];
bool cmp(int const &u, int const &v) {
	if(eve[u].x != eve[v].x)
		return eve[u].x < eve[v].x;
	if(eve[u].y != eve[v].y)
		return eve[u].y < eve[v].y;
	return eve[u].typ < eve[v].typ;
}
void addEvent(int typ, int x, int y, int v) {
	if(x < low || x > upp || y < low || y > upp || !v)
		return;
	ord[etot] = etot;
	eve[etot++] = (Event){typ, x, y, (LL)v};
}
void solve(int L, int R) {
	if(L == R)
		return;
	int M = (L + R) >> 1;
	solve(L, M);
	solve(M + 1, R);
	LL cnt[5] = {};
	for(int i = L, j = M + 1, k = 0; i <= M || j <= R; ) {
		int u = ord[i], v = ord[j];
		if(j > R || (i <= M && eve[u].y <= eve[v].y)) {
			if(!eve[u].typ) {
				LL v0 = eve[u].v, v1 = v0 * eve[u].x, v2 = v0 * eve[u].y, v3 = v1 * eve[u].y;
				cnt[0] += v0;
				cnt[1] += v1;
				cnt[2] += v2;
				cnt[3] += v3;
			}
			que[k++] = ord[i++];
		} else {
			if(eve[v].typ) {
				LL v3 = 1;
				LL v2 = -eve[v].x - 1;
				LL v1 = -eve[v].y - 1;
				LL v0 = v2 * v1;
				ans[eve[v].typ] += eve[v].v * (cnt[0] * v0 + cnt[1] * v1 + cnt[2] * v2 + cnt[3] * v3);
			}
			que[k++] = ord[j++];
		}
	}
	memcpy(ord + L, que, (R - L + 1) * sizeof(int));
}
void solve() {
	sort(ord, ord + etot, cmp);
	int tot = 0;
	for(int i = 0; i < etot; ) {
		int typ = eve[ord[i]].typ, x = eve[ord[i]].x, y = eve[ord[i]].y;
		LL v = 0;
		for( ; i < etot && eve[ord[i]].typ == typ && eve[ord[i]].x == x && eve[ord[i]].y == y; ++i)
			v += eve[ord[i]].v;
		if(v)
			eve[ord[tot++]] = (Event){typ, x, y, v};
	}
	if(tot)
		solve(0, tot - 1);
}
int main() {
	static int seq[4][maxn], *a = seq[0], *pL = seq[1], *pR = seq[2], *stk = seq[3];
	scanf("%d", &m);
	low = maxn;
	upp = 0;
	for(int i = 1; i <= m; ++i) {
		scanf("%d%d%d%d", seq[0] + i, seq[1] + i, seq[2] + i, seq[3] + i);
		low = min(low, min(seq[0][i], seq[2][i]));
		upp = max(upp, max(seq[1][i], seq[3][i]));
	}
	for(int i = 1; i <= m; ++i) {
		int &xL = seq[0][i], &xR = seq[1][i], &yL = seq[2][i], &yR = seq[3][i];
		addEvent(i, xR, yR, 1);
		addEvent(i, xL - 1, yR, -1);
		addEvent(i, xR, yL - 1, -1);
		addEvent(i, xL - 1, yL - 1, 1);
	}
	for(int i = 1, u = 1, v = 1, p = (int)1e9; i <= upp; ++i) {
		u = (((LL)u << 10) - u) % p;
		v = (((LL)v << 10) + v) % p;
		a[i] = u ^ v;
	}
	for(int i = low, sz = 0; i <= upp; ++i) {
		for( ; sz && a[stk[sz - 1]] < a[i]; --sz);
		pL[i] = sz ? stk[sz - 1] + 1 : low;
		stk[sz++] = i;
	}
	for(int i = upp, sz = 0; i >= low; --i) {
		for( ; sz && a[stk[sz - 1]] <= a[i]; --sz);
		pR[i] = sz ? stk[sz - 1] - 1 : upp;
		stk[sz++] = i;
		addEvent(0, pL[i], i, a[i]);
		addEvent(0, pL[i], pR[i] + 1, -a[i]);
		addEvent(0, i + 1, i, -a[i]);
		addEvent(0, i + 1, pR[i] + 1, a[i]);
	}
	for(int i = low, sz = 0; i <= upp; ++i) {
		for( ; sz && a[stk[sz - 1]] > a[i]; --sz);
		pL[i] = sz ? stk[sz - 1] + 1 : low;
		stk[sz++] = i;
	}
	for(int i = upp, sz = 0; i >= low; --i) {
		for( ; sz && a[stk[sz - 1]] >= a[i]; --sz);
		pR[i] = sz ? stk[sz - 1] - 1 : upp;
		stk[sz++] = i;
		addEvent(0, pL[i], i, -a[i]);
		addEvent(0, pL[i], pR[i] + 1, a[i]);
		addEvent(0, i + 1, i, a[i]);
		addEvent(0, i + 1, pR[i] + 1, -a[i]);
	}
	solve();
	for(int i = 1; i <= m; ++i)
		printf("%lld\n", ans[i]);
	return 0;
}