题目描述

难度分:$1756$

输入$n,m,q(1 \leq n,m,q \leq 2 \times 10^5)$。
有一个$n$行$m$列的矩阵，初始值均为$0$。

然后输入$q$个操作/询问，格式如下：

1. 1 L R x：把矩阵第$L,L+1,…,R$列的所有元素都加上$x(1 \leq x \leq 10^9)$。
2. 2 i x：把矩阵第$i$行的元素全部替换为$x(1 \leq x \leq 10^9)$。
3. 3 i j：输出矩阵第$i$行第$j$列的元素值。

矩阵行列编号均从$1$开始。

输入样例$1$

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

输出样例$1$

1
2
2
5
3
4

输入样例$2$

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

输出样例$2$

9000000000

输入样例$3$

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

输出样例$3$

6
5
5
13
10
0

算法

离线+树状数组

刚开始题读假了，没注意到$n \leq 200000$，$m \leq 200000$，上了二维线段树，结果一直RE。后来反应过来之后想了好久也没想到什么数据结构可以无脑做，但是离线做的话有点思路。

我们可以维护一个长度为$O(m)$的树状数组$BIT$，用来存操作$1$作用下每列的和。本题是区间加，单点查询，因此树状数组维护的是一个差分数组。

先遍历一遍所有的询问$queries$，对于每个询问$index$，当遇到操作$2$时维护一个$last$数组，$last[i]=index$表示第$i$行在第$index$条询问时做了一次操作$2$。当遇到操作$3$时，维护一个二维数组$path$，将$index$追加到$path[last[i]]$中，这样一来$path[last[i]]$中就是第$i$行操作$2$（询问编号是$last[i]$）后面所跟上的操作$3$编号。

最后再遍历一遍$queries$数组求答案：

1. 如果遇到的是操作$1$，直接在树状数组实现的差分数组$BIT$上进行区间加法，在$[l,r]$上加$x$。
2. 如果遇到的是操作$2$，遍历$index$后面紧接着的操作$3$（即$path[index]$）编号$idx$，把$x-BIT.query(queries[idx].j)$存入到$ans[idx]$中。
3. 如果遇到的是操作$3$，输出$BIT.query(j)+ans[index]$。前一项是迄今为止所有操作$1$作用在单元格$(i,j)$上的结果，第二项中有最近一次的$x$，所以我们只需要把“最近一次操作$2$之前所有操作的贡献”减去就能得到答案。而这个贡献就是情况$2$中$x$后面减去的那一项，这是因为在真正遍历到这个操作$3$之前，通过情况$2$遍历得到的$BIT.query(queries[idx].j)$值只是那次操作$2$之前所有操作的贡献。

复杂度分析

时间复杂度

遍历$queries$的时间复杂度为$O(q)$。在遍历所有询问的内部，也存在遍历$path$数组的操作，$path$数组中每个元素只会被遍历一次，元素数量是$O(q)$级别。而处理每条询问的过程中，会对长度在$O(m)$级别的树状数组进行区间加和单点查询操作，时间复杂度为$O(log_2m)$。

综上，整个算法的时间复杂度为$O(qlog_2m)$。

空间复杂度

$ans$数组、$path$数组、$last$数组的空间消耗均为$O(q)$，树状数组的空间消耗为$O(m)$。因此，整个算法的额外空间复杂度为$O(m+q)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 200010;
int n, m, q, last[N];
LL ans[N];
vector<int> path[N];

class Fenwick {
public:
    explicit Fenwick(int n): sums_(n + 1) {}

    int lowbit(int x) {
        return x&-x;
    }

    void add(int idx, int val) {
        for(; idx < sums_.size(); idx += lowbit(idx)) {
            sums_[idx] += val;
        }
    }

    LL query(int idx) {
        LL ans = 0;
        for(; idx > 0; idx -= lowbit(idx)) {
            ans += sums_[idx];
        }
        return ans;
    }

    LL query(int left, int right) {
        return query(right) - query(left - 1);
    }

private:
    vector<LL> sums_;
};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> q;
    vector<vector<int>> queries;
    queries.push_back({});
    for(int index = 1; index <= q; index++) {
        int op;
        cin >> op;
        if(op == 1) {
            int l, r, x;
            cin >> l >> r >> x;
            queries.push_back({op, l, r, x});
        }else if(op == 2) {
            int i, x;
            cin >> i >> x;
            last[i] = index;
            queries.push_back({op, i, x});
        }else {
            int i, j;
            cin >> i >> j;
            queries.push_back({op, i, j});
            path[last[i]].push_back(index);
        }
    }
    Fenwick bit(m + 5);
    for(int index = 1; index <= q; index++) {
        int op = queries[index][0];
        if(op == 1) {
            int l = queries[index][1], r = queries[index][2], x = queries[index][3];
            bit.add(l, x);
            bit.add(r + 1, -x);
        }else if(op == 2) {
            int i = queries[index][1], x = queries[index][2];
            for(int idx: path[index]) {
                ans[idx] = x - bit.query(queries[idx][2]);
            }
        }else {
            int i = queries[index][1], j = queries[index][2];
            cout << ans[index] + bit.query(j) << endl;
        }
    }
    return 0;
}