[백준 16978] 수열과 쿼리 22

[ghdcksgml1]

아이디어

• 1 i v : 면 A_i를 v로만 바꿔준다.
• 2 k i j : k번째 1번 쿼리까지 적용되었을 때, i에서 j 구간의 합을 출력한다.

이 문제에서 k만 없었어도 난이도는 굉장히 쉬웠을 것 같다. (세그먼트 트리로 구간합만 구하면 돼서)

하지만 특정 시점에서 적용된 쿼리에 대한 구간의 합을 구해야하기 때문에

이 문제는 오프라인 쿼리로 풀어야겠다고 생각했다.

오프라인 쿼리는 다음과 같이 구현했다.

1일때 변경해야하는 쿼리와, 2일때 변경해야하는 쿼리를 각각 따로 저장해서 관리한다.

2일때 저장해놓은 구간에 대한 쿼리를 k를 기준으로 오름차순으로 정렬해준다.

그 이유는, 이렇게 정렬해서 하나씩 쿼리를 구하면, 예를들어 7번째 적용했던 1번 쿼리에서 1번째 적용했던 1번 쿼리를 구해야하는 것처럼 반대로 넘어가는 것을 막을 수 있다.

(즉, 무조건 k는 증가하는 순으로 나오기때문에 과거 시점으로 돌아가 1번 쿼리를 구할 일이 없다.)

이렇게 각각의 값을 구하면 완성!!

시간복잡도

오프라인쿼리로 풀기때문에 시간 복잡도는 k번째 조건이 없을때와 같은 O(M logN) 이다.

소스코드

// 언어 : C++ , (성공/실패) : 1/0 , 메모리 : 10936 KB , 시간 : 84 ms
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h> // memset
#define MAX 100001

using namespace std;
typedef long long ll; // value의 값이 1,000,000 이기 때문에 int 범위를 넘어갈 수 있다.

struct Tree{
    ll value;
}tree[MAX*4];

// 오프라인 쿼리를 위해 만든 구조체
class Query{
public:
    ll idx,k,i,j; // idx를 꼭 받아줘야함
    Query(ll idx,ll k,ll i,ll j){
        this->idx = idx;
        this->k = k;
        this->i = i;
        this->j = j;
    }
};

ll arr[MAX]; // 처음 N개의 수를 받을 배열
vector<pair<int,int>> ch; // 1번 쿼리를 저장하는 벡터
vector<Query> query; // 2번 쿼리를 저장하는 벡터
ll query_res[MAX]; // 쿼리의 정답

bool compare(Query a,Query b){
    return a.k < b.k; // k를 기준으로 오름차순으로 정렬
}

// 세그먼트 트리 구현
ll buildRec(int node,int start,int end){
    if(start == end){
        return tree[node].value = arr[start];
    }
    int mid = (start + end) / 2;
    return tree[node].value = buildRec(node*2,start,mid) + buildRec(node*2+1,mid+1,end);
}

// 구간의 합을 구하는 쿼리
ll queryRec(int left,int right,int node,int start,int end){
    if(left>end || right<start) return 0;
    if(left<=start && end<=right){
        return tree[node].value;
    }
    int mid = (start + end) / 2;
    return queryRec(left,right,node*2,start,mid) + queryRec(left,right,node*2+1,mid+1,end);
}

// 숫자를 업데이트 하는 쿼리
ll updateRec(int i,ll v,int node,int start,int end){
    if(i>end || i<start) return tree[node].value;
    if(start == end){
        return tree[node].value = v;
    }
    int mid = (start + end) / 2;
    return tree[node].value = updateRec(i,v,node*2,start,mid) + updateRec(i,v,node*2+1,mid+1,end);
}

int main(void){
    // 입출력 속도 최적화
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int N; cin>>N;
    for(int i=1;i<=N;i++){
        ll tmp; cin>>tmp;
        arr[i] = tmp;
    }

    buildRec(1,1,N); // 세그먼트 트리 생성

    int M; cin>>M;
    int q_idx = 0;
    for(int ii=0;ii<M;ii++){
        int num; cin>>num;
        // 각각의 쿼리를 받고 바로 계산하지 말고 따뤄 나눠서 저장해두기
        if(num==1){
            int i;ll v; cin>>i>>v;
            ch.push_back({i,v});
        }else{
            int k,i,j; cin>>k>>i>>j;
            query.push_back({q_idx,k,i,j});
            q_idx++;
        }
    }

    sort(query.begin(), query.end(),compare);

    int cur_k = 0;
    // 오프라인 쿼리
    for(auto q : query){
        if(cur_k != q.k){
            for(int i=cur_k;i<q.k;i++) {
                updateRec(ch[i].first,ch[i].second,1,1,N);
            }
            cur_k = q.k;
        }
        query_res[q.idx] = queryRec(q.i,q.j,1,1,N);
    }

    // 결과 출력
    for(int i=0;i<query.size();i++){
        cout<<query_res[i]<<'\n';
    }

    return 0;
}

크~ 점수 달다~

[jusung-c]

세그먼트 트리도 일반 코테에서 자주 나오는 유형인가요??

[ghdcksgml1]

ㅋㅋㅋ 절대 나올일 없습니다! 백준 점수올리기용

[jusung-c]

휴.. 어지러울 뻔