수열과 쿼리 22 [BOJ 16978]

'쿼리를 정렬'한다는 것은 세그먼트 트리를 처음 배우는 입장에서 쉽게 떠올릴 수 있는 것은 아니다. 하지만 해당 문제처럼 쿼리의 순서가 무의미할 때나 업데이트가 없는 오프라인 쿼리일 때는 매우 자주 이용하며, Mo's Algorithm의 기둥 중 하나가 되기도 한다. 또한 퍼시스턴트 세그먼트 트리로 조금 더 어렵게 풀 수 있기 때문에 퍼시스턴트 세그먼트 트리를 처음 배우는 사람들에게도 매우 좋은 문제이다. 현재는 쿼리 정렬 풀이만 올려놓았는데, 나중에 기회가 되면 퍼시스턴트 세그먼트 트리를 이용한 풀이도 업로드할 예정이다.

 

문제 요약

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

1 i v : A[i]=v로 update

2 k i j : k번째 update 쿼리까지 적용되었을 때 수열 A의 구간 [i, j]의 합을 출력

 

사용 알고리즘

정해 : 세그먼트 트리, 쿼리 정렬

별해 : 퍼시스턴트 세그먼트 트리

 

풀이

지금까지의 세그먼트 트리 문제들은 모든 출력 쿼리에 대해 '해당 쿼리가 들어오기 전까지 update 쿼리가 적용되었을 때'의 답을 출력하는 문제였고, 그래서 쿼리를 정렬할 필요가 없었다. 하지만 이 문제는 'k번째 update 쿼리까지 적용되었을 때'의 답을 출력하는 문제이기에 쿼리를 정렬하는 것이다. 즉, 지금까지의 세그먼트 트리와 정렬 기준이 바뀌었을 뿐, 전혀 다를 것이 없는 문제이다. 따라서 출력 쿼리를 k를 기준으로 정렬해주고, 각 출력 쿼리마다 k번째 update 쿼리까지 적용하면 쉽게 해결할 수 있다. 개인적으로 현재 티어인 P3도 고평가라고 생각한다.

 

코드

#include<bits/stdc++.h>
#define SIZE 100010
using namespace std;
typedef long long ll;
struct Query
{
    int s,e,idx;
    ll k;
};
ll N,M,A[SIZE],seg[SIZE<<2],lz[SIZE<<2],ans[SIZE];
vector<Query>upd,prn;
bool comp(Query x,Query y)
{
    return x.k<y.k;
}
ll init(int l,int r,int node)
{
    if(l==r)return seg[node]=A[l];
    int mid=l+r>>1;
    return seg[node]=init(l,mid,node<<1)+init(mid+1,r,(node<<1)+1);
}
ll update(int l,int r,int node,int s,ll w)
{
    if(l>s||r<s)return seg[node];
    if(l==s&&r==s)return seg[node]=w;
    int mid=l+r>>1;
    return seg[node]=update(l,mid,node<<1,s,w)+update(mid+1,r,(node<<1)+1,s,w);
}
ll query(int l,int r,int node,int s,int e)
{
    if(l>e||r<s)return 0;
    if(s<=l&&r<=e)return seg[node];
    int mid=l+r>>1;
    return query(l,mid,node<<1,s,e)+query(mid+1,r,(node<<1)+1,s,e);
}
int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>N;
    for(int i=1;i<=N;i++)cin>>A[i];
    init(1,N,1);
    cin>>M;
    for(int i=1;i<=M;i++){
        ll tc;Query Q;cin>>tc;
        if(tc-1){
            cin>>Q.k>>Q.s>>Q.e;
            Q.idx=prn.size()+1;
            prn.push_back(Q);
        }
        else{
            cin>>Q.s>>Q.k;
            upd.push_back(Q);
        }
    }
    sort(prn.begin(),prn.end(),comp);
    int j=0;
    for(auto i:prn){
        while(j<i.k){
            update(1,N,1,upd[j].s,upd[j].k);
            j++;
        }
        ans[i.idx]=query(1,N,1,i.s,i.e);
    }
    for(int i=1;i<=prn.size();i++)cout<<ans[i]<<'\n';
}