[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.解题思路

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

注意：

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

算法步骤

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

code

CPP

#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;
}

题解：AT_abc260_e [ABC260E] At Least One

文章操作

[ABC260E] At Least One - 题解

1.题目大意

2.解题思路

注意：

算法步骤

code

相关推荐

评论

题解：AT_abc260_e [ABC260E] At Least One