专栏文章

题解：P14426 [JOISC 2014] 稻草人 / Scarecrows

CCatFromMars
P14426题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@min8irjk
此快照首次捕获于
2025/12/01 22:18
3 个月前
此快照最后确认于
2025/12/01 22:18
3 个月前
查看原文
千古神犇大 Toorean 给我看的题目。因为我是感冒期间口胡的，然后好像看错图了，接下来我们认为枚举的点对是左上角和右下角的点对，而并不是题目中左下角和右上角的点对。
注意到产生贡献的点对形式很怪，于是绝大部分情况下可以直接考虑分治。考虑一下按照 xx 轴分治，然后划分为 x≤midx \le mid 和 x>midx > mid 的两部分。
若 P,QP, Q 跨过 midmid 产生贡献当且仅当：
  • Px≤mid<QxP_x \le mid < Q_x。
  • Py≥QyP_y \ge Q_y 且中间没有任何点。
为了刻画中间没有任何点，提前与处理小于等于 midmid 部分且横坐标大于等于 PxP_x 的点中，纵坐标小于等于 PyP_y 的最大纵坐标 tyty，同理预处理横坐标小于等于 QxQ_x 的点中，纵坐标大于等于 QyQ_y 的最小纵坐标 sysy，那么中间没有点就等价于 sy>Py≥Qy>tysy > P_y \ge Q_y > ty，这本质上是一个二维数点。这个限制比较强，我的处理方式是：将 Qy≤Py<syQ_y \le P_y < sy 的点对减去 Qy≤ty,Py<syQ_y \le ty,P_y < sy 的点对，这样约束就从三个变成两个了。
有用的 xx 轴只有 O(n)O(n) 个，于是最后就是 O(nlog⁡2n)O(n\log ^2 n) 的。
代码：
CPP
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5;
namespace bit {
	int sum[N + 10], lim;
	int lowbit(int x) {
		return x & (-x);
	}
	void upd(int x, int y) {
		x++;
		while(x <= lim + 1) sum[x] += y, x += lowbit(x);
	}
	int qry(int x) {
		x++; int rest = 0;
		while(x)
			rest += sum[x], x -= lowbit(x);
		return rest;
	}
}

struct node {
	int x, y;
} D[N + 10], P[N + 10];
bool cmp(node &a, node &b) {
	return a.x < b.x;
}
bool cmpp(node &a, node &b) {
	return a.y < b.y;
}
int n, cpx[N + 10], cpy[N + 10];

ll ans = 0;
int ty[N + 10], sy[N + 10];
void solve(int l, int r) {
	if(l >= r) return ;
	int mid = (l + r) >> 1;
	solve(l, mid);
	solve(mid + 1, r);
	set <int> st;
	for(int i = mid; i >= l; i--) {
		if(st.empty()) ty[i] = 0;
		else {
			set <int>::iterator it = st.upper_bound(D[i].y);
			if(it == st.begin()) ty[i] = 0;
			else {
				it--;
				ty[i] = (*it);
			}
		}
		st.insert(D[i].y);
		P[i] = (node){ty[i], D[i].y};
	}
	st.clear();
	for(int i = mid + 1; i <= r; i++) {
		if(st.empty()) sy[i] = n + 1;
		else {
			set <int>::iterator it = st.upper_bound(D[i].y);
			if(it == st.end()) sy[i] = n + 1;
			else sy[i] = (*it);
		}
		st.insert(D[i].y);
		P[i] = (node){D[i].y, sy[i]};
	}

	for(int i = mid + 1; i <= r; i++) {
		bit::upd(D[i].y, 1);
		bit::upd(sy[i], -1);
	}
	for(int i = l; i <= mid; i++)
		ans += (bit::qry(D[i].y));
	for(int i = mid + 1; i <= r; i++)
		bit::upd(D[i].y, -1),
		bit::upd(sy[i], 1);
	sort(P + mid + 1, P + r + 1, cmp);
	sort(P + l, P + mid + 1, cmp);
	int j = mid + 1;
	for(int i = l; i <= mid; i++) {
		while(j <= r && P[j].x <= P[i].x)
			bit::upd(P[j].y, 1), j++;
		ans -= (bit::qry(bit::lim) - bit::qry(P[i].y));
	}
	for(int i = mid + 1; i < j; i++) bit::upd(P[i].y, -1);
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	bit::lim = n + 5;
	for(int i = 1; i <= n; i++)
		cin >> D[i].x >> D[i].y, D[i].y = 1000000000 - D[i].y,
		cpx[i] = D[i].x, cpy[i] = D[i].y;

	int len;
	sort(cpx + 1, cpx + n + 1);
	len = unique(cpx + 1, cpx + n + 1) - cpx - 1;
	for(int i = 1; i <= n; i++) D[i].x = lower_bound(cpx + 1, cpx + len + 1, D[i].x) - cpx;
	sort(cpy + 1, cpy + n + 1);
	len = unique(cpy + 1, cpy + n + 1) - cpy - 1;
	for(int i = 1; i <= n; i++) D[i].y = lower_bound(cpy + 1, cpy + len + 1, D[i].y) - cpy;

	sort(D + 1, D + n + 1, cmp);
	solve(1, n);

	cout << ans << '\n';
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...