蒟蒻的第一篇题解(
(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;
}