C Tokitsukaze and a+b=n (hard)

算法 前缀和 $O(n+m)O(n+m)$

本题是问从两个区间取两个数 $a,ba,b$ 和为 $nn$,可以考虑枚举其中一个数 $a,1\le a\le n-1a,1\backslash leq\; a\backslash leq\; n-1$,$b=n-ab\; =\; n\; -a$ 则只需要知道 $n-an-a$ 的数量即可。 首先预先用差分前缀和计算出每个数的数量，对每个区间进行$delta[l_i]+1,delta[r_i+1]-1delta[l\_i]+1,delta[r\_i+1]-1$,然后进行前缀和得到 $numsnums$ 数组。

由于 $a+b=b+aa+b=b+a$, 因此只需要枚举 $aa$ 从1到 $\lfloor \frac{n}{2}\rfloor \backslash lfloor\; \backslash frac\{n\}\{2\}\backslash rfloor$,最后将答案乘2即可。

若 $a!=ba\backslash \; !=b$,则答案增加 $nums[a]\ast nums[b]nums[a]*\; nums[b]$， 否则答案增加 $nums[a]\ast (nums[a]-1)\mathrm{/}2nums[a]*\; (nums[a]-1)/2$

思考一下，前缀和数组里的每个数只存储了数量，但并没有记录是哪个区间，因此上述计算的答案包括了同一区间取出两个数和为 $nn$ ，但是比如当 $a=n-aa\; =\; n-a$ 时，一个区间里不会出现两个一样的数，因此此时没有重复，剩下的只需要计算每一个区间取两个数等于 $nn$ 的个数，再减掉即可，一个区间取两个数计算非常简单，不再赘述。

#include <bits/stdc++.h>
#define int long long
#define forn(i, a, b) for (int i = a; i < b; i++)
#define fore(i, a, b) for (int i = a; i <= b; i++)
#define rofn(i, a, b) for (int i = a; i > b; i--)
#define rofe(i, a, b) for (int i = a; i >= b; i--)
#define Ios ios::sync_with_stdio(false), cin.tie(0)
using namespace std;
const int mod = 998244353;
int delta[400010];
// 计算一个区间取两个不同的数和为n的个数
int calc(int n, int l, int r) {
    if (n > 2 * l && n < 2 * r) {
        if (n <= l + r) {
            return (n - 2 * l + 1) / 2;
        } else {
            return (2 * r - n + 1) / 2;
        }
    }
    return 0;
}
void solve() {
    int n, m;
    cin >> n >> m;
    int l, r, ans = 0, sub = 0;
    fore(i, 1, m) {
        cin >> l >> r;
        delta[l]++;
        delta[r + 1]--;
        sub = (sub + calc(n, l, r)) % mod;
    }
    fore(i, 1, 400005) {
        delta[i] += delta[i - 1];
    }

    fore(i, 1, n / 2) {
        if (i != n - i) {
            ans = (ans + delta[i] * delta[n - i]) % mod;
        } else {
            ans = (ans + delta[i] * (delta[i] - 1) / 2) % mod;
        }
    }
    ans = ((ans - sub) % mod + mod) % mod;
    ans = (2 * ans) % mod;
    cout << ans << "\n";
}
signed main() {
    Ios;
    solve();
    return 0;
}