题解：AT_abc260_e [ABC260E] At Least One

· · 题解

[ABC260E] At Least One - 题解

1.题目大意

给定 m 和 n 对整数 (a_i, b_i)，要求对于每个 k（1 \leq k \leq m），计算满足以下条件的连续子数组 [l, r]（长度为 k）的数量：对于每一对 (a_i, b_i)，子数组至少包含 a_i 或 b_i 中的一个。

2.解题思路

本题的核心在于高效地统计满足条件的子数组数量。我们可以利用差分数组和贪心思想来优化计算。

注意：

  1. 单调性：如果子数组 [l, r] 满足条件，那么任何包含 [l, r] 的子数组也一定满足条件。
  2. 最小区间：对于每个 l，存在一个最小的 r 使得 [l, r] 满足条件，且这个 r 随 l 增加而单调不减。

算法步骤

  1. 预处理：对于每对 (a_i, b_i)，记录其影响的范围。
  2. 差分数组：通过差分数组高效统计每个 k 对应的满足条件的子数组数量。
  3. 后缀和：利用后缀和计算最终答案。

code


#include<bits/stdc++.h>
#define ll long long
using namespace std;
int s[200010],a[200010],ans[200010],n,m;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int xx,yy,ss=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) {
        scanf("%d%d",&xx,&yy);
        a[1]=max(a[1],xx-1);
        a[xx+1]=max(a[xx+1],yy-xx-1);
        a[yy+1]=max(a[yy+1],m-yy);
    }
    for(int i=1;i<=m;i++) {
        a[i+1]=max(a[i+1],a[i]-1);
    }
    for(int i=1;i<=m;i++) {
        s[a[i]]++;
    }
    for(int i=m;i>=1;i--) {
        ss+=s[i];
        ans[i]=m-i+1-ss;
    }
    for(int i=1;i<=m;i++) {
        printf("%d ",ans[i]);
    }
    return 0;
}