AtCoder Beginner Contest 256 Solution

更好的阅读体验戳此进入

题面链接

题面 Luogu 链接

ab 跳了

cd 简单说一下做法，比较水就不实现了

[ABC256C] Filling 3x3 array

Solution

$9$$9$ 个未知量，$6$$6$ 个等式，存在一组线性相关的等式，这玩意实际上就是个简化版的高斯消元，所以考虑枚举四个数即可。复杂度 $O(v^4)$$O(v^4)$。

[ABC256D] Union of Interval

Solution

最开始想着套个 bitset 水过去，不过似乎比较难搞。随便搞个 ODT 或者 线段树 就能水过去，或者左端点排个序讨论一下也行。

[ABC256E] Takahashi's Anguish

题面

存在 $n$$n$ 个人，你需要确定一个序列 $P_n$$P_n$ 表示这 $n$$n$ 个人的排列，对于每个人，第 $i$$i$ 个人有且仅有一个 $x_i$$x_i$，表示不喜欢 $x_i$$x_i$ 站在 $i$$i$ 的前面，若 $x_i$$x_i$ 站在 $i$$i$ 的前面则会产生 $c_i$$c_i$ 的不愉悦值，你需要确定排列以最小化不愉悦值之和，求最小值。

Solution

这道题想到方法之后就很简单了，是一道图论建模题。考虑将不喜欢的关系抽象成一条有向边，不难发现每个点都有且仅有一条出边，则最后形成的图在形态上一定类似一个基环树森林，或者说在形成的图中每一个连通块内最多含有一个环。

不难想到对于无环的一定有合法方案使得每一个点都不会有不喜欢的在其之前，对于环上的则一定至少需要破坏一条环上的边。于是我们跑一个类似拓朴排序的东西即可，对于无环的直接丢弃，有环的在环上找到边权最小的一条边保留即可。

Code

xxxxxxxxxx
86
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
struct Edge{
26
    Edge *nxt;
27
    int to;
28
    int val;
29
    OPNEW;
30
}ed[210000];
31
ROPNEW(ed);
32
Edge* head[210000];
33

34
int N;
35
bitset < 210000 > vis;
36
int ind[210000];
37
ll ans(0);
38

39
int main(){
40
    N = read();
41
    for(int i = 1; i <= N; ++i){
42
        int s = i, t = read();
43
        head[s] = new Edge{head[s], t};
44
        ++ind[t];
45
    }for(int i = 1; i <= N; ++i)head[i]->val = read();
46
    queue < int > cur;
47
    for(int i = 1; i <= N; ++i)if(!ind[i])vis[i] = true, cur.push(i);
48
    while(!cur.empty()){
49
        int tp = cur.front(); cur.pop();
50
        for(auto i = head[tp]; i; i = i->nxt){
51
            --ind[SON];
52
            if(!ind[SON])vis[SON] = true, cur.push(SON);
53
        }
54
    }
55
    for(int i = 1; i <= N; ++i){
56
        if(!vis[i]){
57
            int mn(INT_MAX);
58
            vis[i] = true;
59
            auto cur = head[i];
60
            while(cur->to != i){
61
                vis[cur->to] = true;
62
                mn = min(mn, cur->val);
63
                cur = head[cur->to];
64
            }mn = min(mn, cur->val);
65
            ans += mn;
66
        }
67
    }printf("%lld\n", ans);
68
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
69
    return 0;
70
}
71

72
template < typename T >
73
inline T read(void){
74
    T ret(0);
75
    int flag(1);
76
    char c = getchar();
77
    while(c != '-' && !isdigit(c))c = getchar();
78
    if(c == '-')flag = -1, c = getchar();
79
    while(isdigit(c)){
80
        ret *= 10;
81
        ret += int(c - '0');
82
        c = getchar();
83
    }
84
    ret *= flag;
85
    return ret;
86
}

[ABC256F] Cumulative Cumulative Cumulative Sum

题面

