[BOJ 16978] 수열과 쿼리 22

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

16978번: 수열과 쿼리 22

 

- 문제 요약

 

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

• 1 i v : Ai = v로 변경한다
• 2 k i j : k번째 1번 쿼리까지 적용되었을 때, Ai, Ai+1, ... , Aj의 합을 출력한다.

모든 2번 쿼리마다 합을 출력한다.

 

 

- 알고리즘 정리

 

https://velog.io/@rnmkr/offline-query

offline query

 

오프라인 쿼리를 사용해서 풀었습니다.

쿼리를 전부 입력받고 k 기준으로 정렬해준 다음, 수행해 줍니다.

출력할 때는 원래 순서로 바꿔서 출력해 줍니다.

 

+) Ai의 최대 값이 1,000,000이므로, 변수 타입은 마음 편하게 long long으로 선언해 줬습니다

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 100001
typedef long long ll;
int n,m,co;
struct st{
	int k,ss,ee,idx;
};
ll tree[MAX*4],arr[MAX];

void update(int node,int s,int e,int k,int idx){
    if(e<idx||idx<s){
    	return;
	}
	tree[node]+=k;
	if(s==e){
		return;
	}
	int mid=(s+e)/2;
	update(2*node,s,mid,k,idx);
	update(2*node+1,mid+1,e,k,idx);
}

ll query(int node,int s,int e,int ss,int ee){
    if(e<ss||ee<s){
    	return 0;	
	}
	if(ss<=s&&e<=ee){
		return tree[node];
	}
	int mid=(s+e)/2;
	return query(2*node,s,mid,ss,ee)+query(2*node+1,mid+1,e,ss,ee);
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	for(int i=1;i<=n;i++){
		int a;
		cin>>a;
		update(1,0,n,a,i);
	}
	vector<pair<int,int> >a;
	vector<st>b;
	cin>>m;
	for(int i=0;i<m;i++){
		int c;
		cin>>c;
		if(c==1){
			int x,y;
			cin>>x>>y;
			a.push_back({x,y});
		}
		else if(c==2){
			int x,y,z;
			cin>>x>>y>>z;
			b.push_back({x,y,z,co++});
		}
	}
	sort(b.begin(),b.end(),[](st &a,st &b){ 
        return a.k<b.k; 
    });
    int k=0;
    for(int i=0;i<a.size();i++){
    	while(b[k].k==i){
    		auto [x,ss,ee,ret]=b[k];
    		arr[ret]=query(1,0,n,ss,ee);
    		k++;
		}
		auto [idx,k]=a[i];
		k=k-query(1,0,n,idx,idx);
		update(1,0,n,k,idx);
	}
	int w=b.size();
	for(int i=k;i<w;i++){
		arr[b[i].idx]=query(1,0,n,b[i].ss,b[i].ee);
	}
	for(int i=0;i<w;i++){
		cout<<arr[i]<<'\n';
	}
}

코드 제출 결과

세그 트리 짤 때마다 스스로 뭘 짜고 있는 건지 모르겠다는 생각이 듭니다

다른 PS러 분들 보면 그냥 멍 때리면서 간단한 세그 트리 코드 쭉 짜던데...

DP 혐오증도 이겨냈으니 세그 트리 혐오증도 이겨낼 수 있겠죠..? ㅎ.... 그렇다고 해주세요....

 

(수열과 쿼리 시리즈 올솔하는 그날까지...!)