머지소트 트리

1. 

update가 이뤄지지 않으며 구간 [s,e]에서 x이상 원소의 수를 물어보는 쿼리

 

2.

포인트 update가 이뤄질 수 있으며 구간 [s,e]에서 x이상 원소의 존재성과 그 최소값을 물어보는 쿼리

 

위 1,2번 경우 기존 세그트리를 약간만 변형하여 머지소트 트리를 만들어 풀 수 있다.

1번은 각 세그 노드마다 벡터를, 2번은 set을 쓴다면 이분탐색으로 쉽게 풀 수 있다.

 

 

3. 

포인트 update가 이뤄질 수 있으며 구간 [s,e]에서 x이상 원소의 수를 물어보는 쿼리

 

3번 경우, 세그트리에 splay tree나 treap이나 데카르트트리따위를 넣어 해결할 수 있다고 한다.

->구현 매우 어려움. gcc 내장 트리를 사용한다면 쉬워질 수 있을 것 같다.

 

 

 

 

<코드 - 1>

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

const int MAX = 1e5 + 4;
const int SMAX = (1 << 18);

int n,qq;
vector<int> seg[SMAX];

void construct() {
	for (int i = SMAX / 2 - 1; i >= 1; i--) {
		seg[i] = seg[i * 2];
		seg[i].insert(seg[i].end(), seg[i * 2 + 1].begin(), seg[i * 2 + 1].end());
		sort(seg[i].begin(), seg[i].end());
	}
}

int val(int s, int e, int i, int ns, int ne, int k) {
	if (e < ns || ne < s) return 0;
	if (s <= ns && ne <= e) 
		return seg[i].end() - upper_bound(seg[i].begin(), seg[i].end(), k);
	int md = (ns + ne) / 2;
	return val(s, e, i * 2, ns, md, k) + val(s, e, i * 2 + 1, md + 1, ne, k);
}
int val(int s, int e, int k) {
	return val(s, e, 1, 0, SMAX / 2 - 1, k);
}

int main() {
	FAST; cin >> n;
	for (int i = 1,x; i <= n; i++) {
		cin >> x;
		seg[SMAX / 2 + i].push_back(x);
	}
	construct();
	cin >> qq;
	int last = 0;
	for (int i = 0, a, b, c; i < qq; i++) {
		cin >> a >> b >> c;
		a ^= last, b ^= last, c ^= last;
		//[a,b] 중 c보다 큰 원소개수
		last = val(a, b, c);
		cout << last << '\n';
	}
}

 

construct의 경우 머지소트하듯 nlogn으로 최적화할 수 있다. 하지만 어차피 쿼리 처리가 로그제곱이니 무용지물이라고 생각함.