Luogu – P5677 – [GZOI2017]配对统计


Luogu – P5677 – [GZOI2017]配对统计

题意

给定一个数列 $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;
}
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