[牛客网] 推箱子【离散,线段树区间覆盖】

Online Judge牛客网NOIP2018赛前集训营-提高组(第八场)T2

Label:离散,线段树区间覆盖

ps:这套题目由于被改成模拟离线赛,所以下面的题目描述改编了,题目还是一样的。


题目描述

终于,今天Sheldon要坐飞机前往瑞典领诺贝尔奖了。作为Sheldon的好朋友,Leonard、Penny、Howard、Bernadette、Rajesh也会去。不过由于行李太多太重,众人只好将行李堆在电梯里后,再走楼梯到一楼静静地等电梯。

[牛客网] 推箱子【离散,线段树区间覆盖】

不幸的是,行李堆得太高了,电梯门一开行李就散落一地。很巧的是,如果把地板作为平面,行李近似的看成矩形,定义每块瓷砖的垂直边分别作为坐标轴,x轴的正方向向右,那么每个行李箱的每条边都平行与坐标轴,且没有重叠。

Sheldon见到此番情景,向便Leonard提出了一个问题,如果由Sheldon挑选一个行李箱,由Leonard推着这个箱子向右以每秒1个单位的速度移动。如果路上正面碰上某个行李箱,被碰上的行李箱会在碰到的那个瞬间开始进入运动状态,以1个单位的速度向右移动,不会转动或改变运动方向。考虑到Leonard是个重度哮喘症患者,所以他只能坚持k秒就要停下来。而Sheldon想知道Leonard停下来时所有行李箱的位置。

准确地说,在某个时刻一个箱子i处于移动状态当且仅当:i是选择的箱子;或者存在一个处于移动状态的箱子j,它的右边界等于箱子i的左边界,且它们在y轴上的投影的公共长度>0。你可以发现在这种情况下,任意时刻每个矩形仍然不相交。

Leonard认为这个问题太过于stupid,但又不好意思拒绝(毕竟是十年的室友),于是让老X来回答这个问题。如果老X成功地回答了Sheldon的问题,Leonard就会让Sheldon就会带上老X一起去瑞典。

输入

第一行两个整数n,t和k。Sheldon开始选择的是输入的第t个行李。接下来n行每行四个整数表示行李的左下角坐标是\((x1_i,y1_i)\),右上角坐标是\((x2_i,y2_i)\)。

输出

输出一行n个整数,第i个整数表示k秒后第i个行李箱的左下角的x坐标。

你可以发现只要知道这个值就能唯一确定行李箱的位置。

样例

Input

5 1 1
1 1 2 3
2 2 3 5
3 4 4 5
4 2 5 5
5 1 6 3

Output

2 3 4 5 6

Hint

对于30%的数据,\(k≤100\)。

对于另外40%的数据,\(n≤1000\)。

对于100%的数据,\(n≤10^5,1≤t≤n,1≤k≤10^9\),所有坐标都在\(−10^9\)和\(10^9\)之间。

数据保证任意两个行李不相交。

题解

首先当然是根据\(x1\)将所有箱子排序。我们只要知道每个箱子第一次被推动的时间\(ti\)即可算出最后每个箱子的位置。

为避免擦着过的情况,我们一开始先将\(y2--\)。这样只要满足两个点纵坐标构成的两区间存在交集则表示会相撞。假设\(i\)会被它前面的撞到,且\(i\)能够撞到\(j\),则\(ti[j]=min(ti[j],ti[i]+x1[j]-x2[i])\)。

对于70%数据,直接暴力\(O(N)\)扫一遍前面的行李即可,取最小值,总的时间复杂度为\(O(N^2)\)。

考虑怎么快速取到最小值,很显然可以用线段树去优化。先将纵坐标离散了,然后对线段树的一段区间赋上某个值,这个区间就是离散后的纵坐标。查询时也是根据当前点的纵坐标区间查询最小值。存什么值呢,观察上面那个式子得,只要存\(ti[i]-x2[i]\)即可。线段树支持个区间覆盖,区间查询最小值即可。

这道题就结束了,不过实现上有很多细节要注意:

1.最后一定要判\(ti[]<=k\),保证是在规定时间内被撞到。

2.由于是线段树区间赋值,一开始的懒标记lazy,最小值w一定都要赋值成一个极大值INF。