给定序列 $A_n$$A_n$，定义 $B_i=\sum _{j=1}^j{A}_j,C_i=\sum _{j=1}^i{B}_j,D_i=\sum _{j=1}^i{C}_j$$B_i = \sum_{j = 1}^j A_j, C_i = \sum_{j = 1}^i B_j, D_i = \sum_{j = 1}^i C_j$。存在两种操作：

1 x v：$A_x\leftarrow v$$A_x \leftarrow v$。

2 x：查询 $D_{x}mod998244353$$D_x \bmod{998244353}$。

Solution

就是维护一个高维前缀和，也是经典套路，无脑推式子：

于是可以将 $D_x$$D_x$ 通过等差数列求和表示为：

然后我们可以考虑将 $(1+x-(i-1))\times (x-(i-1))a_i$$(1 + x - (i - 1)) \times (x - (i - 1))a_i$ 化简，似乎就是尽量将与询问有关的 $x$$x$ 和前缀和抽离开，这样才可以便于用数据结构维护。即：

此时我们发现，对于每次询问 $x$$x$ 已知，只需要用数据结构维护 $a_i$$a_i$，$i{a}_i$$ia_i$，$(i^2-3i)a_i$$(i^2 - 3i)a_i$ 的前缀和即可 $O(\log n)$$O(\log n)$ 查询，并且支持单点修改。记得查询之后乘个 $2$$2$ 的逆元。最终复杂度 $O((n+q)\log n)$$O((n + q) \log n)$，可以通过。

Code

xxxxxxxxxx
90
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
#define MOD (998244353ll)
23

24
template < typename T = int >
25
inline T read(void);
26

27
int N, Q;
28
ll A[210000];
29

30
ll qpow(ll a, ll b){
31
    ll ret(1), mul(a);
32
    while(b){
33
        if(b & 1)ret = ret * mul % MOD;
34
        b >>= 1;
35
        mul = mul * mul % MOD;
36
    }return ret;
37
}
38

39
class BIT{
40
private:
41
    ll tr[210000];
42
public:
43
    int lowbit(int x){return x & -x;}
44
    void Modify(int x, ll v){while(x <= N)(tr[x] += v + MOD) %= MOD, x += lowbit(x);}
45
    ll Query(int x){ll ret(0); while(x)(ret += tr[x]) %= MOD, x -= lowbit(x); return ret;}
46
}bit1, bit2, bit3;
47

48
int main(){
49
    const ll inv2 = qpow(2, MOD - 2);
50
    N = read(), Q = read();
51
    for(int i = 1; i <= N; ++i)
52
        A[i] = read(),
53
        bit1.Modify(i, A[i]),
54
        bit2.Modify(i, i * A[i] % MOD),
55
        bit3.Modify(i, ((ll)i * i % MOD - 3ll * i % MOD + MOD) % MOD * A[i] % MOD);
56
    while(Q--){
57
        int opt = read();
58
        if(opt == 1){
59
            int x = read(); ll v = read();
60
            bit1.Modify(x, (v - A[x] + MOD) % MOD),
61
            bit2.Modify(x, x * ((v - A[x] + MOD) % MOD) % MOD),
62
            bit3.Modify(x, ((ll)x * x % MOD - 3ll * x % MOD + MOD) % MOD * ((v - A[x] + MOD) % MOD) % MOD);
63
            A[x] = v;
64
        }else{
65
            ll x = read();
66
            ll ret = (x * x % MOD + 3ll * x % MOD + 2) % MOD * bit1.Query(x) % MOD;
67
            (ret += (-2ll * x + MOD) % MOD * bit2.Query(x) % MOD) %= MOD;
68
            (ret += bit3.Query(x)) %= MOD;
69
            printf("%lld\n", ret * inv2 % MOD);
70
        }
71
    }
72
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
73
    return 0;
74
}
75

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

[ABC256G] Black and White Stones

题面

你现在有一个正 $n$$n$ 边形 , 边长为 $d$$d$。从顶点开始，你每个长度 $1$$1$ 放一个石子，白色或者黑色。换句话说，每条边上有 $d+1$$d+1$ 个石子，相邻两边公用一个石子。

