BOJ 16221 - 모독
역시 플레 4~5 는 세그먼트 트리의 밭이다.
굉장히 많이나오고 사실 플레티넘 문제를 푼것같은 느낌이 안든다.
이 문제는 각 칸에 얼마나 수가 있는지를 추적하면서 하나도 없어졌을 때나 0에서 1이 되었을 때만 세그먼트 트리에 값을 업데이트 해주고 이분탐색으로 1부터 어디까지 이어져있는지 찾아주면 된다.
시간복잡도는 이다.
어디까지 이어져있는지 찾았다면 구해야하는건 결국 모든 개수의 합이므로 합을 관리하는 세그먼트 트리는 따로 관리해서 쿼리해주면 된다.
const int MAX = 1000000;
void solve() {
int q;
cin >> q;
fenwick<int> fenw(MAX + 1), fenw_sum(MAX + 1);
vi cnt(MAX + 1);
cnt[0] = 1;
int last_ans = 0;
while (q--) {
int a, b;
cin >> a >> b;
if (a == 1) {
fenw_sum.update(b, 1);
cnt[b]++;
if (cnt[b] == 1) fenw.update(b, 1);
} else {
fenw_sum.update(b, -1);
cnt[b]--;
if (cnt[b] == 0) fenw.update(b, -1);
}
int l = 0, r = MAX, ret = 0;
while (l <= r) {
int m = l + r >> 1;
if (fenw.query(0, m) == m - 1 + 1) {
ret = m;
l = m + 1;
} else r = m - 1;
}
last_ans = ret;
cout << fenw_sum.query(1, ret) << endl;
}
}
Comments