「题解」「APIO2018」新家 New Home

APIO2018 T1，一道毒瘤题目。

题目链接：Luogu P4632/LibreOJ 2585/APIO2018 T1。

题目

题目描述

五福街是一条笔直的道路，这条道路可以看成一个数轴，街上每个建筑物的坐标都可以用一个整数来表示。小明是一位时光旅行者，他知道在这条街上，在过去现在和未来共有 \(n\) 个商店出现。第 \(i\) 个商店可以使用四个整数 \(x _ i,t _ i,a _ i,b _ i\) 描述，它们分别表示：商店的坐标、商店的类型、商店开业的年份、商店关闭的年份。

小明希望通过时光旅行，选择一个合适的时间，住在五福街上的某个地方。他给出了一份他可能选择的列表，上面包括了 \(q\) 个询问，每个询问用二元组（坐标，时间）表示。第 \(i\) 对二元组用两个整数 \(l _ i,y _ i\) 描述，分别表示选择的地点 \(l _ i\) 和年份 \(y _ i\)。

现在，他想计算出在这些时间和地点居住的生活质量。他定义居住的不方便指数为：在居住的年份，离居住点最远的商店类型到居住点的距离。类型 \(t\) 的商店到居住点的距离定义为：在指定的年份，类型 \(t\) 的所有营业的商店中，到居住点距离最近的一家到居住点的距离。我们说编号为 \(i\) 的商店在第 \(y\) 年在营业当且仅当 \(a _ i\leq y\leq b _ i\)。注意，在某些年份中，可能在五福街上并非所有 \(k\) 种类型的商店都有至少一家在营业。在这种情况下，不方便指数定义为 \(-1\)。你的任务是帮助小明求出每对（坐标，时间）二元组居住的不方便指数。

数据范围

时空限制

题解

本题有多种解法。

解法 A（模拟）

考虑以时间为顺序模拟整个过程，只是使用一些数据结构（线段树）来加速我们的模拟。

扫描线

首先我们先对时间轴进行类似于扫描线的处理，把一个商店拆成一个 \(a\) 时间插入操作和一个 \(b\) 时间删除操作。

所以现在问题变成了，动态维护一个颜色序列，支持在某个位置插入一个颜色和删除一个颜色，我们可以使用线段树快速解决修改问题。

二分答案

询问答案事实上是询问在某一个时间 \(t\)，一个人从某一位置出发同时向两边走，至少走多远才能经过所有的颜色各一次。

当然可以迅速的想到二分答案。

我们二分一个答案 \(\text{mid}\)，于是问题转化成了，我走 \(\text{mid}\) 步可不可以经过所有的颜色。

所以我们还需要快速解决：区间查询是否有所有的颜色。

区间数颜色

这是套路，我们对于每一个颜色记 \(\text{pre} _ i\) ​为这个颜色左侧第一个和它同色点的位置，那么我们会发现一个点是区间 \([l,r]\) 中本颜色的左侧第一个点当且仅当 \(\text{pre} _ i\)。那么我们如果要数区间里有多少颜色只需查询 \([l,r]\) 中的点有多少个点的 \(\text{pre}\) 值小于 \(l\) 即可。

所以我们用线段树套线段树解决这个问题，时间复杂度为 \(\Theta(n\log^3 _ 2n)\)。

解法 B（解法 A 的优化）

查找区间中是否存在所有的颜色是解法 A 中最复杂的一步。但我们可以发现，我们其实并不要求出具体的颜色数量，只需要知道区间内是否有所有的颜色。

仔细观察 \(\text{pre}\) 的含义——左边第一个和这个点同色点的位置，那么我们不难发现：区间 \((\text{pre} _ i,i)\) 内没有 \(i\) 这种颜色。

换句话说我们只需要查找 \([r+1,n]\) 的区间 \(\text{pre}\) 最小值，然后和 \(l\) 进行比较即可确认区间中是否有所有的颜色了。

我们可以使用线段树进行维护，并且用 set 存下所有颜色的最右点坐标，然后每次取 set 里的最小值和区间最小值比较取二者更小的即可。

这种做法的时间复杂度为 \(\Theta(n\log^2 _ 2n)\)。

解法 C（解法 B 的进化）

本质上我们二分答案要求的是最大的 \(i\)，满足 \([i,+\infty)\) 记的最小前驱为 \(\min\)，则 \(\min+i\leq 2\times x\)。

无解的情况先特判掉。

假如我们现在在线段树上的 \([l,r]\)：

• 如果 \(x\) 落在 \([\text{mid}+1,r]\) 上，那么 \(i\) 一定落在 \([\text{mid}+1,r]\) 上。
• 如果 \(x\) 落在 \([l,\text{mid}]\) 上，那么我们需要判断最终的答案会不会落在 \([\text{mid}+1,r]\) 上。由于 \(i\) 越小，\(\min\) 越小，所以我们只用检查一下是否满足 \(\min+i\leq 2\times x\) 即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
#define INF (1e8+5)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
	reg char ch=getchar();
	reg int res=0;
	while(ch<'0'||'9'<ch)ch=getchar();
	while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
	return res;
}

const int MAXN=300000+5;
const int MAXQ=300000+5;

