12899번 데이터 구조

 

세그먼트 트리를 응용한 문제이다. 이제 막 세그먼트 트리를 공부해서 처음엔 추가하는 것도 어려웠다. 추가하는 것은 set을 써도 가능하지만 세그먼트 트리를 공부하기 위한 것이니까 안 하고 고민을 해봤다. 그냥 세그먼트 트리에서 미리 다 만들어져 있다고 가정하고 일반적으로 Update 하듯이 값을 수정해주면 되었다. 그리고 값을 수정한 뒤 X번째로 작은 수를 찾아야 하는데 이 방법을 몰라서 세그먼트 트리를 다시 공부하였다. 

 

결국 방법은 트리 구조에서 마지막번째 레벨의 노드가 1~2000000까지 있게 만들었으므로 K번째 노드가 수 K를 나타내는 것으로 나타낼 수 있다. 그래서 각 노드의 값을 그 수의 개수로 입력하고 세그먼트 트리로 개수들의 합을 저장한다.

K 번째 수는 결국 왼쪽에 K개가 있으면 그 노드가 K번째 수이므로 위치의 수를 구할 수 있다. 

K가 왼쪽 노드의 수보다 클 경우 K - 왼쪽 노드의 개수를 다시 K로 하여 오른쪽 노드에서 찾는다.

 

간단히 이분탐색으로도 구할 수 있는 문제이다.

 

소스코드

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define fu(i,a,j) for(int i=a;i<j;i++)
#define fd(i,a,j) for(int i=a;i>=j;i--)
#define SYNC ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define MOD 998244353
#define MOD2 1000000021
#define INF 1e9
#define N 2000000
using namespace std;

typedef long long ll;
typedef long double ld;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); };
int n, m, k, t;
int dr[] = { 0,0,1,-1, -1,1,1,-1 };
int dc[] = { -1,1,0,0, 1,1,-1,-1 };

int seg[4 * N];
void update(int idx, int l, int r, int i, int val) {
	if (i<l || i>r) return;
	if (l == r) {
		seg[idx] += val;
		return;
	}
	int mid = (l + r) >> 1;
	update(idx << 1, l, mid, i, val);
	update(idx << 1 | 1, mid + 1, r, i, val);
	seg[idx] = seg[idx << 1] + seg[idx << 1 | 1];
}

int getval(int idx, int l, int r, int k) {
	if (l == r) {
		return l;
	}
	int mid = (l + r) >> 1;
	if (k <= seg[idx << 1])
		return getval(idx << 1, l, mid, k);
	return getval(idx << 1 | 1, mid + 1, r, k - seg[idx << 1]);
}

int main() {
	SYNC;
	memset(seg, 0, sizeof seg);
	cin >> t;
	while (t--) {
		int a, x;
		cin >> a >> x;
		if (a == 1) {
			update(1, 1, N, x, 1);
		}
		else {
			int pos = getval(1, 1, N, x);
			update(1, 1, N, pos, -1);
			cout << pos << '\n';
		}
	}
	return 0;
}