Description：

给出所有商户的坐标，类型，开业时间，关闭时间，求对于某个时间某个位置求出距离它最远的某类商铺的距离。

$1\leqslant n\leqslant 3\times 10^5$

Solution：

首先把所有操作分成添加商铺和删除商铺，然后和询问一起按时间排序，然后我们得到了在当前这个事件所有商铺的类型和位置，然后我们每个商户维护一个 $pre$ 表示上一个同种商户的位置，然后二分区间大小，如果在这个区间之后有一个点的 $pre$ 在这个区间之前，就不合法，插入删除就修改一下后继的 $pre$ 什么的。

注意每个叶子要维护一个可删堆因为同一个坐标可以有好多询问。

当然也可以写平衡树。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<set>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n,k,q;

#define MAXN 300010

#define MAXP 600010

int v[MAXP];

multiset<int> s[MAXN];

#define iter set<int>::iterator

multiset<int> val[MAXP];

struct node

{

	int lc,rc;

	int mind;

}t[MAXP << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	rt = newnode();

	t[rt].mind = 0x3f3f3f3f;

	if(l == r)return;

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	return;

}

void update(int rt,int p,int v,int tp,int l,int r)

{

	if(l == r)

	{

		if(tp == -1)val[l].erase(val[l].find(v));

		else val[l].insert(v);

		t[rt].mind = (val[l].empty() ? 0x3f3f3f3f : *val[l].begin());

		return;

	}

	if(p <= mid)update(t[rt].lc,p,v,tp,l,mid);

	else update(t[rt].rc,p,v,tp,mid + 1,r);

	t[rt].mind = min(t[t[rt].lc].mind,t[t[rt].rc].mind);

	return;

}

int query(int rt,int L,int R,int l,int r)

{

	if(L <= l && r <= R)return t[rt].mind;

	int res = 0x3f3f3f3f;

	if(L <= mid)res = min(res,query(t[rt].lc,L,R,l,mid));

	if(R > mid)res = min(res,query(t[rt].rc,L,R,mid + 1,r));

	return res;

}

struct opt

{

	int type,tim,pos,val;

}o[MAXN * 3];

int tot = 0;

bool cmp_opt(opt a,opt b)

{

	if(a.tim != b.tim)return a.tim < b.tim;

	else return abs(a.type) > abs(b.type);

}

int ans[MAXN];

int main()

{

	scanf("%d%d%d",&n,&k,&q);

	int x,y,a,b;

	for(int i = 1;i <= n;++i)

	{

		x = rd();y = rd();a = rd();b = rd();

		o[++tot] = (opt){1,a,x,y};

		o[++tot] = (opt){-1,b + 1,x,y};

		v[++v[0]] = x;

	}

	for(int i = 1;i <= q;++i)

	{

		x = rd();y = rd();

		o[++tot] = (opt){0,y,x,i};

	}

	sort(v + 1,v + 1 + v[0]);v[++v[0]] = 0x3f3f3f3f;

	v[0] = unique(v + 1,v + 1 + v[0]) - v - 1;

	build(root,1,v[0]);

	sort(o + 1,o + 1 + tot,cmp_opt);

	for(int i = 1;i <= k;++i)

	{

		update(root,v[0],0,1,1,v[0]);

		s[i].insert(v[0]);

	}

	for(int i = 1;i <= tot;++i)

	{

		if(o[i].type == 1)

		{

			int p = lower_bound(v + 1,v + 1 + v[0],o[i].pos) - v;

			s[o[i].val].insert(p);

			int pre = 0;

			iter it = s[o[i].val].find(p);

			if(it == s[o[i].val].begin())pre = 0;

			else pre = *(--it);

			it = s[o[i].val].find(p);++it;

			if(it != s[o[i].val].end())

			{

				update(root,*it,pre,-1,1,v[0]);

				update(root,*it,p,1,1,v[0]);

			}

			update(root,p,pre,1,1,v[0]);

		}

		if(o[i].type == -1)

		{

			int p = lower_bound(v + 1,v + 1 + v[0],o[i].pos) - v;

			int pre = 0;

			iter it = s[o[i].val].find(p);

			if(it == s[o[i].val].begin())pre = 0;

			else pre = *(--it);

			it = s[o[i].val].find(p);++it;

			if(it != s[o[i].val].end())

			{

				update(root,*it,pre,1,1,v[0]);

				update(root,*it,p,-1,1,v[0]);

			}

			s[o[i].val].erase(s[o[i].val].find(p));

			update(root,p,pre,-1,1,v[0]);

		}

		if(o[i].type == 0)

		{

			int l = 0,r = 100000001,mi;

			while(l < r)

			{

				mi = ((l + r) >> 1);

				int rig = lower_bound(v + 1,v + 1 + v[0],o[i].pos + mi + 1) - v;

				int minpre = query(root,rig,v[0],1,v[0]);

				minpre = (minpre == 0 ? -0x3f3f3f3f : v[minpre]);

				if(minpre < o[i].pos - mi)l = mi + 1;

				else r = mi;

			}

			if(l == 100000001)l = -1;

			ans[o[i].val] = l;

		}

	}

	for(int i = 1;i <= q;++i)printf("%d\n",ans[i]);

	return 0;

}