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], " \n"[i == m]);
}int main() {
Read();
Discrete();
Sweep();
return 0;
}