c언어 16978번 수열과 쿼리 22 (백준)

#include <stdio.h>

long long int arr[100001]={};
long long int tree[400004]={};

void update(int s, int e, int node, int index, int val) { //segment tree update
	if(s > index || e < index) return;
	tree[node] += val;
	if(s == e) return;
	int m = (s+e)/2;
	update(s, m, node*2, index, val);
	update(m+1, e, node*2+1, index, val);
}

long long int find(int s, int e, int node, int l, int r) { //segment tree에서 부분합 구하기
	if(s > r || e < l) return 0;
	if(l <= s && e <= r) return tree[node];
	int m = (s+e)/2;
	return find(s, m, node*2, l, r) + find(m+1, e, node*2+1, l, r);
}

int main(void) {
	int n, m;
	scanf("%d", &n);
	for(int i=1; i<=n; i++) {
		scanf("%lld", &arr[i]); //요소들을 입력받고
		update(1, n, 1, i, arr[i]); //segment tree update
	}
	
	scanf("%d", &m); //쿼리 개수 입력
	long long int q[m][4]; //쿼리들을 담을 배열
	int left = 0, right = m-1; //0부턴 2번쿼리들을 m-1번에서 부턴 1번쿼리들을 저장
	for(int i=0; i<m; i++) { //쿼리입력 및 저장
		long long int a, b, c, d;
		scanf("%lld", &a);
		if(a==1) {
			scanf("%lld %lld", &b, &c);
			q[right][0] = b;
			q[right][1] = c;
			right--;
		}
		else {
			scanf("%lld %lld %lld", &b, &c, &d);
			q[left][0] = b;
			q[left][1] = c;
			q[left][2] = d;
			q[left][3] = left; //2번쿼리들의 입력을 받은 순서들도 넘겨줍니다. (마지막 순차적 출력을 위해서)
			left++;
		}
	}
	
	int gap = left/2, i, j, key[4];
	while(1) { //2번 쿼리 오름차순 정렬 , shell sort
		if(gap%2==0) gap++;
		for(i=gap; i<left; i++) {
			key[0] = q[i][0];
			key[1] = q[i][1];
			key[2] = q[i][2];
			key[3] = q[i][3];
			for(j=i-gap; j>=0; j-=gap) {
				if(key[0] < q[j][0]) {
					q[j+gap][0] = q[j][0];
					q[j+gap][1] = q[j][1];
					q[j+gap][2] = q[j][2];
					q[j+gap][3] = q[j][3];
				} else break;
			}
			q[j+gap][0] = key[0];
			q[j+gap][1] = key[1];
			q[j+gap][2] = key[2];
			q[j+gap][3] = key[3];
		}
		if(gap == 1) break;
		gap >>= 1;
	}

	long long int ans[left]; //부분합을 담을 배열
	
	int tmp = m-1;
    j=0;
	for(i=0; i<left; i++) { //순서대로 정렬된 2번쿼리와, 순서대로 저장해 놓은 1번쿼리를 이용하여 부분합을 구한 다음 위에서 만든 배열에 저장해두기
		while(q[i][0] > j) { //1번쿼리
			update(1, n, 1, q[tmp][0], q[tmp][1]-arr[q[tmp][0]]); //segment tree update 
			arr[q[tmp][0]] = q[tmp][1];
			j++;
			tmp--;
		}
		ans[q[i][3]] = find(1, n, 1, q[i][1], q[i][2]); //2번쿼리
	}
	
	for(i=0; i<left; i++) { //2번쿼리를 처음 받았던 순서대로 부분합을 출력해줍니다.
		printf("%lld\n", ans[i]);
	}
}

 

풀이 : 세그먼트 트리, 오프라인 쿼리

 

쿼리의 종류는 2가지 입니다.

1. 배열의 값 중 하나를 바꿉니다.

2. 1.쿼리가 몇번 적용된 이후의 특정 구간에서의 구간합을 구합니다.

 

여기서 2번 쿼리의 몇번 적용된 이후의 이 부분을 해결하기위해서  쿼리를 입력받자 마자 바로 처리하는 것이 아니라

일단 1번, 2번 쿼리들을 순서대로 각각 저장해 놓은 다음 2번 쿼리를 1번 쿼리가 몇번 적용된 이후에 적용되는지를 가지고 오름차순 정렬을 합니다.

 

오름차순 정렬을 한 후

2번 쿼리들을 처리하면 됩니다.

 

만약 2번쿼리를 처리하는데 1번쿼리가 2번쿼리가 요구하는 만큼 적용이 되지 않았다면, 만족할때까지 1번쿼리를 실행하여 세그먼트 트리를 update 하면 됩니다!

 

이렇게 2번쿼리들에 대한 부분합들을 구했다면,

 

이러한 부분합들을 2번쿼리들을 처음 입력 받았던 순서에 맞추어서 출력하면 됩니다!

 

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

16978번: 수열과 쿼리 22