树状数组tle#7 只差0.06s
查看原帖
树状数组tle#7 只差0.06s
1048327
KANO07楼主2024/10/22 14:27

不懂为啥#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;
}

2024/10/22 14:27
加载中...