백준13544 수열과 쿼리 3

작성일 | In

문제 링크

  • http://icpc.me/13544

사용 알고리즘

  • Segment Tree
  • Merge Sort Tree

시간복잡도

  • O(Q log2 N)

풀이

입력이 매우 이상합니다.
i, j, k가 단순히 입력으로 결정되는 것이 아닌, 입력된 값과 바로 이전 정답을 xor한 값으로 결정됩니다.
이런 입력은 주로 grader를 안 쓰는 batch 형식의 문제에서 online을 강제할 때 많이 나옵니다.

offline으로 처리하면 단순히 세그먼트 트리를 이용해 log시간에 처리가 가능하지만, online으로 처리하면 머지 소트 트리를 이용해서 log제곱에 처리하거나, PST를 써서 log시간에 처리하면 됩니다.

머지 소트 트리의 설명과 오프라인 처리에 대한 설명은 여기 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;

vector<int> tree[404040];

void update(int node, int s, int e, int x, int v){
	if(x < s || e < x) return;
	tree[node].push_back(v);
	if(s ^ e){
		int m = s + e >> 1;
		update(node*2, s, m, x, v);
		update(node*2+1, m+1, e, x, v);
	}
}

int query(int node, int s, int e, int l, int r, int k){
	if(r < s || e < l) return 0;
	if(l <= s && e <= r) return tree[node].end() - upper_bound(tree[node].begin(), tree[node].end(), k);
	int m = s + e >> 1;
	return query(node*2, s, m, l, r, k) + query(node*2+1, m+1, e, l, r, k);
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	for(int i=1; i<=n; i++){
		int t; cin >> t;
		update(1, 1, n, i, t);
	}
	for(int i=0; i<404040; i++) sort(tree[i].begin(), tree[i].end());
	int ans = 0;
	int q; cin >> q;
	while(q--){
		int i, j, k; cin >> i >> j >> k;
		int a = i ^ ans;
		int b = j ^ ans;
		int c = k ^ ans;
		ans = query(1, 1, n, a, b, c);
		cout << ans << "\n";
	}
}