【分析】
就是，差不多，像是个模拟的东西，如果没有东西挡着你，就不用走了（如果要走，等一下有东西挡着你再走）、
如果有东西挡着你，就走到栅栏左边或者栅栏右边（不用多走，要是需要多走，等一下再走）
但是询问区间的话每个点到栅栏左端点需要加的距离是不一样的，所以我们维护的时候不是他走的距离，而是他走的距离在加上他走到图的最左边的距离。
右边也一样。
就是一个区间修改成INF的操作 以及单点修改 还有区间查询。
代码如下：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define Maxn 200010
#define Maxk 50010
#define INF 0xfffffff int a[Maxk],b[Maxk]; struct node
{
int l,r,lc,rc,a1,a2;
bool lazy;
}t[Maxn*];int len; int mymin(int x,int y) {return x<y?x:y;}
int mymax(int x,int y) {return x>y?x:y;}
int mn=INF,mx=; int build(int l,int r)
{
int x=++len;
t[x].l=l;t[x].r=r;t[x].a1=t[x].a2=INF;
t[x].lazy=;
if(l!=r)
{
int mid=(l+r)>>;
t[x].lc=build(l,mid);
t[x].rc=build(mid+,r);
}
return x;
} void upd(int x)
{
if(t[x].lazy==) return;
if(t[x].l!=t[x].r)
{
int lc=t[x].lc,rc=t[x].rc;
t[lc].lazy=;t[rc].lazy=;
}
t[x].a1=t[x].a2=INF;
t[x].lazy=;
} void change(int x,int l,int r)
{
if(l>r) return;
upd(x);
if(t[x].l==l&&t[x].r==r)
{
t[x].lazy=;
return;
}
int mid=(t[x].l+t[x].r)>>;
if(r<=mid) change(t[x].lc,l,r);
else if(l>mid) change(t[x].rc,l,r);
else
{
change(t[x].lc,l,mid);
change(t[x].rc,mid+,r);
}
int lc=t[x].lc,rc=t[x].rc;
upd(lc);upd(rc);
t[x].a1=mymin(t[lc].a1,t[rc].a1);
t[x].a2=mymin(t[lc].a2,t[rc].a2);
} void change2(int x,int y,int z)
{
upd(x);
if(t[x].l==t[x].r)
{
t[x].a1=mymin(t[x].a1,z+y);
t[x].a2=mymin(t[x].a2,z+mx-y);
return;
}
int mid=(t[x].l+t[x].r)>>;
if(y<=mid) change2(t[x].lc,y,z);
else change2(t[x].rc,y,z);
int lc=t[x].lc,rc=t[x].rc;
upd(lc);upd(rc);
t[x].a1=mymin(t[lc].a1,t[rc].a1);
t[x].a2=mymin(t[lc].a2,t[rc].a2);
} int query(int x,int l,int r,bool p)
{
if(l>r) return INF;
upd(x);
if(t[x].l==l&&t[x].r==r)
{
if(!p) return t[x].a1;
else return t[x].a2;
}
int mid=(t[x].l+t[x].r)>>;
if(r<=mid) return query(t[x].lc,l,r,p);
else if(l>mid) return query(t[x].rc,l,r,p);
else return mymin(query(t[x].lc,l,mid,p),query(t[x].rc,mid+,r,p));
} int main()
{
int k,s;
scanf("%d%d",&k,&s);
for(int i=;i<=k;i++)
{
scanf("%d%d",&a[i],&b[i]);
mn=mymin(mn,a[i]);
mx=mymax(mx,b[i]);
}
mn=-mn+;
for(int i=;i<=k;i++) a[i]+=mn,b[i]+=mn;
mx+=mn;
len=;
build(,mx);
change2(,+mn,);
for(int i=;i<=k;i++)
{
int n1=query(,a[i]+,b[i]-,),n2=query(,a[i]+,b[i]-,);
if(n1!=INF) change2(,a[i],n1-a[i]);
if(n2!=INF) change2(,b[i],n2-(mx-b[i]) );
change(,a[i]+,b[i]-); }
s+=mn;
int ans=mymin(query(,,s,)-(mx-s),query(,s,mx,)-s);
printf("%d\n",ans);
return ;
}
[BZOJ 3387]
2016-10-31 15:17:12