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

Solost

2023 年 01 月 19 日

272 次浏览

暂无评论

900字数

题目题解

![](https://amarantos.oss-cn-hangzhou.aliyuncs.com/typecho/2023/01/2202397934.png)

## solution

累了，刚写完的题解没保存，就简单的给一下过程吧

![](https://amarantos.oss-cn-hangzhou.aliyuncs.com/typecho/2023/01/2583859761.png)

```C++
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>

using namespace std;
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
typedef long long ll;
typedef pair<int, int> PII;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f, mod = 998244353;
const int N = 4e5 + 10;
ll a[N];
void solve()
{
    ll n, m;
    vector<pair<int, int>> q;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int l, r;
        cin >> l >> r;
        a[l]++, a[r + 1]--;//差分数组处理
        q.push_back({ l, r });
    }
    for (int i = 1; i <= 4e5 + 5; i++) {
        a[i] += a[i - 1];//将数组处理成差分数组
    }
    for(int i = 1; i <= 4e5 + 5; i++){
    	a[i] += a[i - 1];//将差分数组处理成前缀和数组
    }
    ll ans = 0;
    for (auto x : q) {
        ll l = x.first, r = x.second;
        ll st = max(n - r, 1ll), ed = max(0ll, n - l);//计算本区间的互补区间大小
        ll st1 = max(l, n - r);
        ll ed1 = min(r, n - l);//计算自身区间满足条件的合法区间
        ans = (ans % mod + (a[ed] - a[st - 1] - max(ed1 - st1 + 1, 0ll)) % mod) % mod;
	//答案就是自身满足条件的合法互补区间减去自身和自身互补的区间长度，就得到了本次区间和剩下所有满足条件互补区间个数，累加取模即可
    }
    cout << ans << endl;
}
int main()
{
    IOS;
    int t = 1;
    while (t--) {
        solve();
    }
    return 0;
}
```

最后修改：2023 年 02 月 02 日