「题解」「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\)。你的任务是帮助小明求出每对(坐标,时间)二元组居住的不方便指数。

数据范围

子任务分数\(n,q\)特殊性质
\(5\)\(\leq 400\)
\(7\)\(\leq 6\times 10^4\)\(\leq 400\)
\(10\)\(\leq 3\times 10^5\)对于所有的商店 \(a _ i=1,b _ i=10^8\)
\(23\)对于所有的商店 \(a _ i=1\)
\(35\)\(\leq 6\times 10^4\)
\(20\)\(\leq 3\times 10^5\)

时空限制

题目编号时间限制空间限制
Luogu P4632\(5\text{s}\)\(1000\text{MiB}\)
LibreOJ 2585\(5\text{s}\)\(1024\text{MiB}\)
APIO2018 T1\(5\text{s}\)\(1024\text{MiB}\)

题解

本题有多种解法。

解法 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;
}

相关题目