poj2374 Fence Obstacle Course

​​http://www.elijahqi.win/archives/868​​​

Description

Farmer John has constructed an obstacle course for the cows’ enjoyment. The course consists of a sequence of N fences (1 <= N <= 50,000) of varying lengths, each parallel to the x axis. Fence i’s y coordinate is i.

The door to FJ’s barn is at the origin (marked ‘*’ below). The starting point of the course lies at coordinate (S,N).

+-S-+-+-+ (fence #N)

+-+-+-+ (fence #N-1)

… …

+-+-+-+ (fence #2)

+-+-+-+ (fence #1)

=|=|=|=*=|=|=| (barn)

-3-2-1 0 1 2 3

FJ’s original intention was for the cows to jump over the fences, but cows are much more comfortable keeping all four hooves on the ground. Thus, they will walk along the fence and, when the fence ends, they will turn towards the x axis and continue walking in a straight line until they hit another fence segment or the side of the barn. Then they decide to go left or right until they reach the end of the fence segment, and so on, until they finally reach the side of the barn and then, potentially after a short walk, the ending point.

Naturally, the cows want to walk as little as possible. Find the minimum distance the cows have to travel back and forth to get from the starting point to the door of the barn.

Input

* Line 1: Two space-separated integers: N and S (-100,000 <= S <= 100,000)

• Lines 2..N+1: Each line contains two space-separated integers: A_i and B_i (-100,000 <= A_i < B_i <= 100,000), the starting and ending x-coordinates of fence segment i. Line 2 describes fence #1; line 3 describes fence #2; and so on. The starting position will satisfy A_N <= S <= B_N. Note that the fences will be traversed in reverse order of the input sequence.

  Output

• Line 1: The minimum distance back and forth in the x direction required to get from the starting point to the ending point by walking around the fences. The distance in the y direction is not counted, since it is always precisely N.

  Sample Input

  4 0

  -2 1

  -1 2

  -3 0

  -2 1

  Sample Output

  4

  Hint

  This problem has huge input data,use scanf() instead of cin to read data to avoid time limit exceed.

INPUT DETAILS:

Four segments like this:

+-+-S-+ Fence 4

+-+-+-+ Fence 3

+-+-+-+ Fence 2

+-+-+-+ Fence 1

|=|=|=*=|=|=| Barn

-3-2-1 0 1 2 3

OUTPUT DETAILS:

Walk positive one unit (to 1,4), then head toward the barn, trivially going around fence 3. Walk positive one more unit (to 2,2), then walk to the side of the barn. Walk two more units toward the origin for a total of 4 units of back-and-forth walking.

Source

USACO 2004 December Gold

這題其實還可以算作思路題，應該還有o(n^2)的dp

我們添加的時候倒叙去添加，相當于從牛出發的地方添加圍欄

每次我們用線段樹去看前一次是否覆寫

就是我們這一次圍欄 的長度能否覆寫從前一層，或者前幾層圍欄跳下來的點

#include<cstdio>
#include<algorithm>
#include<queue>
#define N 220000
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct node{
    int l,r,left,right,sum,v;
}tree[N<<2];
struct node1{
    int y,z,next;
}data[N<<2];
int cnt,tot,num,h[N<<1],tmp1,tmp2,l1,r1,l[N],r[N],n,s,root; 
void insert1(int x,int y,int z){
    data[++cnt].y=y;data[cnt].next=h[x];data[cnt].z=z;h[x]=cnt;
    //data[++cnt].y=x;data[cnt].next=h[y];data[cnt].z=z;h[y]=cnt;
}
void build(int &x,int l,int r){
    x=++num;tree[x].l=l;tree[x].r=r;
    if (l==r){return;}
    int mid=l+r>>1;
    build(tree[x].left,l,mid);build(tree[x].right,mid+1,r);
}
void update(int x){
    int l=tree[x].left,r=tree[x].right;
    tree[x].sum=tree[l].sum+tree[r].sum;
}
inline int abs(int x){
    return x>=0?x:-x;
}
void delete1(int x){
    if (tree[x].l==tree[x].r) {
    //  printf("%d ",tree[x].l);
        insert1(tree[x].v,tmp1,abs(tree[x].l-l1));//printf("%d %d %d\n",tree[x].v,tmp1,abs(tree[x].l-l1));
        insert1(tree[x].v,tmp2,abs(r1-tree[x].l));//printf("%d %d %d\n",tree[x].v,tmp2,abs(r1-tree[x].l));
        tree[x].sum=tree[x].v=0;return;
    }
    int l=tree[x].left,r=tree[x].right;
    if (tree[l].sum) delete1(l);
    if (tree[r].sum) delete1(r);
    update(x);
}
int query(int x,int l,int r){
    if (l<=tree[x].l&&r>=tree[x].r){
        if (tree[x].sum) delete1(x);return tree[x].sum;
    }
    int mid=tree[x].l+tree[x].r>>1;int tmp1=0,tmp2=0;
    if (l<=mid) tmp1=query(tree[x].left,l,r);
    if (r>mid) tmp2=query(tree[x].right,l,r);
    return tmp1+tmp2;
}
void insert2(int x,int l,int v){
    if (tree[x].l==tree[x].r){tree[x].sum=1;tree[x].v=v;return;}
    int mid=tree[x].l+tree[x].r>>1;
    if (l<=mid) insert2(tree[x].left,l,v);
    if (l>mid) insert2(tree[x].right,l,v);
    update(x);
}
bool flag[N<<1];int f[N<<1];queue<int> q;
void spfa(){
    for (int i=0;i<=tot;++i) f[i]=0x7fffffff;
    f[0]=0;flag[0]=true;q.push(0);
    while (q.size()){
        int x=q.front();flag[x]=false;q.pop();
        for (int i=h[x];i;i=data[i].next){
            int y=data[i].y,z=data[i].z;
            if (f[x]+z<f[y]) {
                f[y]=f[x]+z;
                if (flag[y]==false){
                    q.push(y);flag[y]=true;
                }
            }
        }
    }
}
int main(){
    freopen("poj2374.in","r",stdin);
    n=read();s=read();int l2=0x7fffffff,r2=-0x7fffffff;
    for (int i=1;i<=n;++i) l[i]=read(),r[i]=read(),l2=min(l2,l[i]),r2=max(r2,r[i]);
    build(root,l2,r2);
    insert1(0,1,s-l[n]);insert1(0,2,r[n]-s);insert2(root,l[n],1);insert2(root,r[n],2);tot=2;
    for (int i=n-1;i>=1;--i){
        //printf("%d\n",tree[root].sum);
        tmp1=++tot;tmp2=++tot;l1=l[i],r1=r[i];
        int tmp=query(root,l[i],r[i]);insert2(root,l1,tmp1);insert2(root,r1,tmp2);  
    }
    tmp1=tmp2=++tot;l1=0;r1=0;
    int tmp=query(root,l2,r2);
    spfa();
    printf("%d",f[tot]);
//  for (int i=1;i<=cnt;++i) printf("%d %d\n",data[i].y,data[i].z);