请问有多少种方案，使得所有边上的白色石子数量相同。对 $998244353$$998244353$ 取模。

$n\le {10}^{12}$$n \le 10^{12}$，$d\le {10}^4$$d\le 10^4$。注意 $n$$n$ 的范围。

Solution

令 $dp(i,0/1,0/1)$$dp(i, 0 / 1, 0 / 1)$ 表示考虑前 $i$$i$ 条边，开头为白色或黑色，结尾为白色或黑色的方案数，可以额外令 $G(0/1,0/1)$$G(0 / 1, 0 / 1)$ 表示一条边时放石子的方案数，转移显然，枚举每条边黑色点数共有 $[0,d+1]$$[0, d + 1]$，处理答案后求和，然后矩阵快速幂优化一下即可。较为简单，具体算法看代码即可。

Code

xxxxxxxxxx
105
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
#define MOD (998244353ll)
23
#define A(x, y) (a.val[x][y])
24
#define B(x, y) (b.val[x][y])
25

26
template < typename T = int >
27
inline T read(void);
28

29
ll ans(0);
30
ll N, D;
31
ll fact[11000], inv[11000];
32

33
class Matrix2{
34
private:
35
public:
36
    ll val[2][2];
37
    Matrix2(void) = default;
38
    Matrix2(ll v11, ll v12, ll v21, ll v22){
39
        val[0][0] = v11, val[0][1] = v12, val[1][0] = v21, val[1][1] = v22;
40
    }
41
    friend const Matrix2 operator * (const Matrix2 &a, const Matrix2 &b){
42
        return Matrix2(
43
            (A(0, 0) * B(0, 0) % MOD + A(0, 1) * B(1, 0) % MOD) % MOD,
44
            (A(0, 0) * B(0, 1) % MOD + A(0, 1) * B(1, 1) % MOD) % MOD,
45
            (A(1, 0) * B(0, 0) % MOD + A(1, 1) * B(1, 0) % MOD) % MOD,
46
            (A(1, 0) * B(0, 1) % MOD + A(1, 1) * B(1, 1) % MOD) % MOD
47
        );
48
    }
49
    friend const Matrix2 operator ^ (const Matrix2 &a, ll b){
50
        Matrix2 ret(1, 0, 0, 1), mul(a);
51
        while(b){
52
            if(b & 1)ret = ret * mul;
53
            b >>= 1;
54
            mul = mul * mul;
55
        }return ret;
56
    }
57
}G;
58

59
ll qpow(ll a, ll b){
60
    ll ret(1), mul(a);
61
    while(b){
62
        if(b & 1)ret = ret * mul % MOD;
63
        b >>= 1;
64
        mul = mul * mul % MOD;
65
    }return ret;
66
}
67
void Init(void){
68
    fact[0] = 1;
69
    for(int i = 1; i <= 10100; ++i)fact[i] = fact[i - 1] * i % MOD;
70
    inv[10100] = qpow(fact[10100], MOD - 2);
71
    for(int i = 10099; i >= 0; --i)inv[i] = inv[i + 1] * (i + 1) % MOD;
72
}
73
ll GetC(int n, int m){
74
    if(m > n || n < 0 || m < 0)return 0;
75
    return fact[n] * inv[m] % MOD * inv[n - m] % MOD;
76
}
77

78
int main(){Init();
79
    N = read < ll >(), D = read();
80
    for(int k = 0; k <= D + 1; ++k){
81
        G = Matrix2(GetC(D - 1, k - 2), GetC(D - 1, k - 1), GetC(D - 1, k - 1), GetC(D - 1, k));
82
        auto ret = G ^ N;
83
        (ans += ret.val[0][0] + ret.val[1][1]) %= MOD;
84
        // printf("val: %lld, %lld, %lld, %lld\n", G.val[0][0], G.val[0][1], G.val[1][0], G.val[1][1]);
85
    }
86
    printf("%lld\n", ans);
87
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
88
    return 0;
89
}
90

