JOISC19 Examination

문제

https://oj.uz/problem/view/JOI19_examination

문제 보기 - Examination (JOI19_examination) :: oj.uz

N개의 $(x, y)$점이 들어오고, Q개의 $(a, b, c)$쿼리가 들어온다. 쿼리의 의미는 $x>=a, y>=b, x+y>=c$를 만족하는 점들의 수를 세는 것이다.

$N<=100000$

$Q<=100000$

$x, y, a, b, c<=1000000000$

 

풀이

$c=0$이라면 단순히 직사각형 속의 점들의 수를 세는 문제이니, 2D Segment Tree를 이용하거나, 분할정복을 이용하여 $O(Nlog^2N)$ 안에 해결할 수 있다.

 

$c$에 대한 조건을 해결하기 위한 방법은 시간축을 도입하는 것으로, $x+y$와 $c$로 전체 점과 쿼리를 정렬하여 각 쿼리마다 $x+y>=c$를 만족하는 점들만 업데이트한 후 똑같은 직사각형 처리를 하는 것이다.

결론적으로 점 추가 업데이트가 있고, 직사각형 속의 점들의 수를 세는 문제이니, 가장 효율적인 방법은 분할정복을 이용하여 펜윅 트리로 스위핑을 하여 $O(Nlog^2N)$에 해결하는 것이다.

 

시간 복잡도 : $O((N+Q)log^2(N+Q))$

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int MAXN = 1e5;
 
struct Data
{
	int x, y, p, s;
};
 
int N, Q;
vector<Data> V;
vector<int> comp;
int ans[MAXN+10];
 
int getcomp(int x) { return lower_bound(comp.begin(), comp.end(), x)-comp.begin()+1; }
 
int tree[MAXN+10];
void update(int i, int k) { for(i=N-i+1; i<=N; i+=(i&-i)) tree[i]+=k; }
int query(int i) { int ret=0; for(i=N-i+1; i>0; i-=(i&-i)) ret+=tree[i]; return ret; }
void flush(int i) { for(i=N-i+1; i<=N; i+=(i&-i)) tree[i]=0; }
 
void solve(int l, int r)
{
	if(l==r) return;
	int mid=l+r>>1;
	solve(l, mid);
	solve(mid+1, r);
	vector<Data> L, R;
	for(int i=l; i<=mid; i++) if(V[i].p==0) L.push_back(V[i]);
	for(int i=mid+1; i<=r; i++) if(V[i].p) R.push_back(V[i]);
 
	sort(L.begin(), L.end(), [&](const Data &p, const Data &q) { return p.x>q.x; });
	sort(R.begin(), R.end(), [&](const Data &p, const Data &q) { return p.x>q.x; });
 
	for(int i=0, j=0; i<R.size(); i++)
	{
		for(; j<L.size() && L[j].x>=R[i].x; j++)
		{
			update(getcomp(L[j].y), 1);
		}
		ans[R[i].p]+=query(getcomp(R[i].y));
	}
	for(int j=0; j<L.size(); j++) flush(getcomp(L[j].y));
}
 
int main()
{
	scanf("%d%d", &N, &Q);
	for(int i=1; i<=N; i++)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		V.push_back({x, y, 0, x+y});
		comp.push_back(y);
	}
	for(int i=1; i<=Q; i++)
	{
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		V.push_back({x, y, i, z});
	}
 
	sort(comp.begin(), comp.end());
	comp.erase(unique(comp.begin(), comp.end()), comp.end());
 
	sort(V.begin(), V.end(), [&](const Data &p, const Data &q)
	{
		if(p.s!=q.s) return p.s>q.s;
		return p.p<q.p;
	});
 
	solve(0, V.size()-1);
	for(int i=1; i<=Q; i++) printf("%d\n", ans[i]);
}