백준 소스코드 [C++] 17408 수열과 쿼리 24

www.acmicpc.net/problem/17408

17408번: 수열과 쿼리 24

백준 소스코드 [C++] 17408 수열과 쿼리 24

#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#include <limits.h>
#include <vector>
#include <math.h>
#include <stack>
#include <bitset>
#include <string>
#include <set>
#define all(v) v.begin(), v.end()
#define pii pair<int,int>
#define make_unique(v) v.erase(unique(v.begin(), v.end()), v.end())
typedef long long ll;
using namespace std;

int n,m;
vector<int> arr;
vector<pii> tree;

pii init(int i, int l, int r){
  if(l==r) {
    tree[i]=make_pair(arr[l],l);
    return tree[i];
  }
  pii L = init(2*i,l,(l+r)/2);
  pii R = init(2*i+1,(l+r)/2+1,r);
    if(L.first > R.first) tree[i]=L;
    else tree[i]=R;
    return tree[i];
}

pii update(int i,int l,int r,int idx, int val){
    if(idx<l || r<idx) return tree[i];
    if(l==r) {
        tree[i]=make_pair(val,idx);
        return tree[i];
    }
    int m=(l+r)/2;
    pii Lres=update(2*i,l,m,idx,val);
    pii Rres=update(2*i+1,m+1,r,idx,val);
    if(Lres.first > Rres.first) tree[i]=Lres;
    else tree[i]=Rres;
    return tree[i];
}

pii query(int i,int l,int r, int L,int R){
    if(r<L || R<l) return make_pair(-1,-1);
    if(L<=l && r<=R) return tree[i];
    int m=(l+r)/2;
    pii Lres=query(2*i,l,m,L,R);
    pii Rres=query(2*i+1,m+1,r,L,R);
    if(Lres.first > Rres.first) return Lres;
    else return Rres;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n;
    arr.resize(n);
    tree.resize(4*n);
    for(int i=0;i<n;i++) cin>>arr[i];
    init(1,0,n-1);
    cin>>m;
    int order,l,r,v;
    while(m--){
        cin>>order;
        if(order==1){
            cin>>l>>v;
            update(1,0,n-1,l-1,v);
        }
        else{
            cin>>l>>r;
            pii First=query(1,0,n-1,l-1,r-1);
            pii LSecond=query(1,0,n-1,l-1,First.second-1);
            pii RSecond=query(1,0,n-1,First.second+1,r-1);
            cout<<First.first + max(LSecond.first,RSecond.first)<<'\n';
        }
    }
    return 0;
}