不懂为啥#7跑这么慢?
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using db = long double;
#define Finline __inline__ __attribute__((always_inline))
Finline char get_char() {
static char buf[200000001], *p1 = buf, *p2 = buf + fread(buf, 1, 200000000, stdin);
return p1 == p2 ? EOF : *p1++;
}
inline int read() {
int num = 0;
char c;
while ((c = get_char()) < 48)
;
while (num = num * 10 + c - 48, (c = get_char()) >= 48)
;
return num;
}
//------以上快读-------
const int N = 5e5 + 5;
const int M = 1e7;
int tr[M];
inline int lowbit(int x) {
return x & (-x);
}
inline void add(int x) {
for (int i = x; i <= M; i += lowbit(i)) tr[i]++;
}
inline int query(int x) {
int res = 0;
for (int i = x; i >= 1; i -= lowbit(i)) res += tr[i];
return res;
}
//-----树状数组-----
struct pair_hash {
template<class T1, class T2> std::size_t operator()(const std::pair<T1, T2>& pair) const {
auto hash1 = std::hash<T1>{}(pair.first);
auto hash2 = std::hash<T2>{}(pair.second);
return hash1 ^ hash2;
}
};
unordered_map<pll, ll, pair_hash> ask[N];
//-----哈希--------
pll v[N];
int q[N][4];
void solve() {
int n, m;
n = read(), m = read();
for (int i = 1; i <= n; i++) {
v[i].first = read();
v[i].second = read();
v[i].second++;
}
sort(v + 1, v + 1 + n);
for (int i = 1; i <= m; i++) {
int a, b, c, d;
a = read(), b = read(), c = read(), d = read();
b++, d++;
a = upper_bound(v + 1, v + 1 + n, pll{a, 0}) - v - 1;
c = upper_bound(v + 1, v + 1 + n, pll{c, INT_MAX}) - v - 1;
ask[a][{b, d}];
ask[c][{b, d}];
q[i][0] = a, q[i][1] = b, q[i][2] = c, q[i][3] = d;
}
for (int i = 1; i <= n; i++) {
add(v[i].second);
for (auto& [a, val] : ask[i]) {
auto& [x, y] = a;
val = query(y) - query(x - 1);
}
}
for (int i = 1; i <= m; i++) {
int y1 = q[i][1], y2 = q[i][3];
int x1 = q[i][0], x2 = q[i][2];
cout << ask[x2][{y1, y2}] - ask[x1][{y1, y2}] << endl;
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T = 1;
while (T--) {
solve();
}
return 0;
}