POJ 2481 Cows （线段树||树状数组）

阳光穿透心脏的1/2处 2022-06-12 01:39 179阅读 0赞

Farmer John's cows have discovered that the clover growing along the ridge of the hill (which we can think of as a one-dimensional number line) in his field is particularly good.  
  
Farmer John has N cows (we number the cows from 1 to N). Each of Farmer John's N cows has a range of clover that she particularly likes (these ranges might overlap). The ranges are defined by a closed interval \[S,E\].  
  
But some cows are strong and some are weak. Given two cows: cow i and cow j, their favourite clover range is \[Si, Ei\] and \[Sj, Ej\]. If Si <= Sj and Ej <= Ei and Ei - Si > Ej - Sj, we say that cow i is stronger than cow j.  
  
For each cow, how many cows are stronger than her? Farmer John needs your help!

Input

The input contains multiple test cases.  
For each test case, the first line is an integer N (1 <= N <= 10 5), which is the number of cows. Then come N lines, the i-th of which contains two integers: S and E(0 <= S < E <= 10 5) specifying the start end location respectively of a range preferred by some cow. Locations are given as distance from the start of the ridge.  
  
The end of the input contains a single 0.

Output

For each test case, output one line containing n space-separated integers, the i-th of which specifying the number of cows that are stronger than cow i.

Sample Input

3
    1 2
    0 3
    3 4
    0

Sample Output

1 0 0

Hint

Huge input and output,scanf and printf is recommended.

题解：

。。怎么感觉数据结构的题都是卡时间卡内存贼恶心，输出的时候因为加了个判断就无限tle。。下次记住写代码一定要省时间，去掉不必要的判断，这题我是先用线段树做的，先把线段以左边坐标从小到大排序，如果相同按右边坐标从大到小排序，然后依次放入线段树，以右坐标为点更新经过的区间（由于是按左坐标排了序的，只要满足前面的区间覆盖过把了当前区间的右边就算是被覆盖了，即前面的牛比他强壮），区间数++，然后搜索的时候从右坐标往大区间后搜索，得到的区间num就是答案，然后注意要特判，如果。线段左右相同则不用搜索了（搜就错了）。。

线段树代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<deque>
    using namespace std;
    int ans[100005];
    struct cow//记录奶牛吃草情况及其id
    {
        int l,r;
        int id;
    };
    bool cmp(cow x,cow y)//区间排序，先把线段以左边坐标从小到大排序，如果相同按右边坐标从大到小排序，
    {
        if(x.l!=y.l)
            return x.l<y.l;
        else
            return x.r>y.r;
    }
    cow a[100005];
    struct node
    {
        int l,r;
        int sum;//放区间有几头牛覆盖
    };
    node t[4*100005];
    void Build(int l,int r,int num)//日常建树
    {
        t[num].l=l;
        t[num].r=r;
        t[num].sum=0;
        if(l==r)
        {
            return;
        }
        int mid=(l+r)/2;
        Build(l,mid,num*2);
        Build(mid+1,r,num*2+1);
    }
    void update(int x,int num)//更新区间，把经过的区间++
    {
        t[num].sum++;
        if(t[num].l==t[num].r)
        {
            return;
        }
        int mid=(t[num].r+t[num].l)/2;
        if(x<=mid)
            update(x,num*2);
        else
            update(x,num*2+1);
    }
    int query(int l,int r,int num)//询问能够覆盖区间的奶牛数目
    {
        if(t[num].l==l&&t[num].r==r)
        {
            return t[num].sum;
        }
        int mid=(t[num].r+t[num].l)/2;
        if(r<=mid)
            return query(l,r,num*2);
        else if(l>mid)
            return query(l,r,num*2+1);
        else
        {
            return query(l,mid,num*2)+query(mid+1,r,num*2+1);
        }
    }
    int main()
    {
        int n,i,j;
        while(scanf("%d",&n)!=EOF&&n)
        {
            Build(1,100001,1);
            for(i=0;i<n;i++)
            {
                scanf("%d%d",&a[i].l,&a[i].r);
                a[i].id=i;
            }
            sort(a,a+n,cmp);
            for(i=0;i<n;i++)
            {
                if(i>0&&a[i-1].l==a[i].l&&a[i-1].r==a[i].r)//特判
                {
                    ans[a[i].id]=ans[a[i-1].id];
                }
                else
                    ans[a[i].id]=query(a[i].r+1,100001,1);
                update(a[i].r+1,1);
            }
            printf("%d",ans[0]);//超时所在。。如果是i=0，加上循环特判就会超时，很迷
            for(i=1;i<n;i++)
            {
                printf(" %d",ans[i]);
            }
            printf("\n");
        }
        return 0;
    }

然后是树状数组代码，没看题解一遍ac了，然感觉树状数组写起来简单一些，内存也小一些，时间也快些，yoyoyo我会树状数组了

代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<deque>
    using namespace std;
    int ans[100005];
    struct cow//记录奶牛吃草情况及其id
    {
        int l,r;
        int id;
    };
    bool cmp(cow x,cow y)//区间排序，先把线段以左边坐标从小到大排序，如果相同按右边坐标从大到小排序，
    {
        if(x.l!=y.l)
            return x.l<y.l;
        else
            return x.r>y.r;
    }
    cow a[100005];
    int num[100005];//保存树状数组情况
    int lowbit(int x)//找父子区间神奇
    {
        return x&(-x);
    }
    void update(int x)//因为是向前更新，所以是减去lowbit
    {
        while(x>0)//这里填界限
        {
            num[x]++;
            x-=lowbit(x);
        }
    }
    int query(int x)//向后查找，是加上lowbit
    {
        int s=0;
        while(x<=100001)//这里填界限
        {
            s+=num[x];
            x+=lowbit(x);
        }
        return s;//返回和
    }
    int main()
    {
        int n,i,j;
        while(scanf("%d",&n)!=EOF&&n)
        {
            for(i=0;i<n;i++)
            {
                scanf("%d%d",&a[i].l,&a[i].r);
                a[i].id=i;
            }
            memset(num,0,sizeof(num));//初始化
            sort(a,a+n,cmp);
            for(i=0;i<n;i++)
            {
                if(i>0&&a[i].r==a[i-1].r&&a[i].l==a[i-1].l)//判断前后区间是否一样
                    ans[a[i].id]=ans[a[i-1].id];
                else
                    ans[a[i].id]=query(a[i].r+1);
                update(a[i].r+1);//更新区间
            }
            printf("%d",ans[0]);
            for(i=1;i<n;i++)
            {
                printf(" %d",ans[i]);
            }
            printf("\n");
        }
        return 0;
    }