수열과 쿼리 15 [BOJ 14427]

오늘부터 1일 1수쿼 도전을 하려고 한다. 안 풀었던 수열과 쿼리 문제 중 하나를 풀거나, 푼 수열과 쿼리 문제 중 하나의 풀이를 작성하는 것 중 하나를 매일 할 것이다. (할 수 있을까...?)

 

문제 요약

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

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

2 : 수열에서 가장 작은 값을 가지는 인덱스를 출력한다. 단, 최솟값이 여러 개일 경우 가장 작은 인덱스를 출력한다.

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

 

사용 알고리즘

세그먼트 트리

 

풀이

pair을 담는 세그먼트 트리를 잡자. first에는 해당 구간의 최솟값, second에는 해당 구간에서 최솟값을 가지는 가장 작은 인덱스를 저장한다. pair은 크기 비교 시 first가 작은 것이 먼저, first가 같은 경우 second가 작은 것이 먼저이므로 가장 기본적인 min seg를 통해 구현할 수 있다.

출력 쿼리가 전체 구간에 대해서만 들어오므로 쿼리 함수를 작성할 필요 없이 seg[1].second의 값을 출력해주면 된다.

 

코드

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

 

https://unorderedmap.tistory.com/13

1일 1수쿼 기록장