标签：int 题解 Sum Cumulative ret cdots ll define

[ABC256F] Cumulative Cumulative Cumulative Sum Solution

目录

• [ABC256F] Cumulative Cumulative Cumulative Sum Solution
  • 更好的阅读体验戳此进入
  • 题面
  • Solution
  • Code
  • UPD

更好的阅读体验戳此进入

题面

给定序列 $ 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 $。存在两种操作：

1 x v：$ A_x \leftarrow v $。

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

Solution

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

$ \textbf{A} $	$ a_1 $	$ a_2 $	$ a_3 $	$ \cdots $	$ a_i $
$ \textbf{B} $	$ a_1 $	$ a_1 + a_2 $	$ a_1 + a_2 + a_3 $	$ \cdots $	$ a_1 + a_2 + \cdots + a_i $
$ \textbf{C} $	$ a_1 $	$ 2a_1 + a_2 $	$ 3a_1 + 2a_2 + a_3 $	$ \cdots $	$ ia_1 + (i - 1)a_2 + \cdots + a_i $
$ \textbf{D} $	$ a_1 $	$ 3a_1 + a_2 $	$ 6a_1 + 3a_2 + a_3 $	$ \cdots $	$ (1 + 2 + \cdots + i)a_1 + (1 + 2 + \cdots + (i - 1))a_2 + \cdots + a_i $

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

\[D_x= \sum_{i = 1}^x \dfrac{1}{2}(1 + x - (i - 1)) \times (x - (i - 1))a_i \]

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

\[\begin{aligned} & (1 + x - (i - 1)) \times (x - (i - 1))a_i \\ =& (x - i + 2) \times (x - i + 1)a_i \\ =& (x^2 -ix +2x - ix + i^2 -2i + x - i + 2)a_i \\ =& (x^2 -2ix + 3x + i^2 - 3i + 2)a_i \\ =& (x^2 + 3x + 2)a_i - 2x(ia_i) + (i^2 - 3i)a_i \end{aligned} \]

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

Code

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

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

using namespace std;

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

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

#define MOD (998244353ll)

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

int N, Q;
ll A[210000];

ll qpow(ll a, ll b){
    ll ret(1), mul(a);
    while(b){
        if(b & 1)ret = ret * mul % MOD;
        b >>= 1;
        mul = mul * mul % MOD;
    }return ret;
}

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

int main(){
    const ll inv2 = qpow(2, MOD - 2);
    N = read(), Q = read();
    for(int i = 1; i <= N; ++i)
        A[i] = read(),
        bit1.Modify(i, A[i]),
        bit2.Modify(i, i * A[i] % MOD),
        bit3.Modify(i, ((ll)i * i % MOD - 3ll * i % MOD + MOD) % MOD * A[i] % MOD);
    while(Q--){
        int opt = read();
        if(opt == 1){
            int x = read(); ll v = read();
            bit1.Modify(x, (v - A[x] + MOD) % MOD),
            bit2.Modify(x, x * ((v - A[x] + MOD) % MOD) % MOD),
            bit3.Modify(x, ((ll)x * x % MOD - 3ll * x % MOD + MOD) % MOD * ((v - A[x] + MOD) % MOD) % MOD);
            A[x] = v;
        }else{
            ll x = read();
            ll ret = (x * x % MOD + 3ll * x % MOD + 2) % MOD * bit1.Query(x) % MOD;
            (ret += (-2ll * x + MOD) % MOD * bit2.Query(x) % MOD) %= MOD;
            (ret += bit3.Query(x)) %= MOD;
            printf("%lld\n", ret * inv2 % MOD);
        }
    }
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    int flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

UPD

update-2022_12_08 初稿

标签：int,题解,Sum,Cumulative,ret,cdots,ll,define
From： https://www.cnblogs.com/tsawke/p/17032775.html