Codeforces 1139F（树状数组+扫描线）

题目传送

做法

• 对于每个人，inc为x，pref为y；对于每道菜，p和s为x，b为y
• 于是根据题意有$$p[i]<=x<=s[i]$$$$p[i]+b[i]<=x+y$$$$p[i]-b[i]<=x-y$$
• 把所有出现的点都离散化一下，然后开始扫x轴
• 对于x+y和x-y这两个函数，分别开一个树状数组去维护合法点的个数

#include <cstdio>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <vector>
#define rep(i, a, b)	for (int i = a; i <= b; i++)
#define All(x)	(x.begin()), (x.end())
using namespace std;

template <typename T> void read(T &x) {
	x = 0;
	T s = 1, c = getchar();
	for (; !isdigit(c); c = getchar())
		if (c == '-')	s = -1;
	for (; isdigit(c); c = getchar())
		x = x * 10 + c - 48;
	x *= s;
}

typedef long long ll;
const int maxn = 1e5 + 5;
int n, m, tot;
ll p[maxn], s[maxn], b[maxn], inc[maxn], pref[maxn];
int ans[maxn];
vector<ll> A, B;
vector<pair<ll, int>>que;

class FenwickTree {
public:
	int F[maxn << 1];

	void Modify(int x, int val) {
		for (; x <= maxn << 1; x += x&-x)
			F[x] += val;
	}

	int Query(int x) {
		int ret = 0;
		for (; x; x -= x&-x)
			ret += F[x];
		return ret;
	}
}bitA, bitB;

inline void Read() {
	read(n), read(m);
	rep(i, 1, n)	read(p[i]);
	rep(i, 1, n)	read(s[i]);
	rep(i, 1, n)	read(b[i]);
	rep(i, 1, m)	read(inc[i]);
	rep(i, 1, m)	read(pref[i]);
}

inline void Discrete() {
	A.push_back(-(1LL << 60));
	B.push_back(-(1LL << 60));
	rep(i, 1, n) {
		que.push_back({p[i], i});
		que.push_back({s[i], i + maxn * 2});
		A.push_back(p[i] + b[i]);
		B.push_back(p[i] - b[i]);
	}
	rep(i, 1, m) {
		que.push_back({inc[i], i + maxn});
		A.push_back(inc[i] + pref[i]);
		B.push_back(inc[i] - pref[i]);
	}

	sort(All(que)), sort(All(A)), sort(All(B));
	A.erase(unique(All(A)), A.end());
	B.erase(unique(All(B)), B.end());
}

inline void Sweep() {
	int num = 0;
	for (auto i : que) {
		int x = i.second, y;
		if (x < maxn) {
			num++;
			y = lower_bound(All(A), p[x] + b[x]) - A.begin();
			bitA.Modify(y, 1);
			y = lower_bound(All(B), p[x] - b[x]) - B.begin();
			bitB.Modify(y, 1);
		} else if (x < maxn * 2) {//注意排序顺序p < inc < s
			x -= maxn;
			y = lower_bound(All(A), inc[x] + pref[x]) - A.begin();
			ans[x] += bitA.Query(y);
			y = lower_bound(All(B), inc[x] - pref[x]) - B.begin();
			ans[x] += bitB.Query(y);
			ans[x] -= num;
			//当一个x一定大于等于另一个x时，无论y的关系如何，这样容斥一定能得到正确答案
		} else {
			x -= maxn * 2;
			num--;
			y = lower_bound(All(A), p[x] + b[x]) - A.begin();
			bitA.Modify(y, -1);
			y = lower_bound(All(B), p[x] - b[x]) - B.begin();
			bitB.Modify(y, -1);	
		}
	}
	rep(i, 1, m)	printf("%d%c", ans[i], " 
"[i == m]);
}

int main() {
	Read();
	Discrete();
	Sweep();
	return 0;
}