程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj2481 cows（線段樹單點更新）

poj2481 cows（線段樹單點更新）

編輯：C++入門知識

poj2481 cows（線段樹單點更新）

題目鏈接：

huangjing

題目意思：

給出n頭牛的活動區間，比如區間[SI，sj]和[EI,EJ]，如果前面一個區間完全包含另外一個區間那麼說明前一頭牛比後一頭牛強壯。

思路：根據區間的右區間數來建樹，然後用sum[]來維護牛在這些右區間的頭數。首先要根據牛的區間順序進行排序，當然從左像右排序，那麼後面進行查詢比自己強的牛的時候那麼就只用找右區間比自己大的就可以了。那麼如何更新呢？？只需要單點查詢，然後知道找到這頭牛的右區間即可。。。那麼這個問題就解決了。。。

題目：

Language: Cows Time Limit: 3000MS Memory Limit: 65536K Total Submissions: 13017 Accepted: 4327

Description

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⁵), 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⁵) 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

Sample Output

1 0 0

Hint

Huge input and output,scanf and printf is recommended.

Source

POJ Contest,Author:Mathematica@ZSU

[Submit] [Go Back] [Status] [Discuss]

Home Page Go Back To top

#include
#include
#include
#include
#include
#include
#include
#include
#include
#define eps 1e-9
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=100000+10;

int sum[maxn<<2],n,ans[maxn];

struct Node
{
    int st,en,id;
}node[maxn];

bool cmp(Node a,Node b)
{
    if(a.st==b.st)
        return a.en>b.en;
    return a.st>1;
    buildtree(l,mid,dex<<1);
    buildtree(mid+1,r,dex<<1|1);
}

int Query(int l,int r,int dex,int L,int R)
{
    if(L<=l&&R>=r)  return sum[dex];
    int mid=(l+r)>>1;
    if(L>mid) return Query(mid+1,r,dex<<1|1,L,R);
    else if(R<=mid) return  Query(l,mid,dex<<1,L,R);
    else return  Query(mid+1,r,dex<<1|1,L,R)+Query(l,mid,dex<<1,L,R);
}

void Update(int l,int r,int pos,int dex)
{
    sum[dex]++;
    if(l==r)  return;
    int mid=(l+r)>>1;
    if(pos<=mid)  Update(l,mid,pos,dex<<1);
    else Update(mid+1,r,pos,dex<<1|1);
}

int main()
{
    while(~scanf("%d",&n),n)
    {
        for(int i=1;i<=n;i++)
        {
             scanf("%d%d",&node[i].st,&node[i].en);
             node[i].id=i;
        }
        sort(node+1,node+1+n,cmp);
        buildtree(0,maxn,1);
        for(int i=1;i<=n;i++)
        {
            if(i!=1&&node[i].st==node[i-1].st&&node[i].en==node[i-1].en)//注意這個地方如果前後兩個區間相等的話，因為前面一個更新的時候這個去年+1了，所以這裡要判斷一下
                ans[node[i].id]=ans[node[i-1].id];
            else
                ans[node[i].id]=Query(0,maxn,1,node[i].en,maxn);
            Update(0,maxn,node[i].en,1);
        }
        for(int i=1;i