[BOJ] 13537 | 수열과 쿼리 1

문제

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

풀이

수열을 다음과 같은 업데이트 쿼리로 해석한다.

a b : 위치가 a인 위치를 b로 교체

그리고 쿼리 (i j k)를 k에 대해 내림차순으로 정렬한다.

업데이트 쿼리들도 마찬가지로, b에 대해 내림차순으로 정렬한다.

그리고, k>b를 만족할때, 세그먼트 트리에서 위치가 a인 곳에 1을 업데이트 한다.

그러면, 트리에서 i부터 j까지의 합이 쿼리 (i j k)에 대한 답변이 된다.

출력할때도, 쿼리의 입력순으로 정렬해주자.

소스

#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#define ll long long
using namespace std;

struct _ { ll idx, i, j, k; };
bool operator<(_ a, _ b) { return a.k > b.k; }
vector<_> query;
vector<pair<ll, ll> >arr, ans;
ll N, MAX, tree[400000], M;

void update(ll p, ll v) {
	p += MAX;
	tree[p] = v;
	for (; p /= 2; tree[p] = tree[2 * p] + tree[2 * p + 1]);
}

ll sum(ll s, ll e) {
	ll res = 0;
	s += MAX, e += MAX;
	while (s < e) {
		if (s % 2)
			res += tree[s++];
		if (e % 2 == 0)
			res += tree[e--];
		e /= 2;
		s /= 2;
	}
	if(s==e)
		res += tree[e];
	return res;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> N;
	for (MAX = 1; MAX < N; MAX *= 2);
	for (int i = 1; i <= N; i++) {
		ll tmp;
		cin >> tmp;
		arr.push_back({ tmp,i });
	}
	cin >> M;
	for (int i = 0; i < M; i++) {
		ll a, b, c;
		cin >> a >> b >> c;
		query.push_back({ i,a,b,c });
	}
	sort(arr.begin(), arr.end(), greater<pair<ll, ll> >() );
	sort(query.begin(), query.end());
	ll now = 0;
	for (auto idx : query) {
		while (now < arr.size() && idx.k < arr[now].first) {
			update(arr[now].second, 1);
			now++;
		}
		ans.push_back({ idx.idx, sum(idx.i,idx.j) });
	}
	sort(ans.begin(), ans.end());
	for (auto idx : ans)
		cout << idx.second << "\n";
}