백준 15776 New Home (APIO 2018 A번)

문제 설명(링크)

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

15766번: New Home

 

문제 요약

1차원 직선에 여러 가게가 있고 종류는 1부터 $K$이다. 각 가게는 $[a_i, b_i]$시간동안 영업하는데, 쿼리 $Q$개가 들어온다. $y_i$시간에 $l_i$위치에 집을 지을 때, 각 종류의 가게의 접근성은 직선에 존재하는 해당 종류의 가게 중 가장 가까운 것과의 거리이다. 또한 각 집의 후보의 불편도는 각 종류의 가게에 대해 접근성의 최댓값이다. 각 가게 후보에 대해 불편도를 구하라

 

풀이

일단, 어떤 시점에 위치에 따른 각 종류의 접근성은 아래 그래프처럼 된다.

사진출처 : https://codeforces.com/blog/entry/59650

그러면, 이 종류별 그래프들의 최댓값 그래프(upper envelope)가 위치에 따른 불편도 그래프가 된다. 그러면, 가게가 생겨나고 없어지는 변경 쿼리와 $Q$개의 위치에 대한 답을 물어보는 쿼리를 시간 순으로 정렬해 수행하는 풀이를 생각할 수 있다. 그러면, 저 그래프를 시간에 따라 잘 업데이트하면서 관리하는 방향의 풀이를 생각할 수 있다.

 

이에는 한 가지의 아이디어가 필요한데, 최댓값 그래프에서 극댓값들을 전부 관리하는 아이디어이다. 이때, 종류별 그래프의 극댓값은 최댓값 그래프에서 사용되지 않을 수도 있다.

 

저 점들을 모두 안다면, 쿼리를 어떻게 처리할 수 있을까?

일단 $x=l_i$의 직선을 그리고 생각해보자. 직선 왼쪽에 있는 점들은 직선으로 기울기가 -1인 직선(파란색)을 긋고, 직선 오른쪽에 있는 점들은 기울기가 1인 직선(초록색)을 그리자. 그러면 그 직선들과 빨간 직선의 교점들중 가장 높이 있는것이 불편도가 된다. 이를 어떻게 알까? 우선, 한 점에서 이은 파란선과 빨간선의 교점은 x, y좌표의 합과 관련이 있고, 초록선은 차($|x-y|$가 아닌 $x-y$)와 관련이 있다. 따라서 우리는 각 점에 대해 좌표의 합과 차를 저장하고, $x$좌표가 $x_{l_i}$이상의 점들에 대해 좌표의 합의 최대, $x$좌표가 $x_{l_i}$이하의 점들에 대해 좌표의 차의 최대를 관리해주면 된다. 이는 한번의 시뮬레이션을 해 각 시점에 극대점들이 어떻게 추가되고 삭제되는지 전처리하고 쿼리를 해결할 때에는 특정 구간에 있는 유효한(각 시점에서 존재하는) 정점에 대해 좌표의 합과 차의 최대, 최소를 세그먼트 트리로 관리하는 방식으로 풀면 된다.

 

소스코드

