Submission

Score: 0

User: Dormon

Problemset: ฮีโร่และมอนสเตอร์

Language: cpp

Time: 0.585 second

Submitted On: 2025-12-08 12:24:09

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using ll = long long;

struct sparse_segment_tree {
    struct Node {
        ll val = 0;
        Node *l, *r;
        Node() : val(0), l(nullptr), r(nullptr) {}
    };
    int n;
    Node *root = new Node();
    sparse_segment_tree(int n) : n(n) {}
    void push(Node *curr){
        if (curr->l == nullptr) curr->l = new Node();
        if (curr->r == nullptr) curr->r = new Node();
    }
    void pull(Node *curr){
        curr->val = curr->l->val + curr->r->val;
    }
    void update(Node *curr, int l, int r, int idx, ll val){
        push(curr);
        if (l == r){
            curr->val += val;
            return ;
        }
        int mid = (l + r) / 2;
        if (idx <= mid) update(curr->l, l, mid, idx, val);
        else update(curr->r, mid + 1, r, idx, val);
        pull(curr);
    }
    ll query(Node *curr, int l, int r, int lb, int ub){
        push(curr);
        if (lb <= l && r <= ub) return curr->val;
        if (r < lb || l > ub) return 0;
        int mid = (l + r) / 2;
        return query(curr->l, l, mid, lb, ub) + query(curr->r, mid + 1, r, lb, ub);
    }
    void update(ll idx, ll val){
        update(root, 1, n, idx, val);
    }
    ll query(ll l, ll r){
        return query(root, 1, n, l, r);
    }
    void print(Node *curr, int l, int r){
        if (curr == nullptr) return ;
        cout << l << ' ' << r << " : " << curr->val << ' ' << '\n';
        int mid = (l + r) / 2;
        print(curr->l, l, mid); print(curr->r, mid + 1, r);
    }
    void print(){
        print(root, 1, n);
        cout << '\n';
    }
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    vector<ll> v(n);
    sparse_segment_tree seg(1e9 + 2);
    for (auto &e:v) cin >> e;
    for (int i = 1;i <= m;i++){
        ll a, b;
        cin >> a >> b;
        seg.update(a, b);
    }
    for (auto e:v) cout << seg.query(1, e) << '\n';
}