abc253 F – Operations on a Matrix

题意：

\(n\times m\) 矩阵，初始全零。\(q\) 次操作：

• 1 l r x 令 \([l,r]\) 列的所有元素 \(+x\)
• 2 i x 令第 \(i\) 行的所有元素 \(=x\)
• 3 i j 输出位于 \((i,j)\) 的元素

\(n,m,q\le 2e5\)

思路：

Sir, this way: https://www.cnblogs.com/jakon/p/16323545.html

const signed N = 2e5 + 5;
int n, m, q, las[N];
struct {
    int id, l, r, x, i, j;
    vector<int> ve;
    ll ans;
} Q[N];

ll tr[N];
int lowbit(int x) {return x&-x; }
void add(int p, int x) {for(;p<=m;p+=lowbit(p))tr[p]+=x; }
ll ask(int p) {ll s=0;for(;p>0;p-=lowbit(p))s+=tr[p];return s; }

void sol() {
    cin >> n >> m >> q;
    for(int i = 1; i <= q; i++) {
        cin >> Q[i].id;
        if(Q[i].id == 1)
            cin >> Q[i].l >> Q[i].r >> Q[i].x;
        if(Q[i].id == 2) {
            cin >> Q[i].i >> Q[i].x;
            las[Q[i].i] = i;
        }
        if(Q[i].id == 3) {
            cin >> Q[i].i >> Q[i].j;
            Q[i].ans = Q[las[Q[i].i]].x;
            Q[las[Q[i].i]].ve.push_back(i);
        }
    }
    for(int i = 1; i <= q; i++) {
        if(Q[i].id == 1)
            add(Q[i].l, Q[i].x), add(Q[i].r + 1, -Q[i].x);
        if(Q[i].id == 2)
            for(int t : Q[i].ve)
                Q[t].ans -= ask(Q[t].j);
        if(Q[i].id == 3)
            cout << Q[i].ans + ask(Q[i].j) << '\n';
    }
}