CF1045G 题解

前言

题目传送门！

更好的阅读体验？

和模版稍有不同的 cdq 分治。

思路

cdq 是离线算法，所以我们可以先给 \(x_i\) 离散化一下。

同时，记录下 \((x_i - r_i)\) 与 \((x_i + r_i)\) 离散化后对应的结果，即视野范围。

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5;
struct Data {int pos, lpos, rpos, iq, R;} a[N], t[N];
int x[N], unq[N];
bool cmp(Data p, Data q) {return p.R > q.R;}
int n, k;
LL ans;

int idx[N]; //树状数组板子
int lowbit(int x) {return x & -x;}
void update(int i, int k) {for (; i <= n; i += lowbit(i)) idx[i] += k;}
int query(int i)
{
	int sum = 0;
	for (; i; i -= lowbit(i)) sum += idx[i];
	return sum;
}
int sum(int i, int j) {return query(j) - query(i - 1);}

void MergeSort(int l, int r) //cdq 分治！
{
	if (l >= r) return;
	int mid = (l + r) >> 1;
	MergeSort(l, mid), MergeSort(mid + 1, r);
	int L = l, R = l - 1; //类似单调队列，利用 k 的有序性不断更新 L 和 R
	for (int i = mid + 1; i <= r; i++)
	{
		while (L <= mid && a[i].iq - a[L].iq > k) update(a[L++].pos, -1);
		while (R < mid && a[R + 1].iq - a[i].iq <= k) update(a[++R].pos, 1);
		ans += sum(a[i].lpos, a[i].rpos);
	}
	for (int i = L; i <= R; i++) update(a[i].pos, -1); //清空 
	
	int i = l, j = mid + 1; //归并排序
	int cur = 0;
	while (i <= mid && j <= r)
		if (a[i].iq <= a[j].iq) t[++cur] = a[i], i++;
		else t[++cur] = a[j], j++;
	while (i <= mid) t[++cur] = a[i], i++;
	while (j <= r) t[++cur] = a[j], j++;
	for (i = l, j = 1; j <= cur; i++, j++) a[i] = t[j];
}
int main()
{
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++) scanf("%d%d%d", &x[i], &a[i].R, &a[i].iq), unq[i] = x[i];
	sort(unq + 1, unq + n + 1); //离散化ing 
	int m = unique(unq + 1, unq + n + 1) - unq - 1;
	for (int i = 1; i <= n; i++)
	{
		a[i].pos = lower_bound(unq + 1, unq + m + 1, x[i]) - unq;
		a[i].lpos = lower_bound(unq + 1, unq + m + 1, x[i] - a[i].R) - unq;
		a[i].rpos = upper_bound(unq + 1, unq + m + 1, x[i] + a[i].R) - unq - 1;
	}
	sort(a + 1, a + n + 1, cmp);
	MergeSort(1, n);
	printf("%lld", ans);
	return 0;
}

希望能帮助到大家！