JZOJ 6384 珂学家

首先考虑一个不定方程 x1+x2=c，其中有限制 l1≤x1≤r1,l2≤x2≤r2 的整数解的组数。
容易发现确定 x1 并满足 l2≤c−x1≤r2 即可得到一组解。
故共有 min(r1,c−l2)−max(l1,c−r2)+1 组解。

考虑枚举两种试剂 x,y，则对于 c∈[lx+ly,rx+ry]，vx⋅vy 于其的贡献为 min(rx,c−ly)−max(lx,c−ry)+1。
这个不大好处理，但不妨将 c 以 lx+ly,rx+ly,lx+ry,rx+ry 四个点分类讨论。
不妨设 rx+ly≤lx+ry，否则可交换。

1. 当 c∈[lx+ly,rx+ly) 时：
   rx>c−ly,lx>c−ry，故 min(rx,c−ly)−max(lx,c−ry)+1=−ly−lx+1+c。
   注意到这相当于区间加等差数列，使用二阶差分维护即可。
2. 当 c∈[rx+ly,lx+ry) 时：
   rx≤c−ly,lx>c−ry，故 min(rx,c−ly)−max(lx,c−ry)+1=rx−lx+1。
   区间加，维护一阶差分即可，也可以和二阶差分一起维护。
3. 当 c∈[lx+ry,rx+ry] 时：
   rx<c−ly,lx≤c−ry，故 min(rx,c−ly)−max(lx,c−ry)+1=rx+ry+1−c。
   同样是等差序列，类似维护即可。

代码：

#pragma GCC optimize("Ofast")
#pragma GCC target("sse3","sse2","sse")
#pragma GCC diagnostic error "-std=c++14"
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#pragma GCC optimize("fast-math","unroll-loops","no-stack-protector","inline")
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 5e3;
const int K = 2e7;
const int mod = 998244353;
int n,m;
int v[N + 5],l[N + 5],r[N + 5];
int s[K + 5];
int main()
{
    freopen("a.in","r",stdin),freopen("a.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(register int i = 1;i <= n;++i)
        scanf("%d%d%d",v + i,l + i,r + i);
    for(register int i = 1;i < n;++i)
        for(register int j = i + 1;j <= n;++j)
        {
            int x,y,w;
            w = (long long)v[x = i] * v[y = j] % mod,r[x] + l[y] > l[x] + r[y] && (swap(x,y),1);
            s[l[x] + l[y]] = (s[l[x] + l[y]] + w) % mod,s[r[x] + l[y] + 1] = (s[r[x] + l[y] + 1] - w + mod) % mod,s[l[x] + r[y] + 1] = (s[l[x] + r[y] + 1] - w + mod) % mod,s[r[x] + r[y] + 2] = (s[r[x] + r[y] + 2] + w) % mod;
        }
    for(register int i = 1;i <= K;++i)
        s[i] = (s[i] + s[i - 1]) % mod;
    for(register int i = 1;i <= K;++i)
        s[i] = (s[i] + s[i - 1]) % mod;
    int k;
    for(;m;--m)
        scanf("%d",&k),printf("%d\n",s[k]);
}