#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long ll;
typedef pair<ll, ll> pll;
#define MAX 301010
#define MAXS 20
#define INF 1000000000
#define MOD (ll)1000000007
#define bb ' '
#define ln '\n'
template <typename T>
class Segment_Tree {
	//0-based index Segment Tree
	//O(N), O(lgN)
private:
	unsigned int N, s;
	vector<T> tree;
	vector<unsigned int> l, r;
	T query(unsigned int low, unsigned int high, unsigned int loc) {
		if (low == l[loc] && high == r[loc]) return tree[loc];
		if (high <= r[loc * 2]) return query(low, high, loc * 2);
		if (low >= l[loc * 2 + 1]) return query(low, high, loc * 2 + 1);
		return query(low, r[loc * 2], loc * 2) + query(l[loc * 2 + 1], high, loc * 2 + 1);
	}
	void _update(unsigned int loc, T val) {
		loc += s;
		tree[loc] = val;
		loc /= 2;
		while (loc) {
			tree[loc] = tree[loc * 2] + tree[loc * 2 + 1];
			loc /= 2;
		}
	}
	void init(unsigned int x = 1) {
		if (x >= s) {
			l[x] = r[x] = x - s;
			return;
		}
		init(x * 2);
		init(x * 2 + 1);
		l[x] = l[x * 2];
		r[x] = r[x * 2 + 1];
		tree[x] = tree[x * 2] + tree[x * 2 + 1];
	}
public:
	Segment_Tree<T>() {

	}
	Segment_Tree<T>(vector<T>& v) {
		N = v.size();
		s = 1 << (unsigned int)ceil(log2(N));
		tree.resize(2 * s + 1);
		l.resize(2 * s + 1);
		r.resize(2 * s + 1);
		unsigned int i;
		for (i = 0; i < N; i++) tree[i + s] = v[i];
		init();
	}
	T query(unsigned int low, unsigned int high) { return query(low, high, 1); }
	void update(unsigned int location, T new_value) { _update(location, new_value); }
};
struct dat {
	ll x, t, a, b;
	dat() {}
	dat(ll x, ll t, ll a, ll b) :x(x), t(t), a(a), b(b) {}
	bool operator<(dat d) {
		if (t != d.t) return t < d.t;
		if (x != d.x) return x < d.x;
		if (a != d.a) return a < d.a;
		return b < d.b;
	}
};
struct Query {
	ll l, y, num;
	Query() {}
	Query(ll l, ll y, ll num) :l(l), y(y), num(num) {}
	bool operator<(Query q) {
		return y < q.y;
	}
};
map<ll, vector<dat>> arr;
multiset<ll> st[MAX];
vector<Query> query;
ll ans[MAX];
vector<ll> point, tarr;
vector<pll> larr;
ll chk[MAX];
struct node {
	ll x, y;
	ll lv, rv;
	node() :x(0), y(0), lv(0), rv(-INF) {}
	node(ll x, ll y) :x(x), y(y) {
		lv = x + y;
		rv = y - x;
	}
	node(ll x, ll y, ll lv, ll rv) :x(x), y(y), lv(lv), rv(rv) {}
	node operator+(node x) { return node(0, 0, max(lv, x.lv), max(rv, x.rv)); }
};
bool operator<(pll p1, pll p2) {
	if (p1.first == p2.first) return p1.second < p2.second;
	return p1.first < p2.first;
}
ll getind(pll x) {
	return lower_bound(larr.begin(), larr.end(), x) - larr.begin();
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	ll N, K, Q;
	cin >> N >> K >> Q;
	ll i;
	ll x, t, a, b;
	vector<dat> datset;
	for (i = 1; i <= N; i++) {
		cin >> x >> t >> a >> b;
		arr[a].push_back(dat(x, t, a, b));
		arr[b + 1].push_back(dat(x, t, a, b));
		tarr.push_back(a);
		tarr.push_back(b + 1);
	}
	for (i = 0; i < Q; i++) {
		cin >> a >> b;
		query.push_back(Query(a, b, i));
	}
	sort(query.begin(), query.end());
	//simulation
	for (i = 1; i <= K; i++) st[i].insert(-INF);
	for (i = 1; i <= K; i++) st[i].insert(INF);
	map<ll, vector<dat>>::iterator it;
	for (it = arr.begin(); it != arr.end(); it++) {
		t = it->first;
		for (auto d : it->second) {
			ll pv = *prev(st[d.t].lower_bound(d.x));
			ll ne = *st[d.t].upper_bound(d.x);
			if (d.a == t) st[d.t].insert(d.x);
			else st[d.t].erase(st[d.t].find(d.x));
			larr.emplace_back(pv + ne, d.t);
			larr.emplace_back(pv + d.x, d.t);
			larr.emplace_back(d.x + ne, d.t);
		}
	}
	Segment_Tree<node> segtree;
	vector<node> v(larr.size());
	segtree = Segment_Tree<node>(v);
	it = arr.begin();
	ll cnt = 0;
	sort(larr.begin(), larr.end());
	larr.erase(unique(larr.begin(), larr.end()), larr.end());
	for (i = 0; i < Q; i++) {
		Query q = query[i];
		while (it != arr.end()) {
			ll t = it->first;
			if (t > q.y) break;
			for (auto d : it->second) {
				ll pv = *prev(st[d.t].lower_bound(d.x));
				ll ne = *st[d.t].upper_bound(d.x);
				if (d.a == t) {
					if (st[d.t].find(d.x) == st[d.t].end()) {
						segtree.update(getind({ pv + ne, d.t }), node(pv + ne, 0));
						segtree.update(getind({ pv + d.x, d.t }), node(pv + d.x, d.x - pv));
						segtree.update(getind({ d.x + ne, d.t }), node(d.x + ne, ne - d.x));
					}
					st[d.t].insert(d.x);
					if (!chk[d.t]) cnt++;
					chk[d.t]++;
				}
				else {
					st[d.t].erase(st[d.t].find(d.x));
					if (chk[d.t] == 1) cnt--;
					chk[d.t]--;
					if (st[d.t].find(d.x) != st[d.t].end()) continue;
					segtree.update(getind({ pv + ne, d.t }), node(pv + ne, ne - pv));
					segtree.update(getind({ pv + d.x, d.t }), node(pv + d.x, 0));
					segtree.update(getind({ d.x + ne, d.t }), node(d.x + ne, 0));
				}
			}
			it++;
		}
		if (cnt != K) {
			ans[q.num] = -1;
			continue;
		}
		node l = segtree.query(0, getind({ 2 * q.l, 10101010 }) - 1);
		node r = segtree.query(getind({ 2 * q.l, -1 }), larr.size() - 1);
		ans[q.num] = max(l.lv - 2 * q.l, r.rv + 2 * q.l) / 2;
	}
	for (i = 0; i < Q; i++) cout << ans[i] << ln;
	return 0;
}