【BZOJ 3387】线段树= =

57 跨栏训练
为了让奶牛参与运动，约翰建造了 K 个栅栏。每条栅栏可以看做是二维平面上的一条线段，它
们都平行于 X 轴。第 i 条栅栏所覆盖的 X 轴坐标的区间为 [ Ai,Bi ]， Y 轴高度就是 i。一开始，奶牛
在坐标 (S,K + 1) 处，它们的家在原点处，所以要想要回家就必须“跨”一些栅栏。
但奶牛们是跨不过栅栏的，它们只能绕过栅栏。在二维平面上，它们只能沿水平和垂直方向移动，
如果前进的道路上出现栅栏，它们就不能前进，必须沿水平方向移动到没有栅栏的地方再前进。奶牛
们希望走的路越短越好，由于在垂直方向上的路程是确定的，你只需要帮它们求出在水平方向的最短
路程就可以了。
输入格式
• 第一行：两个整数 K 和 S， 1 ≤ K ≤ 50000, − 105 ≤ S ≤ 105
• 第二行到第 N + 1 行：第 i + 1 行有两个整数 Ai 和 Bi， − 105 ≤ Ai ≤ Bi ≤ 105
输出格式
• 单个整数：表示奶牛从起点到终点在水平方向移动的最短总距离
样例输入
4 0
-2 1
-1 2
-3 0
-2 1
样例输出
4
解释
第四个栅栏是最先遇到的，向右移一格绕过
它。为了绕过第二个栅栏，再向右移一格，最后
为了回到原点向左移两格

【分析】

　　就是，差不多，像是个模拟的东西，如果没有东西挡着你，就不用走了（如果要走，等一下有东西挡着你再走）、

　　如果有东西挡着你，就走到栅栏左边或者栅栏右边（不用多走，要是需要多走，等一下再走）

　　但是询问区间的话每个点到栅栏左端点需要加的距离是不一样的，所以我们维护的时候不是他走的距离，而是他走的距离在加上他走到图的最左边的距离。

　　右边也一样。

　　就是一个区间修改成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

巴特西

【BZOJ 3387】线段树= =

最新文章

热门文章

巴特西

【BZOJ 3387】 线段树= =

最新文章

热门文章

【BZOJ 3387】线段树= =