学步园

题意:

给出一些IP段,再给出一些IP,问这些IP是否在这些IP段中.

注意给出的段有可能左>右.要倒一下.

思路:

二分是已知值,找下标.在本题中是已知IP,找此IP应属于的段的下标.找到应属于的段的时候,判断是否在此段中即可.

/**
     几个错误:IP左边为高位,右边为低位,这个不能任意改.
             要用uint.修改要彻底.
             区间合并的时候不仅考虑嵌套,还有重叠,相邻.
**/

#include <cstdio>
#include <algorithm>
using namespace std;
typedef unsigned int uint;
const int MAX = 1000005;
const uint INF = ~0u;
int cnt,n;
typedef struct Seg{
    uint l,r;
}Seg;
bool cmp(Seg a, Seg b){
    return (a.l==b.l)?(a.r<b.r):(a.l<b.l);
}
Seg sg[MAX];
void MergeSeg()
{
    n = cnt;
    uint rmax = sg[0].r,il = 0;
    for(int i=1;i<cnt;i++)
    {
        while(sg[i].l<=rmax+1 && i<cnt)
        {
            if(sg[i].r>rmax)    rmax = sg[i].r;
            sg[i].l = sg[i].r = INF;
            i++;
            n--;
        }
        if(sg[i].l>rmax)
        {
            sg[il].r = rmax;
            il = i;
            rmax = sg[i].r;
        }
    }
    sort(sg,sg+cnt,cmp);
}
bool bin(uint x)
{
    int ans = -1,l = 0, r = n-1, mid;
    while(l<=r)
    {
        mid = (l+r)>>1;
        if(sg[mid].l > x)     r = mid - 1;
        else if(sg[mid].l < x)
        {
            ans = mid;
            l = mid + 1;
        }
        else
        {
            ans = mid;
            break;
        }
    }
    if(ans!=-1)
    {
        if(sg[ans].r>=x)    return true;
    }
    return false;
}
int main()
{
    uint a,b,c,d,x,y,z,w,i=0;
    while(scanf("%u.%u.%u.%u %u.%u.%u.%u",&a,&b,&c,&d,&x,&y,&z,&w)==8)
    {
        uint p = a*(1<<24) + b*(1<<16) + c*(1<<8) + d;
        uint q = x*(1<<24) + y*(1<<16) + z*(1<<8) + w;
        if(p<=q)
        {
            sg[i].l = p;
            sg[i++].r = q;
        }
        else
        {
            sg[i].l = q;
            sg[i++].r = p;
        }
    }
    cnt = i;
    sort(sg,sg+cnt,cmp);
    MergeSeg();
    getchar();
    while(scanf("%u.%u.%u.%u",&a,&b,&c,&d)==4)
    {
        uint tIP = a*(1<<24) + b*(1<<16) + c*(1<<8) + d;
        if(bin(tIP))    puts("yes");
        else    puts("no");
    }
}