백준: Class 6 - 14428, 15824

</br> 클래스 6 계속
</br>

14428: 수열과 쿼리 16

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

#include <bits/stdc++.h>
#define MOD 1000000007

using namespace std;

int nums[100001];
vector< pair<int, int> > segtree;

pair<int, int> makeSeg(int a, int b, int now){
    if( a == b ) return segtree[now] = make_pair(nums[a], a);
    int mid = (a+b) / 2;
    return segtree[now] = min(makeSeg(a, mid, now*2), makeSeg(mid+1, b, now*2+1));
}

pair<int, int> minSeg(int a, int b, int now, int l, int r){
    if( r < a || b < l ) return make_pair(INT_MAX, a);
    if( l <= a && b <= r ) return segtree[now];
    int mid = (a+b) / 2;
    return min(minSeg(a, mid, now*2, l, r), minSeg(mid+1, b, now*2+1, l, r));
}

pair<int, int> updateSeg(int a, int b, int now, int ind, int change){
    if( ind < a || b < ind ) return segtree[now];
    if( a == b ){
        segtree[now].first = change;
        return segtree[now];
    }
    int mid = (a+b) / 2;
    return segtree[now] = min(updateSeg(a, mid, now*2, ind, change), updateSeg(mid+1, b, now*2+1, ind, change));
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    for(int i = 0; i < n; i++){
        cin >> nums[i];
    }

    int h = ceil(log2(n));
    segtree.assign(1 << (h+1), make_pair(0, 0));
    makeSeg(0, n-1, 1);

    int m;
    cin >> m;

    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        if( a == 1 ){
            updateSeg(0, n-1, 1, b-1, c);
            nums[b] = c;
        }
        else{
            cout << minSeg(0, n-1, 1, b-1, c-1).second + 1 << '\n';
        }
    }

}

또 세그먼트 트리
간단하다 전 포스트(2357: 최솟값과 최댓값, https://cyj893.github.io/algorithm/Algorithm17_5/)와 같이 그냥 최솟값 구하면 되는데, 얘는 인덱스를 출력해야 하므로 (최솟값, 최솟값의 인덱스) 페어로 세그먼트 트리에 저장했다.
최솟값이 만약 같다면 인덱스가 작은 순이므로, 그냥 페어 비교로 작은 거 골라 주면 된다.
</br>

15824: 너 봄에는 캡사이신이 맛있단다

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

방법 1.

#include <bits/stdc++.h>
#define MOD 1000000007

using namespace std;

int nums[300001];
int pows[300001];

long long mypow(long long a, int b){
    if( pows[b] ) return pows[b];
    if( b == 0 ) return 1;
    if( b == 1 ) return a;
    if( b % 2 ) return pows[b] = a*mypow(a, b-1) % MOD;
    long long aa = mypow(a, b/2) % MOD;
    return pows[b] = aa*aa % MOD;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    for(int i = 0; i < n; i++){
        cin >> nums[i];
    }

    sort(nums, nums+n);

    long long ans = 0;
    for(int i = 0; i < n-1; i++){
        for(int j = i+1; j < n; j++){
            ans += mypow(2, j-i-1) * (nums[j] - nums[i]);
            ans %= MOD;
        }
    }

    cout << ans << endl;

}

어떻게 풀까 보니까 조합에서 최댓값과 최솟값의 차만 구하면 된다.
그래서 정렬해서 보니까,

ex) 백준 예제
1 4 5 5 6 10

현재 조합을 i~j에서 만든다면(i와 j를 꼭 포함), 주헌고통지수는 nums[j]-nums[i]와 같다.  

1~4: 4-1 = 3이 1개  -> 2^0
1~5: 5-1 = 4가 2개  -> 2^1
1~5: 5-1 = 4가 4개  -> 2^2
...
(nC0 + nC1 + ... + nCn = 2^n이므로)

이렇게 풀면 50점 받는다.
n이 300000이면 포문 두 번 도니까 시간초과 나기 때문…

일단 방향은 맞는 거 같으니까 압축해 보자
</br>

방법 2.

위 예제에서, 더해지는 만큼과 빼지는 만큼을 각 수마다 출력해 봤다.

ex) 백준 예제
1 4 5 5 6 10

1: -1 -2 -4 -8 -16
4:  1 -1 -2 -4 -8
5:  2  1 -1 -2 -4
5:  4  2  1 -1 -2
6:  8  4  2  1 -1
10: 16 8  4  2  1
즉 1*(-31) + 4*(1-15) + 5*(3-7) + 5*(7-3) + 6*(15-1) + 10*(31) = 307

아하~~ 2^(n-1-i)-1 만큼은 빼지고, 2^i-1 만큼은 더해지는구나

따라서 바꾼 코드는

    for(int i = 0; i < n; i++){
        ans -= (mypow(2, n-i-1) - 1) * nums[i];
        ans %= MOD;
        ans += (mypow(2, i) - 1) * nums[i];
        ans %= MOD;
    }
}

250점 맞았다 굿

</br>

---

개강해서 슬프다
</br>