[ABC256F] Cumulative Cumulative Cumulative Sum Solution

更好的阅读体验戳此进入

题面

给定序列 $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
}

UPD

update-2022_12_08 初稿