91
template < typename T >
92
inline T read(void){
93
    T ret(0);
94
    int flag(1);
95
    char c = getchar();
96
    while(c != '-' && !isdigit(c))c = getchar();
97
    if(c == '-')flag = -1, c = getchar();
98
    while(isdigit(c)){
99
        ret *= 10;
100
        ret += int(c - '0');
101
        c = getchar();
102
    }
103
    ret *= flag;
104
    return ret;
105
}

[ABC256Ex] I like Query Problem

题面

给定 $n,q$$n, q$，和序列 $a_n$$a_n$，给定 $q$$q$ 次操作，有三种：

1 L R x：对于 $[L,R]$$[L, R]$ 内的所有 $i$$i$ 进行 $a_i\leftarrow \lfloor {\displaystyle \frac{a_i}{x}}\rfloor$$a_i \leftarrow \lfloor \dfrac{a_i}{x} \rfloor$。

2 L R y：区间推平 $[L,R]$$[L, R]$ 为 $y$$y$。

3 L R：输出 $\sum _{i=L}^R{a}_i$$\sum_{i = L}^R a_i$。

Solution

显然势能线段树，好像不是很难写。大概就是在一般的线段树基础上维护一个区间数是否均相同的标记，然后区间整除的时候直接通过这个实现 lazytag，这个复杂度经过一系列分析总之最后就是 $O(n{\log }^{2}n)$$O(n \log^2 n)$，实现起来很容易，代码也很短，不过，这太不优雅了！

有区间推平操作，不难想到 ODT，显然会被卡，于是想到一种优化：

考虑这个的时候首先要知道一点语法知识，即对于 set 它是不同于一般的线性结构如 basic_string 的，一般的线性结构当插入删除时若改变 capacity 的话指针就会失效，但当在 set 中插入或删除元素的时候，对于非被删数元素的迭代器、指针和引用等都是不会失效的，用 cppreference 的话来说就是：

No iterators or references are invalidated.

众所周知，我们一般通过对变量的 mutable 修饰以使其可以在 set 中被修改，且按照 l 排序，所以这里我们可以将 r 也修饰为 mutable，这样的话我们便可以很方便的 $O(1)$$O(1)$ 延申区间而不损失重构所需的 $O(\log )$$O(\log)$，此时考虑，因为我们的 $1$$1$ 操作中 $x\ge 2$$x \ge 2$，所以显然对于一个数如果不推平为其它数的时候最多 $\log$$\log$ 次就会变为 $0$$0$，所以我们在维护 $1$$1$ 操作时是可以同时将所有已经为 $0$$0$ 的数合并，这样可以有效减少块数，此时似乎对于 $1$$1$ 和 $2$$2$ 操作复杂度就已经正确了，不过如果我在每 $\log$$\log$ 次之后就重新推平满，这样复杂度似乎大概可能会被卡？？不是很确定。

然后这样交上去会获得 $28/30$$28 / 30$ 的好成绩，不过依然会 T，也不难想到，我们直接拉满查询这个东西就退化成 $O(nq)$$O(nq)$ 的了。对于这个我最初的思路是，每当修改后再遇到一个 $3$$3$ 操作就重新建立一棵线段树维护所有数的值，这样在这次查询接着的所有查询就都是 $O(\log n)$$O(\log n)$ 的了，这样应该可以有效的水过一些构造的数据，当然卡的方法也很简单，只要在每次查询之间增加一次微小扰动的修改，但是这样每次都会重新建整棵树，最后复杂度还会退化为 ${\displaystyle \frac{1}{2}}$$\dfrac{1}{2}$ 常数的 $O(nq)$$O(nq)$。但是，经过下载数据点发现，T 掉的两个数据并没有如此设计，而是完全询问拉满，也就是说理论上这样实现之后是可以通过这道题的，估计出题人也没想到这种奇怪的做法。。。

