Submission #35597285

---

Source Code Expand

#include<iostream>
#include<vector>
using namespace std;

const int SIZE = 1 << 20;
const int len = 1 << 19;
int n, m, q;
int query[200010][4];
vector<pair<int, int>> v[200010];
long long tree[SIZE];
long long lazy[SIZE];
long long ans[200010];
int cnt;

void propagate(int idx)
{
    if(idx < len)
    {
        lazy[2 * idx] += lazy[idx];
        lazy[2 * idx + 1] += lazy[idx];
    }
    tree[idx] += lazy[idx];
    lazy[idx] = 0;
}

void update(int idx, int s, int e, int ts, int te, long long v)
{
    int mid;
    
    propagate(idx);
    
    if(s > te || e < ts) return;
    else if(ts <= s && e <= te)
    {
        lazy[idx] = v;
        propagate(idx);
        return;
    }
    
    mid = (s + e) / 2;
    
    update(2 * idx, s, mid, ts, te, v);
    update(2 * idx + 1, mid + 1, e, ts, te, v);
}

long long get(int idx, int s, int e, int ts, int te)
{
    int mid;
    
    propagate(idx);
    
    if(s > te || e < ts) return 0;
    else if(ts <= s && e <= te) return tree[idx];
    
    mid = (s + e) / 2;
    
    return get(2 * idx, s, mid, ts, te) + get(2 * idx + 1, mid + 1, e, ts, te);
}

int main()
{
    int i, j;
    
    cin >> n >> m >> q;
    for(i = 0; i < q; i++)
    {
        for(j = 0; j < 3; j++)
        {
            cin >> query[i][j];
        }
        if(query[i][0] == 1) cin >> query[i][3];
    }
    
    for(i = q - 1; i >= 0; i--)
    {
        if(query[i][0] == 1) update(1, 0, len - 1, query[i][1], query[i][2], query[i][3]);
        else if(query[i][0] == 2)
        {
            for(j = 0; j < v[query[i][1]].size(); j++)
            {
                ans[v[query[i][1]][j].second] += query[i][2] + get(1, 0, len - 1, v[query[i][1]][j].first, v[query[i][1]][j].first);
            }
            v[query[i][1]].clear();
        }
        else
        {
            v[query[i][1]].push_back(make_pair(query[i][2], cnt));
            ans[cnt] -= get(1, 0, len - 1, query[i][2], query[i][2]);
            cnt++;
        }
    }
    
    for(i = 1; i <= n; i++)
    {
        for(j = 0; j < v[i].size(); j++)
        {
            ans[v[i][j].second] += get(1, 0, len - 1, v[i][j].first, v[i][j].first);
        }
    }
    
    for(i = cnt - 1; i >= 0; i--)
    {
        cout << ans[i] << '\n';
    }
}

Submission Info

Judge Result