머지소트트리

int arr[100002];
vector<int> tree[4 * 100002];
int N, M, K;

void update(int bucket, int start, int end, int node,  int x) {
	if (node < start || end < node) return;

	tree[bucket].push_back(x);

	if (start != end) 
	{
		update(bucket * 2, start, (start + end) / 2, node, x);
		update(bucket * 2 + 1, (start + end) / 2 + 1, end,  node,  x);
	}
}

int query(int node, int start, int end, int left, int right, int x) {
	if (left > end || right < start) 
		return 0;
	if (left <= start && end <= right) 
		return tree[node].end() - upper_bound(tree[node].begin(), tree[node].end(), x);

	int mid = (start + end) >> 1;

	return query(node * 2, start, mid, left, right, x) + query(node * 2 + 1, mid + 1, end, left, right, x);
}


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

	rep1(i, N)
	{
		int tmp;
		cin >> tmp;
		update(1, 1, N, i, tmp);
	}

	rep(i, 4 * 100002)
	{
		sort(tree[i].begin(), tree[i].end());
	}

	cin >> M;
	rep(i, M) 
	{
		int a, b, c;

		cin >> a >> b >> c;
		cout << query(1, 1, N, a, b, c)<<'\n';
	}


	return 0;
}

 

간단히 보자면 기존의 세그같은 느낌인데 리프 노드에서 올라갈수록 수열이 합쳐지는 세그트리 신기한듯