P10511 题解
思路
首先好像高一就学过
令
也就是要维护区间平方和与区间和。这可以考虑用前缀和维护。考虑到有散块的可能,所以先把夹在
我们可以先把

例如,想要求 dx = lower_bound(r + 1, r + m + 1, x) - r; 或 dx = lower_bound(l + 1, l + m + 1, x) - l - 1。
其他小细节在代码注释里。注意取膜哦!
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll M = 2e5 + 100, mod = 998244353;
ll n, m, q;
ll l[M], r[M];
ll s[M], qs[M], len[M], b[M];
int main()
{
cin >> n >> m >> q;
for (int i = 1; i <= m; i++)
{
cin >> l[i] >> r[i] >> b[i]; b[i] %= mod;
len[i] = (r[i] - l[i] + 1) % mod;
s[i] = (len[i] * b[i]) % mod;
qs[i] = (s[i] * b[i]) % mod;
len[i] = (len[i - 1] + len[i]) % mod;
s[i] = (s[i - 1] + s[i]) % mod;
qs[i] = (qs[i - 1] + qs[i]) % mod;
}
for (int i = 1; i <= q; i++)
{
/* 一开始想先把离 x/y 右/左 边最近的 左/右 端点编号求出来的……但是实现起来有点麻烦( */
ll x, y, dx, dy /* dx 为 x 所在的编号;dy 含义亦然 */, S, QS, ans; cin >> x >> y;
dx = lower_bound(l + 1, l + m + 1, x) - l - 1, // 也就是 dx = lower_bound(r + 1, r + m + 1, x) - r;
dy = lower_bound(r + 1, r + m + 1, y) - r;
if (dx == dy) { cout << 0 << endl; continue; }
// S = S + (r[dx] - x + 1) * b[dx] + (y - l[dy] + 1) * b[dy];
S = (r[dx] - x + 1) % mod * b[dx] % mod + (y - l[dy] + 1) % mod * b[dy] % mod;
QS = (r[dx] - x + 1) % mod * b[dx] % mod * b[dx] % mod + (y - l[dy] + 1) % mod* b[dy] % mod * b[dy] % mod;
dx++, dy--; // 移到里面夹着的整块
if (dx <= dy) // 排除里面没夹着整块的情况
{
S = (S + s[dy] - s[dx - 1] + mod) % mod;
QS = (QS + qs[dy] - qs[dx - 1] + mod) % mod;
}
ans = ((y - x + 1) % mod * QS % mod - S * S % mod + mod) % mod;
cout << (ans + mod) % mod << endl;
}
return 0;
}P10511 题解
https://zerablog.top/2024/09/16/P10511/