P4632 [APIO2018] 新家
LimpidSlirm
·
·
题解
题意
给定数轴上的 n 个点，每个点用一个二元组 (pos_i,type_i) 描述，pos_i 表示其位置，type_i 表示其种类，且会在时间段 [a_i,b_i] 出现。总共有 k 种 type。
## Solution
看起来像是一个乱七八糟的偏序问题。显然地，只需要离线就可以解决时间维度上的问题。
然后有一个二分答案，即二分一个 $mid$，然后去查询 $[pos_i-mid,pos_i+mid]$ 区间内是否包含所有 $k$ 种点。
问题似乎转化成了二位数点，即以坐标为 $x$ 轴，以类型为 $y$ 轴，只需要维护当前矩形内是否存在所有 $k$ 种 $y$ 值就可以计算出答案。
但是由于颜色不连续的性质，无法用数据结构快速维护（好像可以再离线一次？《二 次 离 线》）。于是人类智慧做法他来了！令某一个点 $i$ 前一个和它种类相同的点为 $pre_i$，当前二分到的区间为 $[l,r]$，在 $n+1$ 号点上放置所有 $k$ 种 $type$ 的点。那么只需要计算 $[r+1,n+1]$ 区间内的任意一种 $type$ 的 $pre$ 的最小值。即在保证所有 $type$ 都被检测到的前提下 ，如果 $[r+1,n+1]$ 区间内任意一个点的前驱的最小值大于等于 $l$，那么显然地 $[l,r]$ 区间内存在所有 $k$ 种点。最小值大于等于 $l$ 意味着所有点的前驱都在 $l$ 之后，若 $pre\in[l,r]$ 则说明当前种类在区间内出现过，若 $r\lt pre$ 则说明 $pre$ 的某一个祖宗前驱在区间 $[l,r]$ 内。而在 $n+1$ 号点放置所有 $k$ 种点的操作保证了所有种类的点都在 $r$ 之后出现过。
使用线段树维护区间最小值，对于每一种 $type$ 维护一个 `multiset` 记录当前 $type$ 所有出现的位置，删除点的时候只需要如链表般将当前节点的 $pre$ 变为 $nxt$ 节点的 $pre$ 即可，加点同理。
由于每个点都会被被 `insert` 进入 `multiset` $3$ 次，故对于 `multiset`，时间复杂度为 $\mathcal{O}(n)$。单次修改时间复杂度为 $\mathcal{O}(\log n)$，再乘上二分答案的一个 log，总时间复杂度为 $\mathcal{O}(n\log^2 n)$。
注意二分答案时区间左右端点应转为离散化后的编号，`multiset` 中删去元素时 `erase()` 参数为迭代器，记得加 $0$ 号点和 $n+1$ 号点作为各种类型的第一个前驱和后继。
## code
```cpp
#include<bits/stdc++.h>
inline int read()
{
int res=0,flag=1;
char ch=getchar();
while(!('0'<=ch&&ch<='9')) (ch=='-')?flag=-1:1,ch=getchar();
while(('0'<=ch&&ch<='9')) res=res*10+ch-'0',ch=getchar();
return res*flag;
}
struct infomation
{
int id;
int pos;
int type;
int time;
bool operator <(const struct infomation &other)const
{
if(this->time!=other.time)
return this->time<other.time;
return this->type>other.type;
}
};
struct SegmentTree
{
struct node
{
std::multiset<int> s;
int min;
};
struct node nd[1200010];
#define inf 0x3f3f3f3f
void build(int left,int right,int id)
{
nd[id].min=inf;
if(left==right)
return ;
int mid=(left+right)>>1;
build(left,mid,id<<1);
build(mid+1,right,id<<1|1);
return ;
}
void pushup(int id)
{
nd[id].min=std::min(nd[id<<1].min,nd[id<<1|1].min);
return ;
}
void modify(int left,int right,int id,int pos,int data)
{
if(right<pos||pos<left)
return ;
if(left==pos&&right==pos)
{
nd[id].s.insert(data);
nd[id].min=*nd[id].s.begin();
return ;
}
int mid=(left+right)>>1;
modify(left,mid,id<<1,pos,data);
modify(mid+1,right,id<<1|1,pos,data);
pushup(id);
return ;
}
void del(int left,int right,int id,int pos,int data)
{
if(right<pos||pos<left)
return ;
if(left==pos&&right==pos)
{
nd[id].s.erase(nd[id].s.find(data));
nd[id].min=(nd[id].s.size()==0)?inf:(*nd[id].s.begin());
return ;
}
int mid=(left+right)>>1;
del(left,mid,id<<1,pos,data);
del(mid+1,right,id<<1|1,pos,data);
pushup(id);
return ;
}
int query(int left,int right,int id,int start,int end)
{
if(right<start||end<left)
return inf;
if(start<=left&&right<=end)
return nd[id].min;
int mid=(left+right)>>1;
int ansl=query(left,mid,id<<1,start,end);
int ansr=query(mid+1,right,id<<1|1,start,end);
return std::min(ansl,ansr);
}
};
struct infomation info[900010];
struct SegmentTree st;
int n,k,q,m,cnt;
int res[300010];
std::map<int,int> postion;
std::multiset<int> shop[300010];
void init()
{
n=read(),k=read(),q=read();
std::priority_queue<int,std::vector<int>,std::greater<int> > heap;
for(int i=1;i<=n;i++)
{
int pos=read(),type=read(),fr=read(),to=read();
info[(i<<1)-1]=(infomation){0,pos,type,fr};
info[i<<1]=(infomation){0,pos,-type,to};
heap.push(pos);
m=std::max(m,pos);
}
for(int i=1;i<=q;i++)
{
int pos=read(),time=read();
info[2*n+i]=(infomation){i,pos,0,time};
m=std::max(m,pos);
}
postion.clear();
postion[-1e8]=++cnt;
while(heap.empty()==false)
{
if(postion[heap.top()]==0)
postion[heap.top()]=++cnt;
heap.pop();
}
std::sort(info+1,info+2*n+q+1);
postion[2e8]=++cnt;
st.build(1,cnt,1);
for(int i=1;i<=k;i++)
shop[i].insert(1),shop[i].insert(cnt);
st.modify(1,cnt,1,cnt,1e8);
for(int i=1;i<=k;i++)
st.modify(1,cnt,1,cnt,1);
return ;
}
void modify(int pos,int type)
{
int pre=*--shop[type].lower_bound(pos);
st.modify(1,cnt,1,pos,pre);
int nxt=*shop[type].lower_bound(pos);
st.del(1,cnt,1,nxt,pre);
st.modify(1,cnt,1,nxt,pos);
shop[type].insert(pos);
return ;
}
void del(int pos,int type)
{
int pre=*--shop[type].lower_bound(pos);
st.del(1,cnt,1,pos,pre);
shop[type].erase(shop[type].find(pos));
int nxt=*shop[type].lower_bound(pos);
st.del(1,cnt,1,nxt,pos);
st.modify(1,cnt,1,nxt,pre);
return ;
}
void solve()
{
int now=1;
for(int i=1;i<=2*n+q;i++)
{
if(info[i].type>0)
modify(postion[info[i].pos],info[i].type);
if(info[i].type==0)
{
int left=0,right=m,ans=1e8+1;
while(left<=right)
{
int mid=(left+right+1)>>1;
int l=(*postion.lower_bound(info[i].pos-mid)).second;
int r=(*--postion.upper_bound(info[i].pos+mid)).second;
if(st.query(1,cnt,1,r+1,cnt)>=l)
ans=mid,right=mid-1;
else
left=mid+1;
}
res[info[i].id]=(ans==1e8+1)?-1:ans;
}
if(info[i].type<0)
del(postion[info[i].pos],-info[i].type);
}
for(int i=1;i<=q;i++)
printf("%d\n",res[i]);
return ;
}
int main(int argc,const char *argv[])
{
init();
solve();
return 0;
}
```
## 写在最后
讲道理 $\mathcal{O}(n\log^2 n)$ 吸完氧跑的还是挺快的。