쓰담쓰담 (백준 12741)

안녕하세요. 오늘은 쓰담쓰담해줄거예요.

문제

https://www.acmicpc.net/problem/12741

아이디어

arr[i]-arr[i-1]를 diff[i-1]이라고 합시다.
어떠한 구간이 증가하는지 확인하려면 diff값이 다 0이상인지, 즉 최솟값이 0이상인지 확인해주면 됩니다.
diff를 가지고 세그트리를 만든 다음에 change만 잘 해주면 됩니다.

소스코드

#include <iostream>
#define ll long long
using namespace std;

ll tree[404040] = { 0 };
ll arr[101010] = { 0 }, diff[101010] = { 0 };
ll init(ll s, ll e, ll node)
{
    if (s == e) return tree[node] = diff[s];
    ll mid = (s + e) / 2;
    return tree[node] = min(init(s, mid, node * 2), init(mid + 1, e, node * 2 + 1));
}
ll MIN(ll s, ll e, ll node, ll l, ll r)
{
    if (e < l || r < s) return 2e9;
    if (l <= s && e <= r) return tree[node];
    ll mid = (s + e) / 2;
    return min(MIN(s, mid, node * 2, l, r), MIN(mid + 1, e, node * 2 + 1, l, r));
}
void change(ll s, ll e, ll node, ll idx, ll val) //diff[idx]를 val로 바꾸기
{
    if (e < idx || idx < s) return;
    if (s == e)
    {
        tree[node] = val;
        return;
    }
    ll mid = (s + e) / 2;
    change(s, mid, node * 2, idx, val);
    change(mid + 1, e, node * 2 + 1, idx, val);
    tree[node] = min(tree[node * 2], tree[node * 2 + 1]);
}

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N, Q, i, a, b, c;
    cin >> N >> Q;
    for (i = 1; i <= N; i++)
    {
        cin >> arr[i];
        diff[i - 1] = arr[i] - arr[i - 1];
    }
    init(1, N, 1);

    for (i = 0; i < Q; i++)
    {
        cin >> a >> b >> c;
        if (a == 1)
        {
            if (b == c || MIN(1, N, 1, b, c - 1) >= 0) //증가한다면
                cout << "CS204\n";
            else //아니라면
                cout << "HSS090\n";
        }
        else
        {
            swap(arr[b], arr[c]);
            change(1, N, 1, b - 1, arr[b] - arr[b - 1]);
            change(1, N, 1, b, arr[b + 1] - arr[b]);
            change(1, N, 1, c - 1, arr[c] - arr[c - 1]);
            change(1, N, 1, c, arr[c + 1] - arr[c]);
        }
    }
}

감사합니다.