Rockdu's Blog

地址：https://loj.ac/problem/2585

说一说我和这道题的故事吧。

APIO2018现场：和moonzero在一个考室，前一天才好不容易会使用linux系统后一天就要上考场了，非常的方。

打开problems，首先映入眼帘的便是 A.新家。

毫不犹豫先打了5分暴力，然后去打了T3，T2的暴力。

回头来准备肝T1，发现自己会Subtask2的7分暴力。

然后死也没调出来，400个set把自己送胸牌了。

下来moonzero告诉我他更窒息，写了400个splay………………

嗯，叙旧就叙到这里了，前几天又想起这道题，发现有了思路。

接下来我们来看看APIO这道亲民的码农题的做法吧。

首先我们容易发现题目要求的其实是t时刻以x为中心，能围住所有种类商店的最小半径。

发现显然是有可二分性的，如果我们可以快速判断t时刻时的任意一段[l,r]区间是否包含所有种类的商店那么我们就可以得到答案了。

我们考虑这样维护：对于每一个位置p维护数组pre[p]，表示建立在p的所有商店中，[每一个商店的[前一个种类相同的商店]]的坐标的最小值。比如下图所示的pre[p]就是箭头所指的坐标。

这样维护有什么好处呢？我们考虑下面两种情况：

对于A来说，它没有包括所有商店，因为它的右端点后面有蓝色的商店，蓝色商店的前一个商店跨过了A区间，因此我们断定A区间缺少蓝色商店，而B区间因为没有一种商店的前一个商店能跨过它，因此我们断定B区间不缺少商店。

我们发现对于一段区间[l,r]只要存在一个商店的坐标>r，并且它的前一个种类相同的商店的坐标<l那么这段区间就一定缺少一种类型的商店。那么我们对于整段坐标数轴维护pre[p]的最小值即可，只要x>r的商店中最靠前的没有落在l的左边那么[l,r]一定含有所有种类商店。这里用一棵线段树维护即可。

对于每一种商店，我们只关心它的前一个同种类型的商店，因此所有的商店连成了一个链状结构，我们要求插入删除，这里我们用set维护。每一次插入商店只会影响后继商店的pre值以及自己的pre值，删除同理，每一次set中插入和删除的时候都对线段树进行更新。但是我们发现，可以存在很多商店在同一位置，因此pre[p]的值应该是p位置所有商店种类相同的前一个商店坐标的最小值。这里我们每一个位置再维护一个multiset或者可删除堆就可以了。

这道题思路自然，但是代码及其难写，首先是两个离散化，其次是很多的细节。

1、对于同种类商店出现在同一个位置不需要做任何更改，因为开一家和开很多家效果是一样的，记录每种商店在每个位置出现的次数就行了。

2、在离散化后的数组上二分答案时，check后返回离散化之前的答案会让代码好写很多。

总复杂度O(n log^2 n)，5s嘛，梦想一下就过了。

实际上可以做到O(n log n)，我们发现二分check查询的都是一段后缀，于是可以在线段树上二分。爬树二分的复杂度降为O(n log n)。

#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
using namespace std;
const int maxn = 1e6 + 5;
const int inf = 0x3f3f3f3f;
int n, k, q, NR, TR;
int lsh_to_x[maxn], ans[maxn];
struct Shop {
	int x, type, l, r;
	int lsh_x, lsh_l, lsh_r;
} sp[maxn];
struct Query {
	int x, t, lsh_t, id;
} Q[maxn];
bool cmp(const Shop &A, const Shop &B) {
	return A.x < B.x;
}
vector<int > App[maxn], Disapp[maxn], NQ[maxn];
map<int, int > Tp[maxn];
map<int, int >::iterator it, tmp;
multiset<int > st[maxn];
map<int, int > lsh;

namespace SGT {
	const int L = 0, R = 1; 
	int mn[maxn << 2];
	void push_up(int rt) {
		mn[rt] = min(mn[rt << 1], mn[rt << 1 | 1]);
	}
	void build(int l, int r, int rt) {
		if(l == r) return mn[rt] = inf, void();
		int mid = l + r >> 1;
		build(l, mid, rt << 1);
		build(mid + 1, r, rt << 1 | 1);
		push_up(rt);
	}
	//x可不可以重复 
	void edit(int pos, int tl, int tr, int dt, int rt) {
		if(tl == tr) return mn[rt] = dt, void();
		int mid = tl + tr >> 1;
		if(pos <= mid) edit(pos, tl, mid, dt, rt << 1);
		else edit(pos, mid + 1, tr, dt, rt << 1 | 1);
		push_up(rt);
	}
	int query(int l, int r, int tl, int tr, int rt) {
		if(l == tl && r == tr) return mn[rt];
		int mid = tl + tr >> 1;
		if(r <= mid) return query(l, r, tl, mid, rt << 1);
		else if(l > mid) return query(l, r, mid + 1, tr, rt << 1 | 1);
		else return min(query(l, mid, tl, mid, rt << 1), query(mid + 1, r, mid + 1, tr, rt << 1 | 1));
	}
}

int lst;
map<int, int >::iterator ins(map<int, int > & M, int x) {
	return ++M[x], M.find(x);
}
void del(map<int, int > & M, int x) {
	--M[x]; if(!M[x]) M.erase(M.find(x));
}