但是我们可以尝试扩展这种做法，不难想到刚才说的做法复杂度主要浪费在了修改时只修改了一部分，而不需要整棵树重建，所以我们可以尝试在这里优化一下。不难想到，对于一般的线段树，其是支持除了 $1$$1$ 操作外所有操作的快速实现的，而 ODT 又可以将区间整除转化为区间推平，于是我们便不难想到，同时维护一棵 ODT 和一棵线段树，对于 $1$$1$ 操作在 ODT 上通过刚才说的优化转换为若干个区间推平，然后将推平作用到线段树上，对于 $2$$2$ 操作则 ODT 和线段树同时进行，对于 $3$$3$ 的查询直接在线段树上跑即可。这个的复杂度我没太想出来，不过翻了一下题解区，发现一篇 Blog [ABC256Ex] I like Query Problem 题解 和我的做法几乎相同，唯一的区别就是其在 ODT 维护区间整除的时候是直接重构的 ODT。总体来讲这两种维护方式差别是不大的，无非就是一只小 $\log$$\log$ 的区别，大佬的 Blog 最后分析的复杂度为 $O(n{\log }^{2}n)$$O(n \log^2 n)$，所以我的这个可能也是这个复杂度？？总之表现还不错，最终 $1.6\mathtt{\text{s}}$$1.6\texttt{s}$ 跑完。

写在后面

这个奇怪的做法虽然能过，不过还是不推荐写，毕竟实现起来比较复杂细节较多，如果写的话似乎直接写重构部分 ODT 的方法会更好实现一些。一般的线段树写法实现大概也就 $60$$60$ 行，然后这个东西我实现大概写了将近两百行。。。

Code

xxxxxxxxxx
186
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, Q;
26
int A[510000];
27

28
struct Node{
29
    int l;
30
    mutable int r;
31
    mutable ll val;
32
    friend const bool operator < (const Node &a, const Node &b){
33
        return a.l < b.l;
34
    }
35
};
36

37
class SegTree{
38
private:
39
public:
40
    ll tr[510000 << 2];
41
    ll lz[510000 << 2];
42
    #define LS (p << 1)
43
    #define RS (LS | 1)
44
    #define MID ((gl + gr) >> 1)
45
    #define SIZ(l, r) ((r) - (l) + 1)
46
public:
47
    SegTree(void){memset(lz, -1, sizeof lz);}
48
    void Pushup(int p){tr[p] = tr[LS] + tr[RS];}
49
    void Pushdown(int p, int gl, int gr){
50
        if(!~lz[p])return;
51
        lz[LS] = lz[RS] = lz[p];
52
        tr[LS] = SIZ(gl, MID) * lz[p];
53
        tr[RS] = SIZ(MID + 1, gr) * lz[p];
54
        lz[p] = -1;
55
    }
56
    void Build(int p = 1, int gl = 1, int gr = N){
57
        if(gl == gr)return tr[p] = A[gl = gr], void();
58
        Build(LS, gl, MID), Build(RS, MID + 1, gr);
59
        Pushup(p);
60
    }
61
    void Assign(int l, int r, ll v, int p = 1, int gl = 1, int gr = N){
62
        // printf("Assign ST : l = %d, r = %d, v = %lld, gl = %d, gr = %d, p = %d\n", l, r, v, gl, gr, p);
63
        if(l <= gl && gr <= r)return tr[p] = SIZ(gl, gr) * v, lz[p] = v, void();
64
        Pushdown(p, gl, gr);
65
        if(l <= MID)Assign(l, r, v, LS, gl, MID);
66
        if(MID + 1 <= r)Assign(l, r, v, RS, MID + 1, gr);
67
        Pushup(p);
68
    }
69
    ll Query(int l, int r, int p = 1, int gl = 1, int gr = N){
70
        if(l <= gl && gr <= r)return tr[p];
71
        if(r < gl || l > gr)return 0;
72
        Pushdown(p, gl, gr);
73
        return Query(l, r, LS, gl, MID) + Query(l, r, RS, MID + 1, gr);
74
    }
75
    void Desc(int siz = 3){
76
        int len(1);
77
        int cur(0);
78
        while(siz--){
79
            for(int i = 1; i <= len; ++i)printf("%lld%c", tr[++cur], i == len ? '\n' : ' ');
80
            len <<= 1;
81
        }
82
    }
83
}st;
84

