[ABC253F] Operations on a Matrix Solution

更好的阅读体验戳此进入

题面

存在 $n$$n$ 行 $m$$m$ 列的矩阵，给定 $q$$q$ 次操作，有 $3$$3$ 种格式。

• 1 l r x：将 $[l,r]$$[l, r]$ 列的所有元素全部加上 $x$$x$。
• 2 i x：将第 $i$$i$ 行的元素全部变为 $x$$x$。
• 3 i j：输出矩阵 $(i,j)$$(i, j)$ 位置的元素值。

Solution

感觉还算是一道细节不少的题。

首先这道题的做法不少，主流的就是类似二位偏序维护，或者写一个区间修改的主席树。

这里主要说一下用 BIT 维护的方法。

首先不难想到，$2$$2$ 操作会覆盖掉前面所有的对其有影响的 $1$$1$ 操作。然后 $1$$1$ 操作是区间修改列，$2$$2$ 操作是单点推平行。所以考虑离线，然后对于每个查询，令其序号为 $r$$r$，有行 $x$$x$ 列 $y$$y$，我们要找到在其之前的上一个推平 $x$$x$ 行，令其的操作序号为 $l$$l$，那么我们就需要对这个答案初始设为那次推平的值，然后加上 $[l,r]$$[l, r]$ 之间的所有的对于 $y$$y$ 列的操作。

思路就是这样，维护的方式还是有些高妙的。先考虑离线一遍，然后维护对于每个查询的上一次对应的推平，同时维护该查询的初始值，然后在需要减去的位置开个 basic_string 插进去需要减的序号。然后我们考虑会有一次区间的查询，用 BIT 和前缀和维护，再遍历一次操作，先将前缀加起来，然后减去的那个前缀就在我们第二次遍历的时候通过遍历对应的 basic_string 而减去。然后最后跑一遍输出答案即可。

Code

xxxxxxxxxx
93
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
template < typename T = int >
23
inline T read(void);
24

25
int N, M, Q;
26
int lst[210000], pos[210000];
27
ll ans[210000];
28
struct Query{int opt; int a, b, c;}qs[210000];
29
basic_string < int > del[210000];
30

31
class BIT{
32
private:
33
    ll tr[210000];
34
public:
35
    int lowbit(int x){return x & -x;}
36
    void Modify(int x, int v){while(x <= M)tr[x] += v, x += lowbit(x);}
37
    ll Query(int x){ll ret(0); while(x)ret += tr[x], x -= lowbit(x); return ret;}
38
    void ModifyRange(int l, int r, ll v){Modify(l, v), Modify(r + 1, -v);}
39
}bit;
40

41
int main(){
42
    // freopen("test_05.txt", "r", stdin);
43
    // freopen("out.txt", "w", stdout);
44
    N = read(), M = read(), Q = read();
45
    for(int i = 1; i <= Q; ++i){
46
        int opt = read();
47
        switch(opt){
48
            case 1:{
49
                int l = read(), r = read(), v = read(); qs[i] = Query{opt, l, r, v};
50
                break;
51
            }
52
            case 2:{
53
                int p = read(), v = read(); qs[i] = Query{opt, p, v};
54
                pos[p] = i;
55
                break;
56
            }
57
            case 3:{
58
                int x = read(), y = read(); qs[i] = Query{opt, x, y};
59
                ans[i] = qs[pos[x]].b;
60
                del[pos[x]] += i;
61
                break;
62
            }
63
            default: break;
64
        }
65
    }
66
    for(int i = 1; i <= Q; ++i){
67
        switch(qs[i].opt){
68
            case 1:{bit.ModifyRange(qs[i].a, qs[i].b, qs[i].c); break;}
69
            case 2:{for(auto p : del[i])ans[p] -= bit.Query(qs[p].b); break;}
70
            case 3:{ans[i] += bit.Query(qs[i].b); break;}
71
            default: break;
72
        }
73
    }
74
    for(int i = 1; i <= Q; ++i)if(qs[i].opt == 3)printf("%lld\n", ans[i]);
75
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
76
    return 0;
77
}
78

79
template < typename T >
80
inline T read(void){
81
    T ret(0);
82
    int flag(1);
83
    char c = getchar();
84
    while(c != '-' && !isdigit(c))c = getchar();
85
    if(c == '-')flag = -1, c = getchar();
86
    while(isdigit(c)){
87
        ret *= 10;
88
        ret += int(c - '0');
89
        c = getchar();
90
    }
91
    ret *= flag;
92
    return ret;
93
}

UPD

update-2022_12_05 初稿