void insert(int id) {
	using namespace SGT;
	it = ins(Tp[sp[id].type], sp[id].lsh_x);
	if(Tp[sp[id].type][sp[id].lsh_x] > 1)
		return ;
	--it; lst = it -> first, st[sp[id].lsh_x].insert(it -> first);
	//printf("%d insert %d\n", sp[id].lsh_x, it -> first);
	++it, ++it, st[it -> first].insert(sp[id].lsh_x);
	//printf("%d insert %d\n", it -> first, sp[id].lsh_x);
	st[it -> first].erase(st[it -> first].find(lst));
	//printf("%d erase %d\n", it -> first, lst);
	edit(sp[id].lsh_x, 0, NR + 1, *st[sp[id].lsh_x].begin(), 1);
	edit(it -> first, 0, NR + 1, *st[it -> first].begin(), 1);
}

void del(int id) {
	using namespace SGT;
	it = Tp[sp[id].type].lower_bound(sp[id].lsh_x);
	if(Tp[sp[id].type][sp[id].lsh_x] > 1) {
		return del(Tp[sp[id].type], sp[id].lsh_x), void();
	}
	//printf("sz : %d\n", st[sp[id].lsh_x].size());
	lst = (--it) -> first;
	st[sp[id].lsh_x].erase(st[sp[id].lsh_x].find(lst));
	//printf("%d erase %d\n", sp[id].lsh_x, lst);
	++it, ++it, st[it -> first].erase(st[it -> first].find(sp[id].lsh_x));
	//printf("%d erase %d\n", it -> first, sp[id].lsh_x);
	st[it -> first].insert(lst);
	//printf("%d insert %d\n", it -> first, lst);
	edit(sp[id].lsh_x, 0, NR + 1, *st[sp[id].lsh_x].begin(), 1);
	edit(it -> first, 0, NR + 1, *st[it -> first].begin(), 1);
	return del(Tp[sp[id].type], sp[id].lsh_x), void();
}

int GetLshX() {
	sort(sp + 1, sp + 1 + n, cmp);
	int p = 1;
	sp[1].lsh_x = p;
	lsh_to_x[p] = sp[1].x;
	for(register int i = 2; i <= n; ++i) {
		if(sp[i - 1].x != sp[i].x) ++p;
		sp[i].lsh_x = p;
		lsh_to_x[p] = sp[i].x;
	}
	lsh_to_x[p + 1] = inf;
	lsh_to_x[0] = -inf;
	return p;
}

int GetLshLR() {
	map<int, int >::iterator it;
	for(register int i = 1; i <= n; ++i)
		lsh[sp[i].l] = 1, lsh[sp[i].r] = 1;
	for(register int i = 1; i <= q; ++i)
		lsh[Q[i].t] = 1;
	int cnt = 0;
	for(it = lsh.begin(); it != lsh.end(); ++it)
		it -> second = ++cnt;
	for(register int i = 1; i <= n; ++i)
		sp[i].lsh_l = lsh[sp[i].l], sp[i].lsh_r = lsh[sp[i].r];
	for(register int i = 1; i <= q; ++i)
		Q[i].lsh_t = lsh[Q[i].t];
	return cnt;
}

int check(int x, int mid) {
	if(lsh_to_x[mid + 1] <= x) return -1;
	int mn = SGT::query(mid + 1, NR + 1, 0, NR + 1, 1);
	int Rdis = lsh_to_x[mid + 1] - 1, Ldis = lsh_to_x[mn];
	if(x * 2 - Rdis > Ldis) return -1;
	return max(lsh_to_x[mid] - x, x - Ldis);
}
int time;
//(L, R]
int Dv(int x, int L, int R) {
	int tmp, AR = inf;
	while(L < R - 1) {
		int mid = L + R >> 1;
		if(~(tmp = check(x, mid))) 
			R = mid, AR = tmp;
		else L = mid;
	}
	return AR;
}

int main() {
	scanf("%d%d%d", &n, &k, &q);
	for(register int i = 1; i <= n; ++i) {
		scanf("%d%d%d%d", &sp[i].x, &sp[i].type, &sp[i].l, &sp[i].r);
	}
	for(register int i = 1; i <= q; ++i) {
		scanf("%d%d", &Q[i].x, &Q[i].t);
		Q[i].id = i;
	}
	NR = GetLshX();
	TR = GetLshLR();
	for(register int i = 1; i <= k; ++i) {
		ins(Tp[i], 0), ins(Tp[i], NR + 1);
		st[NR + 1].insert(0);
		//printf("%d insert 0\n", NR + 1);
	}
	SGT::build(0, NR + 1, 1);
	SGT::edit(NR + 1, 0, NR + 1, 0, 1);
	for(register int i = 1; i <= NR + 1; ++i)
		st[i].insert(inf);
	for(register int i = 1; i <= n; ++i) {
		App[sp[i].lsh_l].push_back(i);
		Disapp[sp[i].lsh_r + 1].push_back(i);
	}
	for(register int i = 1; i <= q; ++i) {
		NQ[Q[i].lsh_t].push_back(i);
	}
	for(register int i = 1; i <= TR; ++i) {
		time = i;
		for(register int j = App[i].size() - 1; j >= 0; --j) {
			//printf("Insert : %d\n", App[i][j]); 
			insert(App[i][j]);
		}
		for(register int j = Disapp[i].size() - 1; j >= 0; --j) {
			//printf("Del : %d\n", Disapp[i][j]); 
			del(Disapp[i][j]);
		}
		for(register int j = NQ[i].size() - 1; j >= 0; --j) {
			//printf("Q : %d\n", NQ[i][j]);
			ans[Q[NQ[i][j]].id] = Dv(Q[NQ[i][j]].x, 0, NR + 1);
		}
	}
	for(register int i = 1; i <= q; ++i) {
		printf("%d\n", ans[i] != inf ? ans[i] : -1);
	}
	return 0;
}