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; }
近期评论