`Tokitsukaze` `and` `a+b=n`

前提提要：

今天的这道题，是来源于2023牛客寒假算法集训营的第二次练习的problem c

题目来源

C-Tokitsukaze and a+b=n (hard)_2023牛客寒假算法基础集训营2 (nowcoder.com)

注意，只要报名了的人才可以进入网站

原题题面

题目描述

Tokitsukaze 有一个整数 n，以及 m 个区间 [L,R]

她想知道有多少种选法，满足：从 m 个区间中选择两个区间 [Li,Ri], [Lj,Rj] (i≠j)，并从第一个区间选择一个整数 a (Li≤a≤Ri)，从第二个区间选择一个整数 b (Lj≤b≤R)，使得 a+b=n

对于两种选法，若 i, j, a, b 中有任意一个数不同，则算作不同的选法。

由于答案可能很大，请输出对 998 244 353 取模后的结果。

输入描述:

第一行包含两个整数 n, m (2 ≤n,m≤ 4 * 10^5)。

接下来 m 行，每行包含两个整数 L, R (1 ≤ L ≤ R ≤ 2 * 10^5)

输出描述:

输出一个整数表示答案对 998 244 353取模后的结果

输入

输出

题目解释

朴素算法

经过一系列的分析，我们可以得到这么一个思路，我们可以每两个区间进行遍历，对于两个区间都给予两个不同的指针，一个从小到大，一个从大到小，遇到了加起来满足题意的就向下进行，最后输出所有的满足的答案

上面的算法是最朴素的解法了，解法上是满足题目要求的，但是时间上的复杂度较高，无法通过题目要求，对于这道题的410^5的循环量，近乎要O(n) 或者O(n log n) 的解法才可以跑完，所以，我们要对第一个思路进行优化，将复杂度优化至*O(n)

优化1 数学

我们对于1 3 和2 4这两个区间，求出这两个区间有多少满足情况的，我们可以将第一个区间上的每一个数都被5给减去，那么第一个区间的范围就变成了2 4，现在，我们就知道了，2到4范围里面的所有数都是满足第一个区间上的数的，然后，我们再计算一下2到4和2 4有多少个数字是相同的，假设变化后的第一个区间是

a[] = {2,3,4};

原本的第二个区间是

b[] = {2,3,4};

求两个范围里面有多少个重复的数，我们只要拿到两个范围里面的各自的最小值和最大值，

a范围 l1 = 2, r1 = 4
b范围 l2 = 2, r2 = 4

计算重复数的式子如下：

int sum, l, r;
if(r2 < l1 || r1 < l2) sum = 0;
else {
	l = max(l1, l2);
	r = min(r1, r2);
	sum = r - l + 1;
}

通过这么一个步骤，我们就可以得到两个区间，然后进行简单的数学计算就可以直接得出两个区间中有多少个匹配的了

但是，这样计算下来，时间复杂度还是太高了，每两个区间进行就还要O(n^2) 的复杂度，所以我们还需要继续优化

优化2 差分

现在，我们可以这么想，既然我们要求两个区间中是否有重复的数字，那我们对于n个区间，我们可以将n个区间里面所有的数进行相加,看看我们所有数的范围，比如说上面的例子，对于三个区间

1 3 和 2 4 和 3 5
总区间数字如下
数字	0	1	2	3	4	5
次数	0	1	2	3	2	1

我们可以找到所有数字出现的总次数，然后对于每一个区间进行遍历，找一找每一个区间与总区间的重复数有多少个，进行相加，同时再减去对比的区间里面出现的重复数，就可以得到答案了

//差分法补充
int f[6];
for(int i = 1;i <= 3;i++) {
    int a, b;
    cin >> a >> b;
    f[a] ++;
    f[b + 1]--;
}
//差分数组求和
for(int i = 1;i <= 5;i++) {
    f[i] += f[i - 1];
}

这样一来，我们已经预处理了所有的区间和，我们再遍历每一个区间，就只要O(n)的解法就可以写出来了，这样也就优化到了题目所给出的要求啦 (∩_∩)

下面是差分代码

#include<bits/stdc++.h>
using namespace std;
//取模数和数组范围
const int N = 1000010,M = 998244353;
//	左数	右数	差分求和数	减去数
int l[N], r[N], d[N], f[N];

main函数

int n, m, ans = 0;
cin >> n >> m;
for(int i = 1;i <= m;i++) {
    //输入
    cin >> l[i] >> r[i];
    //差分
    d[l[i]]++; d[r[i] + 1]--;
    //满足条件1
    if(n - l[i] >= l[i] && n - l[i] <= r[i])
    {
        //差分
        f[l[i]]++;
        f[n - l[i] + 1]--;
    }
    //满足条件2
    else if(n - r[i] >= l[i] && n - r[i] <= r[i])
    {
        //差分
        f[n - r[i]]++;
        f[r[i] + 1]--;
    }
}

差分数组求和

for(int i = 1;i <= n;i++) {
    d[i] += d[i - 1];
    f[i] += f[i - 1];
}

小tip

计算所有满足条件的数字，即所有满足数减去重复数取模

//取模补充，减少取模的错误率,假如对N取模
const int N = 10000000;
int m = 1145141919;
m = (m + N) % N;
int t = -114514;
t = (t + N) % N;

取模+求和

for(int i = 1;i < n;i++) {
    //自身 = 自身 + 乘以次数 - 重复数 + 模数
    ans = (ans + 1ll * d[i] * d[n - i] % M - f[i] + M) % M;
}
//输出所有数字
cout << ans << endl;
return 0;

`ac`代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1000010,M = 998244353;
int l[N], r[N]；
int d[N], f[N];

int main()
{
    int n, m, ans = 0;
    cin >> n >> m;
    for(int i = 1;i <= m;i++) {
        cin >> l[i] >> r[i];
        d[l[i]]++; d[r[i] + 1]--;
        if(n - l[i] >= l[i] && n - l[i] <= r[i])
        {
            f[l[i]]++;
            f[n - l[i] + 1]--;
        }
        else if(n - r[i] >= l[i] && n - r[i] <= r[i])
        {
            f[n - r[i]]++;
            f[r[i] + 1]--;
        }
    }
    for(int i = 1;i <= n;i++) {
        d[i] += d[i - 1];
        f[i] += f[i - 1];
    }
    for(int i = 1;i < n;i++) {
        ans = (ans + 1ll * d[i] * d[n - i] % M - f[i] + M) % M;
    }
    cout << ans << endl;
    return 0;
}

写在最后

这道题还是有些小遗憾的，在写这道题的时候，已经得出最后的优化版本了，本来想着直接ac，但是提交修改了几次都wa了，后面想到应该是我写的重复数代码没有减对，直接按上一题的思路减去，最后很遗憾没写出来，因此还需要继续练习，努力补题！