【枚举区间】CF Edu10 C

落日映苍穹つ 2024-03-25 00:19 100阅读 0赞

[Problem - C - Codeforces][]

题意：

![155e04f8b5114d97a013247f06027577.png][]

思路：

应该反思一下这么典的思路为什么会想不到

枚举区间，一个很经典的套路是，枚举 l，对 r 计数

对于一个l，r取这么多限制中离 l 最近的那个

![73e66c83c91f4b348917364b9497e0c6.png][]

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using i64 = long long;
    
    constexpr int N = 3e5 + 10;
    constexpr int M = 3e5 + 10;
    constexpr int P = 2e6;
    constexpr i64 Inf = 1e18;
    constexpr int mod = 1e9 + 7;
    constexpr double eps = 1e-6;
    
    int n, m;
    int a[N], pos[N], r[N];
    
    void solve() {
        std::cin >> n >> m;
        for (int i = 1; i <= n; i ++) {
            std::cin >> a[i];
            pos[a[i]] = i;
            r[i] = n;
        }
    
        for (int i = 1; i <= m; i ++) {
            int x, y;
            std::cin >> x >> y;
            if (pos[x] > pos[y]) std::swap(x, y);
            r[pos[x]] = std::min(pos[y] - 1, r[pos[x]]);
        }
    
        for (int i = n - 1; i >= 1; i --) {
            r[i] = std::min(r[i], r[i + 1]);
        }
    
        int ans = 0;
        for (int i = 1; i <= n; i ++) ans += r[i] - i + 1;
        std::cout << ans << "\n";
    }
    signed main() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        
        int t = 1;
    
        while (t--) {
            solve();
        }
        
        return 0;
    }

[Problem - C - Codeforces]: https://codeforces.com/contest/652/problem/C
[155e04f8b5114d97a013247f06027577.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/f5b462f97c9444a7976ba003ec62f939.png
[73e66c83c91f4b348917364b9497e0c6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/cd50856361894a75be5d874d889bf7da.png