CF Edu152 C

小咪咪 2024-03-26 22:38 87阅读 0赞

[Problem - C - Codeforces][]

题意：

![dc8c36dc290344c988ab2c298156cac1.png][]

![49d85d3c87cb4a739dc9a0489f835517.png][]

思路：

首先，观察样例可知

![737beb494afb44f4a5af82ba46fe7d55.png][]

这种是等效的

推广一下

0000.....111111

..l..............r......

这种是等效的

容易想到维护后面第一个1的位置和前面第一个0的位置，然后把所有区间都等效一下，开一个二元组的set

但是有点问题，考虑一些特殊case

0001111

这样的，很明显等效之后左端点在右端点后面

这种的也是

这些特殊case有什么共同点呢？这些区间一个区间sort之后对应一种情况

因此直接插入 \{-1， -1\}即可

111100000

那么这种呢？等效前和等效后的区间是一样的，直接插入即可

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using i64 = long long;
    
    constexpr int N = 2e5 + 10;
    constexpr int M = 2e5 + 10;
    constexpr int P = 2600;
    constexpr i64 Inf = 1e18;
    constexpr int mod = 1e9 + 7;
    constexpr double eps = 1e-6;
    
    std::string s;
    
    int n, m;
    int a[N];
    int pre0[N];//前面第一个0的位置
    int suf1[N];//后面第一个1的位置
    
    void solve() {
        std::cin >> n >> m >> s;
        s = " " + s;
        for (int i = 1; i <= n; i ++) {
            a[i] = s[i] - '0';
        }
    
        pre0[0] = 0;
        suf1[n + 1] = n + 1;
    
        for (int i = 1; i <= n; i ++) {
            if (a[i] == 0) pre0[i] = i;
            else pre0[i] = pre0[i - 1];
        }
    
        for (int i = n; i >= 1; i --) {
            if (a[i] == 1) suf1[i] = i;
            else suf1[i] = suf1[i + 1];
        }
    
        std::set<std::pair<int,int> > S;
        for (int i = 1; i <= m; i ++) {
            int l, r;
            std::cin >> l >> r;
            int tl = suf1[l];
            int tr = pre0[r];
            if (tl > tr) S.insert({-1, -1});
            else S.insert({tl, tr});
        }
    
        std::cout << S.size() << "\n";
    }
    signed main() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        
        int t = 1;
        std::cin >> t;
    
        while (t--) {
            solve();
        }
        
        return 0;
    }

[Problem - C - Codeforces]: https://codeforces.com/contest/1849/problem/C
[dc8c36dc290344c988ab2c298156cac1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/dbdfdcfcd93648a094e94fe2fd45234f.png
[49d85d3c87cb4a739dc9a0489f835517.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/ef515897e3f34eeca63e5588326e76fe.png
[737beb494afb44f4a5af82ba46fe7d55.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/504bb72f0df84061b573110a047dcd82.png