Codeforces Round #553 Div.2 E - Number of Components

深碍√TFBOYSˉ_ 2021-11-08 17:22 201阅读 0赞

# 思维题 #

又是一道完全不会的题qwq

将一条链划分成若干个联通块，其实就是划分成一些区间。每个区间都会有左端点和右端点，且当一个点作为左端点的时候，必定有一个点作为右端点(都是废话)

那么我们只要把每个点能作为左端点的区间数加起来就是答案啦，右端点的就不用统计了，因为每一个点作为左端点都对应了另一个点作为右端点。

如何统计呢？当然是取决于前一个点的值啦！

如果val\[i - 1\] > val\[i\],那么可以组成的区间要满足1 <= l <= val\[i\] <= r < val\[i - 1\], 算出来的答案就是 val\[i\] \* (val\[i - 1\] - val\[i\])

如果val\[i - 1\] < val\[i\],那么可以组成的区间要满足val\[i - 1\] < l <= val\[i\] <= r <= n, 算出来的答案就是 (val\[i\] - val\[i - 1\]) \* (n - val\[i\] + 1)

#include <bits/stdc++.h>
    #define INF 0x3f3f3f3f
    #define full(a, b) memset(a, b, sizeof a)
    using namespace std;
    typedef long long ll;
    inline int lowbit(int x){ return x & (-x); }
    inline int read(){
        int X = 0, w = 0; char ch = 0;
        while(!isdigit(ch)) { w |= ch == '-'; ch = getchar(); }
        while(isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
        return w ? -X : X;
    }
    inline int gcd(int a, int b){ return a % b ? gcd(b, a % b) : b; }
    inline int lcm(int a, int b){ return a / gcd(a, b) * b; }
    template<typename T>
    inline T max(T x, T y, T z){ return max(max(x, y), z); }
    template<typename T>
    inline T min(T x, T y, T z){ return min(min(x, y), z); }
    template<typename A, typename B, typename C>
    inline A fpow(A x, B p, C lyd){
        A ans = 1;
        for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd;
        return ans;
    }
    const int N = 100005;
    int a[N], n;
    ll ans;
    int main(){
    
        ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
        cin >> n;
        for(int i = 1; i <= n; i ++) cin >> a[i];
        ans += 1LL * a[1] * (n - a[1] + 1);
        for(int i = 2; i <= n; i ++){
            if(a[i] < a[i - 1]) ans += 1LL * a[i] * (a[i - 1] - a[i]);
            else if(a[i] > a[i - 1]) ans += 1LL * (a[i] - a[i - 1]) * (n - a[i] + 1);
        }
        cout << ans << endl;
        return 0;
    }

转载于:https://www.cnblogs.com/onionQAQ/p/10832497.html