BOJ 17408 수열과 쿼리 24

max 를 찾는 문제의 작은 변형.

 

tree 의 각 노드를 pair<int,int>로 두고 으뜸값과 버금값을 기록하면 된다.

func 는 두 개의 pair 의 네 값에서 으뜸과 버금을 찾아 pair 로 돌려준다.

 

tree 의 terminal node 는 입력값이 기록되어야 하므로 버금값은 입력되는 값보다 작은 아무 값이나 정하면 된다.

주어진 문제에서는 입력값이 자연수이므로 tree 의 기본값인 0 을 써도 상관없다.

음수가 허용되면 주석 처리한 부분을 살리면 된다. 

 

#include<bits/stdc++.h>

using namespace std;
using pii=pair<int,int>;

int arr[100001];
pii tree[300000];

pii func(pii a, pii b){
    pii res;
    int t;
    if(a.first>=b.first) {
        res.first=a.first;
        t=b.first;
    } else {
        res.first=b.first;
        t=a.first;
    }
    
    res.second=max(t, max(a.second, b.second));
    return res;
}

void init(int l,int r,int node){
    if(l==r) {
        tree[node].first=arr[l];
        //tree[node].seccond=-INT_MAX;
        return;
    }
    
    int mid=l+r>>1;
    init(l,mid,2*node), init(mid+1,r,2*node+1);
    tree[node]=func(tree[2*node], tree[2*node+1]);
}

void upd(int l,int r,int node, int p, int v){
    if(p<l || r<p) return;
    if(l==r) {
        tree[node].first=v;
        return;
    }
    
    int mid=l+r>>1;
    upd(l,mid,2*node,p,v), upd(mid+1,r,2*node+1,p,v);
    tree[node]=func(tree[2*node], tree[2*node+1]);
}

pii qry(int l,int r,int node, int ql, int qr){
    if(qr<l || r<ql) return {0,0};
    if(ql<=l && r<=qr) return tree[node];
    
    int mid=l+r>>1;
    return func(qry(l,mid,2*node,ql,qr), qry(mid+1,r,2*node+1,ql,qr));
}

int main(){
    int n; scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&arr[i]);
    init(1,n,1);
    
    int m; scanf("%d",&m);
    while(m--){
        int op; scanf("%d",&op);
        if(op==1){
            int p, v; scanf("%d%d", &p,&v);
            upd(1,n,1,p,v);
        } else {
            int l,r; scanf("%d%d",&l,&r);
            pii t=qry(1,n,1,l,r);
            printf("%d\n", t.first+t.second);
        }
    }
}