int n,k,Q;
vector<int> V;

inline int GetID(int x){
	return lower_bound(V.begin(),V.end(),x)-V.begin()+1;
}

struct Heap{
	priority_queue<int,vector<int>,greater<int>/**/> a,b;
	inline void push(int x){
		a.push(x);
		return;
	}
	inline void del(int x){
		b.push(x);
		return;
	}
	inline int top(void){
		while(!b.empty()&&a.top()==b.top())
			a.pop(),b.pop();
		return a.top();
	}
};

namespace SegmentTree{
	const int T=(1<<19)+MAXN;
	Heap q[MAXN];
	struct Node{
		int Max,Min;
		#define Max(x) unit[(x)].Max
		#define Min(x) unit[(x)].Min
	};
	Node unit[T];
	int n,d;
	inline void Build(reg int size,reg int k){
		n=size;
		d=1;
		while(d<n)
			d<<=1;
		--d;
		for(reg int i=n+d+1;i>=1;--i)
			Min(i)=INF;
		for(reg int i=1;i<=n;++i)
			q[i].push(INF);
		for(reg int i=1;i<=k;++i)
			q[n].push(-INF);
		for(reg int i=n+d;i;i>>=1)
			Min(i)=-INF;
		for(reg int i=1;i<n;++i)
			Max(d+i)=V[i-1];
		Max(d+n)=2*INF;
		for(reg int i=d;i>=1;--i)
			Max(i)=max(Max(i<<1),Max(i<<1|1));
		return;
	}
	inline int Solve(reg int x){
		if(Min(n+d)==-INF)
			return -1;
		reg int i=1;
		int now=INF;
		while(i<=d)
			if(x>Max(i<<1))
				i=(i<<1|1);
			else if(Max(i<<1)+1+min(Min(i<<1|1),now)<=2*x)
				i=i<<1|1;
			else{
				now=min(Min(i<<1|1),now);
				i=i<<1;
			}
		return min(2*x-min(now,Min(i)),Max(i))-x;
	}
	inline void Update(reg int i){
		Min(i+d)=q[i].top();
		i+=d;
		while(i>>=1){
			if(Min(i)==min(Min(i<<1),Min(i<<1|1)))
				break;
			Min(i)=min(Min(i<<1),Min(i<<1|1));
		}
		return;
	}
	inline void Add(reg int i,reg int x){
		q[i].push(x);
		Update(i);
		return;
	}
	inline void Del(reg int i,reg int x){
		q[i].del(x);
		Update(i);
		return;
	}
	inline void Modify(reg int i,reg int x0,reg int x){
		q[i].del(x0),q[i].push(x);
		Update(i);
		return;
	}
}

multiset<int> S[MAXN];

inline void Add(multiset<int> &S,int x){
	multiset<int>::iterator it1=S.insert(x),it2=it1;
	--it1,++it2;
	SegmentTree::Add(GetID(x),*it1);
	SegmentTree::Modify(GetID(*it2),*it1,x);
	return;
}

inline void Del(multiset<int> &S,int x){
	multiset<int>::iterator it=S.find(x),it1=it,it2=it;
	--it1,++it2;
	SegmentTree::Del(GetID(x),*it1);
	SegmentTree::Modify(GetID(*it2),x,*it1);
	S.erase(it);
	return;
}

struct Node{
	int x,t,a;
	inline Node(reg int x=0,reg int t=0,reg int a=0):x(x),t(t),a(a){
		return;
	}
	inline bool operator<(const Node& x)const{
		return a<x.a;
	}
	inline void add(void){
		Add(S[t],x);
		return;
	}
	inline void del(void){
		Del(S[t],x);
		return;
	}
};

Node qa[MAXN],qb[MAXN],q[MAXQ];

int ans[MAXQ];

int main(void){
	n=read(),k=read(),Q=read();
	for(reg int i=1;i<=n;++i){
		static int x,t,a,b;
		x=read(),t=read(),a=read(),b=read();
		qa[i]=Node(x,t,a);
		qb[i]=Node(x,t,b);
		V.push_back(x);
	}
	sort(V.begin(),V.end());
	V.erase(unique(V.begin(),V.end()),V.end());
	reg int m=V.size();
	SegmentTree::Build(m+1,k);
	for(reg int i=1;i<=Q;++i){
		static int x,a;
		x=read(),a=read();
		q[i]=Node(x,i,a);
	}
	sort(qa+1,qa+n+1);
	sort(qb+1,qb+n+1);
	sort(q+1,q+Q+1);
	for(reg int i=1;i<=k;++i)
		S[i].insert(-INF),S[i].insert(INF);
	for(reg int i=1,lptr=1,rptr=1;i<=Q;++i){
		while(lptr<=n&&qa[lptr].a<=q[i].a)
			qa[lptr++].add();
		while(rptr<=n&&qb[rptr].a<q[i].a)
			qb[rptr++].del();
		ans[q[i].t]=SegmentTree::Solve(q[i].x);
	}
	for(reg int i=1;i<=Q;++i)
		printf("%d\n",ans[i]);
	return 0;
}

相关题目

• 「题解」「APIO2018」选圆圈 Circle selection；
• 「题解」「APIO2018」铁人两项 Duathlon；