【树状数组】Cows

(POJ2481)

Time Limit:1000MS Memory

Limit:65536K

Total Submit:16 Accepted:8

Description

【问题描述】

约翰是一个农民，他养了一群羊，一群很喜欢吃山上的三叶草的羊。所有的三叶草都生长在一条直线上，味道十分美妙。

约翰有N头牛，分别叫牛1到牛N。每头牛都有特别中意的三叶草范围，记为[S,E]——这是直线上的一个区间。不同牛喜欢的三叶草范围之间可能重叠。

有些牛比较强壮，有些牛比较弱小。给定两头牛：牛i和牛j。它们喜欢的三叶草范围分别为[Si, Ei]和[Sj, Ej]。如果Si

<=Sj 并且 Ej <=Ei 并且 Ei-Si

> Ej-Sj，那么就认为牛i比牛j更强壮。

对于每头牛，有多少头牛比它更强壮呢？约翰请你来帮忙。

Input

输入包括多组数据。对于每组数据，第一行是整数N

(1 <= N <=

105)，表示牛的头数。接下来N行，第i行有两个整数S和E(0 <= S

< E <= 105)，表示牛i喜欢的三叶草区间。

最后一组数据只有0，表示结束。

Output

对于每组测试数据，输出一行，包括n个用空格分开的整数，第i个整数表示比牛i更强壮的牛的数目。

Sample

Input

3

1 2

0 3

3 4

0

Sample

Output

1 0 0

Hint

对于C/C++程序员：数据规模较大，建议采用scanf 和 printf。

请将你的程序在 http://poj.org/problem?id=2481 上提交测试是否能通过！

Source

POJ2481

这题想了好久，也上网看了不少解题报告，都是说“和

数星星 那道题一样”，我却怎么也不明白，而且网上给的程序都是用C语言写的。很是郁闷。

其实这题给出区间边界x，y 可以把他们看成是 横坐标

和 纵坐标。 然后就和 数星星 差不多了

先按

y从大到小排序，y相等的从小到大排序

树状数组的下标为x，把排好序的数组从头到尾扫一遍，把结果储存在另一个数组。

这题我先是超时，检查了好久，竟发现是快排写错了。少了个while循环。

然后又是WA，对两个区间完全相同的情况处理错了。

并且，POJ上是多组数据，而我得到的翻译版本竟是单组数据。。

var

n,max:longint;

a:array[0..100010,1..4]of longint;

f:array[0..100010]of longint;

b:array[0..100010]of longint;

procedure init;

var

i:longint;

begin

for i:=1 to n do

begin

readln(a[i,1],a[i,2]);

inc(a[i,1]);

inc(a[i,2]);

if a[i,2]>max then

max:=a[i,2];

a[i,3]:=i;

end;

end;

procedure

qsort1(x,y:longint);

var

i,j,k1,k2,k:longint;

begin

if x>=y then exit;

i:=x;

j:=y;

k:={random(j-i)+i;}(i+j)div 2;

k1:=a[k,1];

k2:=a[k,2];

while i

begin

while

(a[i,2]>k2)or((a[i,2]=k2)and(a[i,1]

do inc(i);

while

(a[j,2]k1))

do dec(j);

if i<=j then

begin

a[0]:=a[i];

a[i]:=a[j];

a[j]:=a[0];

inc(i);

dec(j);

end;

end;

qsort1(i,y);

qsort1(x,j);

end;

function

find(i:longint):longint;

begin

find:=0;

if i=0 then exit;

while i>0 do

begin

inc(find,f[i]);

i:=i-i and -i;

end;

end;

procedure

add(i:longint);

begin

if i=0 then exit;

while i<=max do

begin

inc(f[i]);

i:=i+i and -i;

end;

end;

procedure main;

var

i,j:longint;

begin

i:=1;

while i<=n do

begin

j:=i;

while

(a[i,2]=a[j,2])and(a[i,1]=a[j,1]) do

begin

if i=j then

a[i,4]:=find(a[i,1])

else a[i,4]:=a[j,4];

add(a[i,1]);

inc(i);

end;

if i=j then inc(i);

end;

end;

procedure print;

var

i:longint;

begin

for i:=1 to n do b[a[i,3]]:=i;

for i:=1 to n do

write(a[b[i],4],' ');

writeln;

end;

begin

randomize;

readln(n);

while n<>0 do

begin

fillchar(a,sizeof(a),0);

fillchar(f,sizeof(f),0);

fillchar(b,sizeof(b),0);

max:=0;

init;

qsort1(1,n);

main;

print;

read(n);

end;

end.