85
class ODT{
86
private:
87
    set < Node > tr;
88
public:
89
    auto Insert(Node p){return tr.insert(p);}
90
    auto Split(int p){
91
        auto it = tr.lower_bound(Node{p});
92
        if(it != tr.end() && it->l == p)return it;
93
        advance(it, -1);
94
        if(p > it->r)return tr.end();
95
        int l = it->l, r = it->r;
96
        ll val = it->val;
97
        tr.erase(it);
98
        Insert(Node{l, p - 1, val});
99
        return Insert(Node{p, r, val}).first;
100
    }
101
    void Assign(int l, int r, ll val){
102
        auto itR = Split(r + 1), itL = Split(l);
103
        tr.erase(itL, itR);
104
        Insert(Node{l, r, val});
105
        st.Assign(l, r, val);
106
    }
107
    void Divide(int l, int r, ll x){
108
        auto itR = Split(r + 1), itL = Split(l);
109
        for(auto it = itL; it != itR;){
110
            it->val /= x;
111
            if(!it->val){
112
                decltype(it) nxt;
113
                for(nxt = next(it); nxt != itR; nxt = tr.erase(nxt)){
114
                    nxt->val /= x;
115
                    if(!nxt->val)it->r = nxt->r;
116
                    else{
117
                        st.Assign(it->l, it->r, it->val);
118
                        st.Assign(nxt->l, nxt->r, nxt->val);
119
                        it = next(nxt);
120
                        break;
121
                    }
122
                }
123
                if(nxt == itR)st.Assign(it->l, it->r, it->val), it = nxt;
124
            }else
125
                st.Assign(it->l, it->r, it->val), advance(it, 1);
126
        }
127
    }
128
    ll Query(int l, int r){
129
        ll ret(0);
130
        auto itR = Split(r + 1), itL = Split(l);
131
        for(auto it = itL; it != itR; ++it)
132
            ret += (it->r - it->l + 1) * it->val;
133
        return ret;
134
    }
135
    void Desc(void){
136
        printf("Describe ODT:\n");
137
        for(auto nod : tr)printf("%d ~ %d : %lld\n", nod.l, nod.r, nod.val);
138
    }
139
}odt;
140

141
int main(){
142
    // freopen("01_n_small_00.txt", "r", stdin);
143
    // freopen("out.txt", "w", stdout);
144
    N = read(), Q = read();
145
    for(int i = 1; i <= N; ++i)odt.Insert(Node{i, i, A[i] = read()});
146
    st.Build();
147
    while(Q--){
148
        int opt = read();
149
        switch(opt){
150
            case 1:{
151
                int l = read(), r = read(), x = read();
152
                odt.Divide(l, r, x);
153
                break;
154
            }
155
            case 2:{
156
                int l = read(), r = read(), x = read();
157
                odt.Assign(l, r, x);
158
                break;
159
            }
160
            case 3:{
161
                int l = read(), r = read();
162
                printf("%lld\n", st.Query(l, r));
163
                break;
164
            }
165
            default: break;
166
        }
167
    }
168
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
169
    return 0;
170
}
171

172
template < typename T >
173
inline T read(void){
174
    T ret(0);
175
    int flag(1);
176
    char c = getchar();
177
    while(c != '-' && !isdigit(c))c = getchar();
178
    if(c == '-')flag = -1, c = getchar();
179
    while(isdigit(c)){
180
        ret *= 10;
181
        ret += int(c - '0');
182
        c = getchar();
183
    }
184
    ret *= flag;
185
    return ret;
186
}

UPD

update-2022_12_08 初稿

update-2022_12_08 修复 Ex 的一点小锅