传送门
\(\texttt{Difficulty:2500}\)
#include<bits/stdc++.h> #include<unordered_map> #include<unordered_set> using namespace std; using LL = long long; using LD = long double; using ULL = unsigned long long; using PII = pair<int, int>; using TP = tuple<int, int, int>; #define all(x) x.begin(),x.end() #define mst(x,v) memset(x,v,sizeof(x)) #define mk make_pair //#define int LL #define lc p*2 #define rc p*2+1 #define endl '\n' #define inf 0x3f3f3f3f #define INF 0x3f3f3f3f3f3f3f3f #pragma warning(disable : 4996) #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) const double eps = 1e-8; const LL MOD = 1000000009; const LL mod = 998244353; const int maxn = 100010; int N, M, p[maxn], s[maxn], b[maxn], inc[maxn], pref[maxn], tot = 0, cnt = 0, A[maxn * 4]; int n, dat[2][maxn * 4], ans[maxn]; struct Line { int x, op, id; bool operator<(const Line& rhs) { if (x == rhs.x) return op < rhs.op; return x < rhs.x; } }L[maxn * 3]; void add(int i, int x, int t) { while (i <= n) { dat[t][i] += x; i += i & (-i); } } int sum(int i, int t) { int ans = 0; while (i) { ans += dat[t][i]; i -= i & (-i); } return ans; } int compress(int* ar) { vector<int>xs; for (int i = 1; i <= cnt; i++) xs.push_back(ar[i]); sort(all(xs)); xs.erase(unique(all(xs)), xs.end()); for (int i = 1; i <= cnt; i++) A[i] = upper_bound(all(xs), A[i]) - xs.begin(); return xs.size(); } void solve() { for (int i = 1; i <= N; i++) A[++cnt] = p[i] + b[i], A[++cnt] = b[i] - p[i]; for (int i = 1; i <= M; i++) A[++cnt] = inc[i] + pref[i], A[++cnt] = pref[i] - inc[i]; n = compress(A); for (int i = 1; i <= N; i++) { L[++tot].id = i, L[tot].op = 0, L[tot].x = p[i]; L[++tot].id = i, L[tot].op = 2, L[tot].x = s[i]; } for (int i = 1; i <= M; i++) L[++tot].id = i, L[tot].op = 1, L[tot].x = inc[i]; sort(L + 1, L + tot + 1); for (int i = 1; i <= tot; i++) { if (L[i].op == 0) { add(A[L[i].id * 2 - 1], 1, 0); add(A[L[i].id * 2], 1, 1); } else if (L[i].op == 2) { add(A[L[i].id * 2 - 1], -1, 0); add(A[L[i].id * 2], -1, 1); } else ans[L[i].id] = sum(A[L[i].id * 2 - 1 + N * 2], 0) - sum(A[L[i].id * 2 + N * 2] - 1, 1); } for (int i = 1; i <= M; i++) cout << ans[i] << ' '; cout << endl; } int main() { IOS; cin >> N >> M; for (int i = 1; i <= N; i++) cin >> p[i]; for (int i = 1; i <= N; i++) cin >> s[i]; for (int i = 1; i <= N; i++) cin >> b[i]; for (int i = 1; i <= M; i++) cin >> inc[i]; for (int i = 1; i <= M; i++) cin >> pref[i]; solve(); return 0; }