Znzryb's Blog
0%

ABC - 377 -D - Many Segments 2

Posted on Edited on

题目大意

给定 nn 条线段 [Li,Ri][L_i, R_i]，线段端点都在 1∼m1\sim m 的范围内。需要统计满足题意的区间数量（等价于对每个左端点 ll，能延伸到的最大右端点受右侧最小的 RR 约束），并输出总数。

AC代码

主要思路是一个点所能到达的最大边界取决于它的minR，也即在它右边的最小右边界

可以看到minR的统计过程是这样的

1
2
3
4
5
6
7
8
9
10
11
for(int _=1;_<=n;_++) {
        ll l,r;
        cin>>l>>r;
        minR[l]=min(minR[l],r);     // 其实包括l之前所有的点，minR的值应该设为r（min（ r ，现有值））
                                        // 但如果直接这样设，时间复杂度会来到O（n^2）级别，显然无法通过全部数据
    }                                   // 那我们为什么不先设一个l，在最后来一个汇总，反正也不要求强制在线。
    ll currMin=m+1;
    for(int i=m;i>=1;--i) {             // 汇总
        currMin=min(currMin,minR[i]);
        minR[i]=currMin;
    }

可以证明在 【Li,Ri】，比Li还小的地方 l（包含Li）的【l，r】区间包含Ri，必然导致【l，r】包含【Li，Ri】

所以比Li更小的地方应该将Ri考虑在minR的取值中

比如说minR[1]==4 他的答案怎么统计那？

1
2
3
4
5
1 2 3

1 2

1

可以看到一共有三种区间（[1,3],[1,2],[1,1]）即区间长度之和即为答案（[1,4]）

然后还有一些离线化的优化方法，注释里写的很清楚

AC 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <cmath>
#include <bitset>

using namespace std;
typedef long long ll;
const ll N=2e5+10;
ll n,m,cnt,minR[N],ans;    // minR代表该点l对应的最小R

void debug() {
    for(int i=1;i<=m;++i) {
        cout<<minR[i]<<" ";
    }
    cout<<endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++) {             // 初始化minR
        minR[i]=m+1;
    }
    for(int _=1;_<=n;_++) {
        ll l,r;
        cin>>l>>r;
        minR[l]=min(minR[l],r);     // 其实包括l之前所有的点，minR的值应该设为r（min（ r ，现有值））
                                        // 但如果直接这样设，时间复杂度会来到O（n^2）级别，显然无法通过全部数据
    }                                   // 那我们为什么不先设一个l，在最后来一个汇总，反正也不要求强制在线。
    ll currMin=m+1;
    for(int i=m;i>=1;--i) {             // 汇总
        currMin=min(currMin,minR[i]);
        minR[i]=currMin;
    }
    ans=0;
    for(int i=1;i<=m;++i) {
        ans+=minR[i]-i;           // 答案统计
    }
    cout<<ans<<endl;
    // debug();
}
// AC https://atcoder.jp/contests/abc377/submissions/59206219

心路历程（WA，TLE，MLE……）

一次提交过的，之前的代码样例都过不了就不放在这里了