[BOJ] 13553 수열과 쿼리 8

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

13553번: 수열과 쿼리 8

알고리즘: Mo's, Fenwick tree

 

시간복잡도: $O((N+M)\sqrt NlogN)$

---

$|A_i-A_j|\le K$를 풀어쓰면, $A_i-K\le A_j \le A_i+K$가 된다.

 

Mo's 로 접근해보면, $A_i$를 추가 및 삭제를 할 때 위 구간을 만족하는 $A_j$의 개수를 더해주거나 빼주면 된다.

특정 범위를 만족하는 수의 개수를 구하는 쿼리는 segment tree로 해결이 가능하다.

 

어차피 $A_i\le 10^5$으로 범위가 매우 작으므로 좌표 압축을 하지 않고,

$A_i$의 값을 index로 삼는 segment tree를 만들어 개수를 저장해주면 된다.

 

 

는... segment tree로 구현했다가 TLE를 받아버려서 좀 더 빠른 fenwick tree로 구현하여 통과하였다 (...) 

 

 

	// 13553: 수열과 쿼리 8
	// fail1: segtree TLE -> 나중에 fenwick 하고 속도 차이 시험해보자
	// fail2: fenwick 구현 실수
	#include<iostream>
	#include<algorithm>
	#include<cmath>
	using namespace std;
	typedef long long ll;
	int N, M, K, l, r, sz;
	int a[100001], tree[100001];
	ll ans[100001], total_cnt;
	struct Q
	{
	int l, r, idx;
	bool operator < (const Q &a) const
	{
	if (l/sz != a.l/sz) return l/sz < a.l/sz;
	return r < a.r;
	}
	}q[100001];
	void updateFwT(int idx, int is_push=1)
	{
	while (idx <= 100000)
	{
	tree[idx] += is_push;
	idx += (idx & -idx);
	}
	}
	int getCnt(int idx)
	{
	int cnt = 0;
	if (idx < 1) return 0;
	if (idx > 100000) idx = 100000;
	while (idx > 0)
	{
	cnt += tree[idx];
	idx -= (idx & -idx);
	}
	return cnt; // exclude A_i
	}
	int main()
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> N >> K;
	sz = sqrt(N);
	for (int i = 1; i <= N; ++i)
	cin >> a[i];
	cin >> M;
	for (int i = 0; i < M; ++i)
	{
	cin >> q[i].l >> q[i].r;
	q[i].idx = i;
	}
	sort(q, q+M);
	l = q[0].l;
	r = l - 1;
	for (int i = 0; i < M; ++i)
	{
	for (int j = l; j < q[i].l; ++j)
	{
	updateFwT(a[j], -1);
	total_cnt -= getCnt(a[j]+K) - getCnt(a[j]-K-1);
	}
	for (int j = l-1; j >= q[i].l; --j)
	{
	total_cnt += getCnt(a[j]+K) - getCnt(a[j]-K-1);
	updateFwT(a[j]);
	}
	for (int j = r+1; j <= q[i].r; ++j)
	{
	total_cnt += getCnt(a[j]+K) - getCnt(a[j]-K-1);
	updateFwT(a[j]);
	}
	for (int j = r; j > q[i].r; --j)
	{
	updateFwT(a[j], -1);
	total_cnt -= getCnt(a[j]+K) - getCnt(a[j]-K-1);
	}
	ans[q[i].idx] = total_cnt;
	l = q[i].l;
	r = q[i].r;
	}
	for (int i = 0; i < M; ++i)
	cout << ans[i] << "\n";
	return 0;
	}

view raw BOJ_13553.cpp hosted with ❤ by GitHub