수열과 쿼리 17 [BOJ 14438]

https://unorderedmap.tistory.com/12

수열과 쿼리 16 [BOJ 14428]

수열과 쿼리 15, 16과 거의 같은 문제이다. 단, 최솟값의 인덱스가 아니라 최솟값만을 구한다는 점에서 조금 다르다.

 

문제 요약

길이 10만 이하의 수열에서 2가지 쿼리를 수행한다.

1 i v : i번째 값을 v로 바꾼다.

2 i j : 수열의 i번째 원소부터 j번째 원소까지 중에서 최솟값을 출력한다.

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

 

사용 알고리즘

세그먼트 트리

 

풀이

최솟값을 담는 세그먼트 트리에 대한 가장 기본적인 문제이다. 각 노드에는 해당 구간에서의 최솟값을 저장해준뒤, 쿼리들을 모두 시간복잡도 O(logN)에 처리해주면 된다. 전체 시간복잡도 O(NlogN)으로 문제를 해결해줄 수 있다.

 

코드

#include<bits/stdc++.h>
#define SIZE 100010
using namespace std;
int N,Q,A[SIZE],seg[SIZE*4];
void init(int l,int r,int node)
{
    if(l>r)return;
    if(l==r){
        seg[node]=A[l];
        return;
    }
    int mid=l+r>>1;
    init(l,mid,node*2);
    init(mid+1,r,node*2+1);
    seg[node]=min(seg[node*2],seg[node*2+1]);
}
void update(int l,int r,int node,int s,int w)
{
    if(l>r)return;
    if(l==s&&r==s){
        seg[node]=w;
        return;
    }
    if(l>s||r<s)return;
    int mid=l+r>>1;
    update(l,mid,node*2,s,w);
    update(mid+1,r,node*2+1,s,w);
    seg[node]=min(seg[node*2],seg[node*2+1]);
}
int query(int l,int r,int node,int s,int e)
{
    if(l>r)return 1e9;
    if(s<=l&&r<=e)return seg[node];
    if(l>e||r<s)return 1e9;
    int mid=l+r>>1;
    return min(query(l,mid,node*2,s,e),query(mid+1,r,node*2+1,s,e));
}
int main()
{
    cin>>N;
    for(int i=1;i<=N;i++)scanf("%d",&A[i]);
    init(1,N,1);
    for(cin>>Q;Q--;){
        int tc,s,e;scanf("%d %d %d",&tc,&s,&e);
        if(tc-1)printf("%d\n",query(1,N,1,s,e));
        else update(1,N,1,s,e);
    }
}

 

https://unorderedmap.tistory.com/13

1일 1수쿼 기록장