蒟蒻的第一篇题解(

(simple / medium)

用[a, b]表示[l1, r1]中元素和n的差值,再求[a, b]和[l2, r2]的交集就行了

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int t, n, l1, r1, l2, r2, st[200010];

int main()
{
    cin >> t;
    while(t --)
    {
        cin >> n;
        cin >> l1 >> r1 >> l2 >> r2;
        int a = n - r1, b = n - l1;
        if(b < l2 || a > r2) cout << 0 << endl;
        else cout << min(r2, b) - max(l2, a) + 1 << endl;
    }
    return 0;
}

(hard)

st数组用来记录每个数出现的次数(差分),之后利用(小学数学就学过的)加法原理和乘法原理(?)求出答案。因为两个数不能来自同一个区间(即i != j),所以需要对 同时含有x和n - x的区间 进行特殊处理(16·18行),即利用simple难度的情景,只不过两个区间是一样的,找到这种情况有几种,将其减去就行。

#include <iostream>
#include <algorithm>
using namespace std;

const long long mod = 998244353, N = 400010;
long long n, m, st[N], ans;
int l, r;

int main()
{
    cin >> n >> m;
    for(int i = 0; i < m; i ++)
    {
        cin >> l >> r;
        st[l] ++, st[r + 1] --;
        int a = n - r, b = n - l;
        if(b < l || a > r) ans += 0;
        else ans -= min(r, b) - max(l, a) + 1;
    }
    
    for(int i = 1; i <= n; i ++)
    {
        st[i] += st[i - 1];
    }
    for(int i = 1; i < n; i ++)
    {
        ans += st[i] * st[n - i];
    }
    cout << ans % mod;
    
    return 0;
}