NOMURA Programming Contest 2022（AtCoder Beginner Contest 253）

F - Operations on a Matrix

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : $500$ points

### Problem Statement

We have an $N \times M$ matrix, whose elements are initially all $0$.

Process $Q$ given queries. Each query is in one of the following formats.

• 1 l r x : Add $x$ to every element in the $l$-th, $(l+1)$-th, $\ldots$, and $r$-th column.
• 2 i x: Replace every element in the $i$-th row with $x$.
• 3 i j: Print the $(i, j)$-th element.

### Constraints

• $1 \leq N, M, Q \leq 2 \times 10^5$
• Every query is in one of the formats listed in the Problem Statement.
• For each query in the format 1 l r x, $1 \leq l \leq r \leq M$ and $1 \leq x \leq 10^9$.
• For each query in the format 2 i x, $1 \leq i \leq N$ and $1 \leq x \leq 10^9$.
• For each query in the format 3 i j, $1 \leq i \leq N$ and $1 \leq j \leq M$.
• At least one query in the format 3 i j is given.
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

$N$ $M$ $Q$
$\mathrm{Query}_1$
$\vdots$
$\mathrm{Query}_Q$

$\mathrm{Query}_i$, which denotes the $i$-th query, is in one of the following formats:

$1$ $l$ $r$ $x$
$2$ $i$ $x$
$3$ $i$ $j$

### Output

For each query in the format 3 i j, print a single line containing the answer.

3 3 9
1 1 2 1
3 2 2
2 3 2
3 3 3
3 3 1
1 2 3 3
3 3 2
3 2 3
3 1 2

### Sample Output 1

1
2
2
5
3
4

The matrix transitions as follows.

$\begin{pmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{pmatrix} \rightarrow \begin{pmatrix} 1 & 1 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 0 \\ \end{pmatrix} \rightarrow \begin{pmatrix} 1 & 1 & 0 \\ 1 & 1 & 0 \\ 2 & 2 & 2 \\ \end{pmatrix} \rightarrow \begin{pmatrix} 1 & 4 & 3 \\ 1 & 4 & 3 \\ 2 & 5 & 5 \\ \end{pmatrix}$

1 1 10
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
3 1 1

9000000000

10 10 10
1 1 8 5
2 2 6
3 2 1
3 4 7
1 5 9 7
3 3 2
3 2 8
2 8 10
3 8 8
3 1 10

6
5
5
13
10
0

### 我的笔记

latest 数组第 $i$ 位代表第 $i$ 行最后一次替换操作。

vis vector 数组的第 $i$ 个 vector 容器储存第 $i$ 次替换操作会影响到的查询操作的序号。

ans 数组第 $i$ 位代表第 $i$ 次操作的答案。

• 首先读入数据

• 当为更新操作的时候，只读入。
• 当为替换操作的时候，更新矩阵对应行的 最后一次替换操作 的操作序号。
• 当为查询操作的时候，将该 查询操作的操作序号 加入到 vis 数组中的 最后一次替换操作的序号 的项中。

• 然后开始计算

• 如果是更新操作，我们用树状数组维护列的更新情况，树状数组储存前缀和，这样每次只需要修改首尾两个元素，查询时输出求和即可。
• 如果是替换操作，我们通过读入时创建的 vis 数组，可以知道这次替换操作会影响到哪几次的查询操作，然后将有影响的查询操作的 ans 设置为 该次替换的替换值 $-$ 此时此列的更新值。之所以要减去 此时此列的更新值，是因为该次替换覆盖了之前所有的更新操作，减去的这个值会与查询操作加上的值相消，下面就是说的这个。
• 如果是查询操作，我们将 ans 对应位 $+$ 此时此列的更新值，与上面减去的更新值相消后，便是从最后一次替换到现在的更新值。

### 源码

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int MAXN = 2e5 + 10;
int N, M, Q;
struct DATA
{
int op, a, b, c;
} q[MAXN];
int latest[MAXN];
int ans[MAXN];
vector<int> vis[MAXN];

int Fenwick_Tree[MAXN];
void update(int pos, int val)
{
for (int i = pos; i < MAXN; i += i & -i)
Fenwick_Tree[i] += val;
}
int query(int pos)
{
int ans = 0;
for (int i = pos; i; i -= i & -i)
ans += Fenwick_Tree[i];
return ans;
}

signed main()
{
cin >> N >> M >> Q;
for (int i = 1; i <= Q; i++)
{
cin >> q[i].op;
if (q[i].op == 1)
{
cin >> q[i].a >> q[i].b >> q[i].c;
}
else if (q[i].op == 2)
{
cin >> q[i].a >> q[i].b;
latest[q[i].a] = i;
}
else
{
cin >> q[i].a >> q[i].b;
vis[latest[q[i].a]].push_back(i);
}
}
for (int i = 1; i <= Q; i++)
{
if (q[i].op == 1)
{
update(q[i].a, q[i].c);
update(q[i].b + 1, -q[i].c);
}
else if (q[i].op == 2)
{
for (int v : vis[i])
ans[v] = q[i].b - query(q[v].b);
}
else
{
ans[i] += query(q[i].b);
cout << ans[i] << endl;
}
}
return 0;
}