题解：AT_abc455_f [ABC455F] Merge Slimes 2
wzq_owo
·
·
题解
每次合并两个数字 x 和 y 时，生成的新数字是 x + y ，而操作代价则是 x \times y。x 是几个 B 相加而来的，通过乘法分配律可知，这几个 B 合并前的代价是 B \times y ，而合并后依然是，所以合并操作不影响代价。
则得到代价为 \sum_{1 \leq i < j \leq M} B_i \times B_j。
记 S = \sum_{i=1}^M B_i，则：
S^2=\sum_{i=1}^N B_i^2 + 2\times \sum_{1\leq i < j \leq M}B_i\times B_j
记 T=\sum_{i=1}^N B_i^2，则 \sum_{1 \leq i < j \leq M} B_i \times B_j = \frac{S-T}{2}。
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int N = 1e5 + 5;
int n, q;
ll psum[N << 2], sum[N << 2], add[N << 2];
ll qpow(ll a, ll b)
{
ll res = 1;
while (b)
{
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
ll inv2 = qpow(2, mod - 2);
void pushup(int p)
{
psum[p] = (psum[p << 1] + psum[p << 1 | 1]) % mod;
sum[p] = (sum[p << 1] + sum[p << 1 | 1]) % mod;
}
void pushdwon(int p, int l, int r)
{
if (add[p] == 0) return ;
int mid = (l + r) >> 1;
add[p << 1] = (add[p << 1] + add[p]) % mod;
add[p << 1 | 1] = (add[p << 1 | 1] + add[p]) % mod;
psum[p << 1] = (psum[p << 1] + 2 * add[p] * sum[p << 1] % mod) % mod;
psum[p << 1] = (psum[p << 1] + add[p] * add[p] % mod * (mid - l + 1) % mod) % mod;
psum[p << 1 | 1] = (psum[p << 1 | 1] + 2 * add[p] * sum[p << 1 | 1] % mod) % mod;
psum[p << 1 | 1] = (psum[p << 1 | 1] + add[p] * add[p] % mod * (r - mid) % mod) % mod;
sum[p << 1] = (sum[p << 1] + add[p] * (mid - l + 1) % mod) % mod;
sum[p << 1 | 1] = (sum[p << 1 | 1] + add[p] * (r - mid) % mod) % mod;
add[p] = 0;
}
void update(int p, int l, int r, int ql, int qr, ll k)
{
if (ql <= l && r <= qr)
{
psum[p] = (psum[p] + 2 * k * sum[p] % mod) % mod;
psum[p] = (psum[p] + k * k % mod * (r - l + 1) % mod) % mod;
sum[p] = (sum[p] + k * (r - l + 1)) % mod;
add[p] = (add[p] + k) % mod;
return ;
}
pushdwon(p, l, r);
int mid = (l + r) >> 1;
if (ql <= mid) update(p << 1, l, mid, ql, qr, k);
if (mid < qr) update(p << 1 | 1, mid + 1, r, ql, qr, k);
pushup(p);
}
ll queryp(int p, int l, int r, int ql, int qr)
{
if (ql <= l && r <= qr)
{
return psum[p];
}
pushdwon(p, l, r);
int mid = (l + r) >> 1;
ll ans = 0;
if (ql <= mid) ans = (ans + queryp(p << 1, l, mid, ql, qr)) % mod;
if (mid < qr) ans = (ans + queryp(p << 1 | 1, mid + 1, r, ql, qr)) % mod;
return ans;
}
ll query(int p, int l, int r, int ql, int qr)
{
if (ql <= l && r <= qr)
{
return sum[p];
}
pushdwon(p, l, r);
int mid = (l + r) >> 1;
ll ans = 0;
if (ql <= mid) ans = (ans + query(p << 1, l, mid, ql, qr)) % mod;
if (mid < qr) ans = (ans + query(p << 1 | 1, mid + 1, r, ql, qr)) % mod;
return ans;
}
int main()
{
cin >> n >> q;
while (q -- )
{
int l, r, a;
cin >> l >> r >> a;
update(1, 1, n, l, r, a);
ll S = query(1, 1, n, l, r), T = queryp(1, 1, n, l, r);
cout << (S * S % mod - T + mod) % mod * inv2 % mod << endl;
}
return 0;
}
```