【洛谷-P5677】配对统计 • TonyYin's Blog

题意#

给定一个数列 $a_1, a_2, \cdots, a_n$ .

定义在有序数对 $(x, y)$ 上的“好对”：对于 $a_x$ ， $y\in[1, x)\cup(x, n]$ 能使 $|a_x-a_y|$ 取最小值。

给定 $q\leq 3\times 10^5$ 组询问，每次询问一个区间 $[l, r]$ 中，有多少个好对。

题目求：每次询问的答案 $Ans_i$ 与询问编号 $i$ 的乘积的和，即：

\sum_{i=1}^{m}Ans_i\times i

分析#

关于匹配#

任何一个好对 $(x, y)$ ，都满足 $|a_x-a_y|\leq |a_x-a_i|(i\neq x)$ .

并且通过数据范围可以发现： $\forall i\neq j$ 都有 $a_i\neq a_j$ ，所以当 $x$ 固定时，确定 $y$ 的方法是非常自然的。

将 $a$ 数组排序，排序后的数组为 $b$ ，不妨设 $a_x$ 在 $b$ 中的下标为 $t$ ，那么 $a_y$ 在 $b$ 中的下标只可能为 $t-1$ 和 $t+1$ .

具体地：

如果 $|b_t-b_{t-1}|<|b_{t+1}-b_{t}|$ ，也就是 $b_{t-1}$ 距离 $b_t$ 更近，那么 $a_y$ 在 $b$ 中的下标为 $t-1$ ；
如果 $|b_t-b_{t-1}|>|b_{t+1}-b_{t}|$ ，此时 $b_{t+1}$ 距离 $b_t$ 最近， $a_y$ 在 $b$ 中的下标为 $t+1$ ；
如果 $|b_t-b_{t-1}|=|b_{t+1}-b_{t}|$ ， $a_y$ 在 $b$ 中的下标为 $t-1$ 或 $t+1$ .

总之，我们可以非常容易地在 $O(n\log n)$ 复杂度内，对于每个 $x$ ，找到能与其构成好的配对的 $y$ .

关于询问#

思路#

现在的问题是如何统计答案。

因为题目只要求输出所有询问的和，于是想到将询问离线下来。对于每个好对，统计有多少个询问完全覆盖了它。这个好对对于最终答案的贡献就是：所有覆盖它的询问的编号之和。

对于这个问题，容易想到将所有询问排序，之后用树状数组维护，具体方法：

方法#

从左到右枚举 $[1, n]$ ，假设枚举到了 $i$ .

对于 $i$ ，我们已经计算过与其匹配的数，在 $a$ 中的下标 $y$ ，如果 $y>i$ ，那么所有左端点 $l\leq i$ 且右端点 $r\geq y$ 的询问都能包含这个好对。

再考虑答案的形式 $\sum_{i=1}^{m}Ans_i\times i$ ，我们现在要求：左端点 $l\leq i$ 且右端点 $r\geq y$ 的询问的编号和，使用树状数组维护。

于是考虑将询问按照左端点排序，在枚举到 $i$ 的时候，把所有左端点 $l\leq i$ 的询问加入到树状数组中，把树状数组的位置 $r$ 的权值加上这个询问的编号 $num$ .

这样， $(i, y)$ 的贡献就等价于：树状数组中 $[y, n]$ 的区间和。

如果与 $i$ 匹配的 $y<i$ ，在上面的方法中并没有包含到。所以我们再反向枚举一遍 $i$ ，方法相同。将右端点 $r\geq i$ 的询问加入树状数组，每次的贡献为树状数组中 $[1, y]$ 的区间和。

代码#

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 3e5 + 10;
const int inf = 0x3f3f3f3f3f3f3f3f;
int c[MAXN];
int n, m;
int lowbit(int x) {
	return x & (-x);
}
void update(int x, int k) {
	for(int i = x; i <= n; i += lowbit(i)) {
		c[i] += k;
	}
}
int query(int x) {
	int ret = 0;
	for(int i = x; i > 0; i -= lowbit(i)) {
		ret += c[i];
	}
	return ret;
}
int query2(int x) {
	return query(n) - query(x - 1);
}
int a[MAXN];
struct Node{int num, val;} b[MAXN];
bool cmp(Node A, Node B) {
	return A.val <= B.val;
}
struct Query{int val, l, r;} q[MAXN];
bool cmp2(Query A, Query B) {
	return A.r >= B.r;
}
bool cmp3(Query A, Query B) {
	return A.l <= B.l;
}
int rk[MAXN];
signed main() {
	scanf("%lld%lld", &n, &m);
	for(int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
		b[i].val = a[i]; b[i].num = i;
	}
	sort(b + 1, b + n + 1, cmp);
	for(int i = 1; i <= n; i++) {
		rk[b[i].num] = i;
	}
	for(int i = 1; i <= m; i++)  {
		q[i].val = i;
		scanf("%lld%lld", &q[i].l, &q[i].r);
	}
	sort(q + 1, q + m + 1, cmp2);
	int ans = 0;
	b[0].val = -inf; b[n + 1].val = inf;
	for(int i = n, j = 1; i >= 1; i--) {
		while(q[j].r >= i && j <= m) {
			update(q[j].l, q[j].val);
			j++;
		}
        //下面六行：判断 t-1 和 t+1，哪个距离 t 更近，能与 t 构成好的匹配。
		if(b[rk[i]].val - b[rk[i] - 1].val <= b[rk[i] + 1].val - b[rk[i]].val) {
			if(b[rk[i] - 1].num < i) ans += query(b[rk[i] - 1].num);
		}
		if(b[rk[i]].val - b[rk[i] - 1].val >= b[rk[i] + 1].val - b[rk[i]].val) {
			if(b[rk[i] + 1].num < i) ans += query(b[rk[i] + 1].num);
		}
	}
	sort(q + 1, q + m + 1, cmp3);
	memset(c, 0, sizeof(c));
	for(int i = 1, j = 1; i <= n; i++) {
		while(q[j].l <= i && j <= m) {
			update(q[j].r, q[j].val);
			j++;
		}
		if(b[rk[i]].val - b[rk[i] - 1].val <= b[rk[i] + 1].val - b[rk[i]].val) {
			if(b[rk[i] - 1].num > i) ans += query2(b[rk[i] - 1].num);
		}
		if(b[rk[i]].val - b[rk[i] - 1].val >= b[rk[i] + 1].val - b[rk[i]].val) {
			if(b[rk[i] + 1].num > i) ans += query2(b[rk[i] + 1].num);
		}
	}
	cout << ans << endl;
	return 0;
}

cpp