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