3.离散数组要开\(2N\),因为对于每个箱子都离散了\(y1,y2\)共\(2N\)个数。相应的,线段树数组大小要开\(8N\)。

4.一开始的\(y2--\),保证不会出现擦过的情况。

5.一个考试时很silly的疑惑:怎么保证按x1排序后,只要纵坐标有交集两个箱子会相撞,如果前面箱子的x2>后面箱子的x1那不就不相撞了吗,其实画个图就知道这两者不可能同时满足qwq。

代码如下:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,INF=1e9+2;
inline int read(){
    int x=0,e=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')e=-1;c=getchar();}
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*e;
}
struct node{
    int x,y,x2,y2,id;
}o[N];
inline bool cmp(node a,node b){return a.x<b.x;}
int n,s,k,LIM;

struct sgt{
    int l,r,w,lazy;
}b[8*N];
void build(int o,int l,int r){
    b[o].l=l,b[o].r=r,b[o].w=INF,b[o].lazy=INF;
    if(l==r)return;
    int mid=l+r>>1;
    build(o<<1,l,mid);build(o<<1|1,mid+1,r);
}
void down(int o){
    if(b[o].lazy==INF)return ;
    int p=b[o].lazy;
    b[o<<1].w=min(b[o<<1].w,p);b[o<<1|1].w=min(b[o<<1|1].w,p);
    b[o<<1].lazy=min(b[o<<1].lazy,p);b[o<<1|1].lazy=min(b[o<<1|1].lazy,p);
    b[o].lazy=INF;
}
void update(int o,int l,int r,int d){
    if(b[o].l==l&&b[o].r==r){
        b[o].w=min(b[o].w,d);
        b[o].lazy=min(b[o].lazy,d);
        return;
    }
    down(o);
    int mid=b[o].l+b[o].r>>1;
    if(r<=mid)update(o<<1,l,r,d);
    else if(l>mid)update(o<<1|1,l,r,d);
    else{
        update(o<<1,l,mid,d);update(o<<1|1,mid+1,r,d);
    }
    b[o].w=min(b[o<<1].w,b[o<<1|1].w);
}
int query(int o,int l,int r){
    if(b[o].l==l&&b[o].r==r)return b[o].w;
    down(o);
    int mid=b[o].l+b[o].r>>1;
    if(r<=mid)return query(o<<1,l,r);
    else if(l>mid)return query(o<<1|1,l,r);
    return min(query(o<<1,l,mid),query(o<<1|1,mid+1,r));
}
int ti[N],res[N];
int yy[2*N];
int main(){
    n=read(),s=read(),k=read();
    int tmp=0;
    for(register int i=1;i<=n;i++){
        int a=read(),b=read(),c=read(),d=read();
        d--;    
        o[i]=(node){a,b,c,d,i};
        yy[++tmp]=b,yy[++tmp]=d;
    }
    sort(o+1,o+n+1,cmp);
    sort(yy+1,yy+tmp+1);
    LIM=unique(yy+1,yy+tmp+1)-yy-1;
    
    for(register int i=1;i<=n;i++){
        o[i].y=lower_bound(yy+1,yy+LIM+1,o[i].y)-yy;
        o[i].y2=lower_bound(yy+1,yy+LIM+1,o[i].y2)-yy;
    }
    build(1,1,LIM);
    int st;
    for(register int i=1;i<=n;i++)if(o[i].id==s){st=i;break;}
    ti[st]=1;
    update(1,o[st].y,o[st].y2,1-o[st].x2);
    for(register int i=st+1;i<=n;i++){
        int now=query(1,o[i].y,o[i].y2);    
        if(now==INF)continue;
        ti[i]=o[i].x+now;
        update(1,o[i].y,o[i].y2,ti[i]-o[i].x2);
    }
    for(register int i=1;i<=n;i++){
        if(ti[i]&&ti[i]<=k)res[o[i].id]=k-ti[i]+1+o[i].x;
        else res[o[i].id]=o[i].x;
    }
    for(register int i=1;i<n;i++)printf("%d ",res[i]);
    printf("%d\n",res[n]);
} 
上一篇:TI的电压转换芯片TXS0108E在MDIO总线上的运用


下一篇:P1433 吃奶酪 深度搜索 剪枝 卡时