CF1045G AI robots

\(CDQ\)分治的妙题。
考虑按视野从大到小排序，那右边的可以看见左边的话左边一定看得见右边的，直接\(CDQ\)就行了。对于这种\([x-K,x+K]\)的区间维护可以在统计的时候差分也可以直接在更新的时候差分。本代码使用后者。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define R register
#define LL long long
const int inf = 0x3f3f3f3f;
const int MAXN = 1e5 + 10;

inline int read() {
	char a = getchar(); int x = 0,f = 1;
	for(; a > '9' || a < '0'; a = getchar()) if(a == '-') f = -1;
	for(; a >= '0' && a <= '9' ;a = getchar()) x = x * 10 + a - '0';
	return x * f;
}

int n, k;
struct Node { int pos, sig, iq, l, r; } t[MAXN];
int b[MAXN * 3], cnt;
inline bool cmp1(Node x, Node y) { return x.sig > y.sig; }
inline bool cmp2(Node x, Node y) { return x.iq < y.iq; }

int tr[MAXN * 3];
inline int lowbit(int x) { return x & -x; }
inline void update(int x, int y) {
	for(; x < MAXN * 3 ; x += lowbit(x)) tr[x] += y;
}
inline int ask(int x) { 
	int ans = 0;
	for(; x ; x -= lowbit(x)) ans += tr[x];
	return ans;
}
inline int qask(int l, int r) {
	return ask(r) - ask(l - 1); 
}

LL Ans = 0;

inline void cdq(int l, int r) {
	if( l == r ) return ;
	int mid =((l + r) >> 1);
	cdq(l, mid); cdq(mid + 1, r);
	int ql = l, qr = l;
	for(R int i = mid + 1; i <= r; i ++) {
		while(ql <= mid && t[i].iq - t[ql].iq > k) { update(t[ql].pos, -1); ql ++; }
		while(qr <= mid && t[qr].iq - t[i].iq <= k) { update(t[qr].pos, 1);  qr ++; }
		Ans += qask(t[i].l, t[i].r);
	}
	while(ql <= mid) { update(t[ql].pos, -1); ql ++; }
	while(qr <= mid) { update(t[qr].pos, 1); qr ++; }
	sort(t + l, t + r + 1, cmp2); 
}

int main() {
	n = read(); k = read();
	for(R int i = 1; i <= n; i ++)
		t[i].pos = read(), t[i].sig = read(), t[i].iq = read();
	for(R int i = 1; i <= n; i ++) {
		b[++cnt] = t[i].pos;
		b[++cnt] = t[i].pos - t[i].sig;
		b[++cnt] = t[i].pos + t[i].sig;
	}
	sort(b + 1, b + 1 + cnt); 
	int N = unique(b + 1, b + 1 + cnt) - b - 1;
	for(R int i = 1; i <= n; i++) {
		t[i].l = lower_bound(b + 1, b + 1 + N, t[i].pos - t[i].sig) - b;
		t[i].r = lower_bound(b + 1, b + 1 + N, t[i].pos + t[i].sig) - b;
		t[i].pos = lower_bound(b + 1, b + 1 + N, t[i].pos) - b;
	}	
	sort(t + 1, t + 1 + n, cmp1);
	cdq(1, n);
	printf("%lld\n", Ans);
	return 0;	
}