D. Lipshitz Sequence

Disjoint Set Union(dsu)


출처: Codeforces D. Lipshitz Sequence

sol)
최대값은 인덱스가 1차이나는 값들로 정해진다.
(붙어있는 수 들로)
dsu로 최대값이 어디까지 갈 수 있는지 계산을 하고 출력.




[-] Collapse

#include<stdio.h>
#include<algorithm>
#include<cstring>
using namespace std;

typedef long long ll;

ll ori[100010];
ll can_left[100010];
ll can_right[100010];
pair<ll, int> L[100010];
int par[100010];
int n, q;

int find(int idx){
    if (par[idx] == idx) return idx;
    else return par[idx] = find(par[idx]);
}
void merge(int u, int v){
    u = find(u); v = find(v);
    par[v] = u;
}

int main(){
// freopen("input.txt", "r", stdin);
    memset(can_left, -1, sizeof(can_left));
    memset(can_right, -1, sizeof(can_right));
    for (int i = 0; i < 100010; i++) par[i] = i;
    scanf("%d %d", &n, &q);
    for (int i = 1; i <= n; i++) scanf("%lld", &ori[i]);
    for (int i = 1; i <= n - 1; i++)
        L[i] = make_pair(abs(ori[i] - ori[i + 1]), i);
    for (int i = 1; i <= n - 1; i++) ori[i] = L[i].first;

    ori[n] = ori[0] = 100000001;
    sort(L + 1, L + 1 + n - 1);

    for (int i = 1; i <= n - 1; i++){
        ll v = L[i].first;
        int idx = L[i].second;
        can_left[idx] = can_right[idx] = idx;
        if (can_left[idx-1] != -1 && ori[idx - 1] <= v){
            can_left[idx] = can_left[find(idx - 1)];
            merge(idx, idx - 1);
        }
        if (can_right[idx+1] != -1 && ori[idx + 1] <= v){
            can_right[idx] = can_right[find(idx + 1)];
            merge(idx, idx + 1);
        }
    }
    for (int i = 0; i < q; i++){
        ll l, r; scanf("%lld %lld", &l, &r);
        ll ans = 0;
        for (ll idx = l; idx < r; idx++){
            ll left, right;
            left = idx - max(can_left[idx], l) + 1;
            right = min(can_right[idx], r - 1) - idx + 1;
            ans += ori[idx] * left * right;
        }
        printf("%lld\n", ans);
    }

    return 0;
}