Submission #44141023

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
    #define tout cout
    #include <bits/wida.h>
#endif
#define endl "\n"
#define int long long


struct BIT_2D {
    struct Compress {
        int n;
        vector<int> alls;
        
        Compress() {}
        
        void add(int x) {
            alls.emplace_back(x);
        }
        
        void init() {
            alls.emplace_back(numeric_limits<int>::max());
            sort(alls.begin(), alls.end());
            alls.erase(unique(alls.begin(), alls.end()), alls.end());
            this->n = alls.size();
        }
        
        int operator[](int x) { // 返回 x 元素的新下标
            return upper_bound(alls.begin(), alls.end(), x) - alls.begin();
        }
        
        int get(int x) { // 返回 x 元素的新下标
            return lower_bound(alls.begin(), alls.end(), x) - alls.begin();
        }
    };
    int n;
    vector<vector<int>> w;
    vector<pair<int, int>> ver;
    
    Compress row;
    vector<Compress> col;
    
    BIT_2D() {}
    void merge(int x, int y) {
        ver.emplace_back(x, y);
    }
    void init() {
        for (auto [x, y] : ver) { // 离散化横坐标
            row.add(x);
        }
        row.init();
        
        this->n = row.n;
        w.resize(n + 1);
        col.resize(n + 1);
        
        for (auto [x, y] : ver) { // 对每一行的纵坐标离散化，以此节约空间
            for (int i = row[x]; i <= n; i += i & -i) {
                col[i].add(y);
            }
        }
        
        for (int i = 1; i <= n; i++) {
            col[i].init();
            w[i].resize(col[i].n);
        }
    }
    
    void add(int x, int y, int k) {
        for (int i = row[x]; i <= n; i += i & -i) {
            for (int j = col[i][y]; j < col[i].n; j += j & -j) {
                w[i][j] += k;
            }
        }
    }
    void add(int x, int y, int X, int Y, int k) { // 区块修改：二维差分
        X++, Y++;
        add(x, y, k), add(X, y, -k);
        add(X, Y, k), add(x, Y, -k);
    }
    int ask(int x, int y) { // 单点查询
        int ans = 0;
        for (int i = row[x]; i; i -= i & -i) {
            for (int j = col[i][y]; j; j -= j & -j) {
                ans += w[i][j];
            }
        }
        return ans;
    }
    int ask(int x, int y, int X, int Y) { // 区块查询：二维前缀和
        x--, y--;
        return ask(X, Y) - ask(x, Y) - ask(X, y) + ask(x, y);
    }
    
    void debug() {
        for (int i = 1; i <= 20; i++) {
            for (int j = 1; j <= 20; j++) {
                cout << setw(3) << ask(i, j) << " ";
            }
            cout << endl;
        }
    }
};


signed main() {
    int n, m;
    cin >> n >> m;
    
    BIT_2D bit;
    vector<array<int, 5>> reg;
    for (int i = 1; i <= n; i++) {
        int x, y, d, w;
        cin >> x >> y >> d >> w;
        bit.merge(x, y);
        bit.merge(x, y + d + 1);
        bit.merge(x + d + 1, y);
        bit.merge(x + d + 1, y + d + 1);
        reg.push_back({x, y, x + d, y + d, w});
    }
    
    bit.init();
    
    for (auto [x, y, X, Y, w] : reg) { // 传入数据
        bit.add(x, y, X, Y, w);
    }
    
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        cout << bit.ask(x, y) << endl;
    }
}

int __OI_INIT__ = []() {
    ios::sync_with_stdio(0), cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(12);
    return 0;
}();

Submission Info

Judge Result