Atcoder beginer contest 253 F - operations on a matrix / / tree array

Subject portal ：F - Operations on a Matrix (atcoder.jp)

The question ：

Give me a N*M Zero matrix of size , as well as Q operations . operation 1（l,r,x）： about [l,r] Add... To each column in the interval x; operation 2（i,x）： For the first i That's ok , Replace with x; operation 3（i,j）： Query matrix page i That's ok , The first j Value of column element .

N、M、Q All sizes are 2E5.

Ideas ： Tree array

First of all, consider no operation 2 The situation of , Then it is easy to use the tree array to realize the interval addition of columns and single point query .

When there is an operation 2 when , For operation 3 Query for ： The last operation of this line 2 The line modification value of is recorded as x, From the last operation 2 All... To this operation 1 The added value of the operation column is recorded as sum2, Then the output answer is x + sum2. All... From the beginning to this operation 1 The added value of the operation column is recorded as sum, From the beginning to the last operation 2 The column added value of is recorded as sum1, So there are sum2 = sum - sum1, The answer is ：x + sum - sum1. You can query offline .

Code reference ：

#include <bits/stdc++.h>
#define LL long long
#define lowbit(x) (x & -x)
using namespace std;

const int N = 200010;

int n, m, Q, last[N];
LL tr[N], ans[N];
vector<int> v[N];

struct query {
    int op, a, b, c;
} q[N];

void add(int x, int c)
{
    for(int i = x; i <= m; i += lowbit(i)) tr[i] += c;
}

LL sum(int x)
{
    LL res = 0;
    for(int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

int main()
{
    cin >> n >> m >> Q;

    for(int i = 1; i <= Q; i++) {
        scanf("%d%d%d", &q[i].op, &q[i].a, &q[i].b);
        if(q[i].op == 1) scanf("%d", &q[i].c);
        else if(q[i].op == 2) last[q[i].a] = i;
        else v[last[q[i].a]].push_back(i);
    }

    for(int i = 1; i <= Q; i++) {
        if(q[i].op == 1) add(q[i].a, q[i].c), add(q[i].b + 1, -q[i].c);
        else if(q[i].op == 2) for(auto item : v[i]) ans[item] = q[i].b - sum(q[item].b);  
        else printf("%lld\n", ans[i] + sum(q[i].b));
    }

    return 0;
}