var
tmp,data,father,size,ans,num:array[0..100000] of longint;
t:array[0..50000,1..3] of longint;
i,j,m,n,root,node:longint;
son:array[0..1,0..100000] of longint;
procedure Qsort(s,l:longint);
var i,j,mid,tmp:longint;
begin
i:=s; j:=l; mid:=t[(i+j) div 2,1];
repeat
while (t[i,1]<mid) do i:=i+1;
while (t[j,1]>mid) do j:=j-1;
if i<=j then
begin
tmp:=t[i,1];
t[i,1]:=t[j,1];
t[j,1]:=tmp;
tmp:=t[i,2];
t[i,2]:=t[j,2];
t[j,2]:=tmp;
tmp:=t[i,3];
t[i,3]:=t[j,3];
t[j,3]:=tmp;
tmp:=num[i];
num[i]:=num[j];
num[j]:=tmp;
inc(i);
dec(j);
end;
until i>j;
if s<j then Qsort(s,j);
if i<l then Qsort(i,l);
end;
Procedure update(x:longint);
begin
size[x]:=size[son[0,x]]+size[son[1,x]]+1;
end;
Procedure Lrot(x:longint);
var y:longint;
begin
y:=father[x];
son[1,y]:=son[0,x];
if son[0,x]<>0 then
begin
father[son[0,x]]:=y;
end;
father[x]:=father[y];
if father[y]<>0 then
begin
if son[0,father[y]]=y then
begin
son[0,father[y]]:=x;
end
else
begin
son[1,father[y]]:=x;
end;
end;
son[0,x]:=y;
father[y]:=x;
update(y);
update(x);
end;
Procedure Rrot(x:longint);
var y:longint;
begin
y:=father[x];
son[0,y]:=son[1,x];
if son[1,x]<>0 then
begin
father[son[1,x]]:=y;
end;
father[x]:=father[y];
if father[y]<>0 then
begin
if son[0,father[y]]=y then
begin
son[0,father[y]]:=x;
end
else
begin
son[1,father[y]]:=x;
end;
end;
son[1,x]:=y;
father[y]:=x;
update(y);
update(x);
end;
Procedure splay(x,y:longint);
begin
while father[x]<>y do
begin
if father[father[x]]=y then
begin
if x=son[0,father[x]] then
begin
Rrot(x);
end
else
begin
Lrot(x);
end;
end
else
if father[x]=son[0,father[father[x]]] then
begin
if x=son[0,father[x]] then
begin
Rrot(father[x]);
Rrot(x);
end
else
begin
Lrot(x);
Rrot(x);
end;
end
else
begin
if x=son[1,father[x]] then
begin
Lrot(father[x]);
Lrot(x);
end
else
begin
Rrot(x);
LRot(x);
end;
end;
if y=0 then
root:=x;
end;
end;
Procedure addnode(x,y,z:longint);
begin
data[x]:=z;
father[x]:=y;
son[0,x]:=0;
son[1,x]:=0;
size[x]:=1;
end;
Procedure init;
begin
root:=0;
node:=0;
end;
Procedure ins(k:longint);
var y:longint;
begin
if root=0 then
begin
root:=1;
node:=1;
addnode(1,0,k);
exit;
end;
y:=root;
repeat
inc(size[y]);
if k<data[y] then
begin
if son[0,y]<>0 then
y:=son[0,y]
else
begin
inc(node);
addnode(node,y,k);
son[0,y]:=node;
y:=node;
break;
end;
end
else
begin
if son[1,y]<>0 then
y:=son[1,y]
else
begin
inc(node);
addnode(node,y,k);
son[1,y]:=node;
y:=node;
break;
end;
end;
until false;
splay(y,0);
end;
function rank(x:longint):longint;
var y:longint;
begin
y:=root;
while true do begin
if x<=size[son[0,y]] then
y:=son[0,y]
else
if x=size[son[0,y]]+1 then break
else begin
x:=x-size[son[0,y]]-1;
y:=son[1,y];
end;
end;
rank:=data[y];
splay(y,0);
end;
function find(x:longint):longint;
var
y: longint;
begin
y := root;
repeat
if data[y] = x then break;
if x < data[y] then begin
if son[0, y] = 0 then
break
else
y := son[0, y];
end
else begin
if son[1, y] = 0 then
break
else
y := son[1, y];
end;
until false;
find:= y;
splay(y, 0);
end;
Procedure del(x:longint);
var y,z:longint;
begin
y:= find(x);
splay(y, 0);
if son[0, y] = 0 then begin
if son[1, y] = 0 then
init
else begin
root := son[1, y];
father[son[1, y]] := 0;
end;
end
else begin
z := son[0, y];
while son[1, z] <> 0 do z := son[1, z];
splay(z, y);
son[1, z] := son[1, y];
if son[1, y] <> 0 then father[son[1, y]] := z;
father[z] := 0;
root := z;
update(z);
end;
end;
begin
readln(n,m);
init;
for i:=1 to n do
begin
read(tmp[i]);
end;
for j:=1 to m do
begin
readln(t[j,1],t[j,2],t[j,3]);
num[j]:=j;
end;
Qsort(1,m);
for i:=t[1,1] to t[1,2] do
begin
ins(tmp[i]);
end;
ans[num[1]]:=rank(t[1,3]);
for j:=2 to m do
begin
if t[j-1,2]<t[j,1] then
for i:=t[j-1,1] to t[j-1,2] do
begin
del(tmp[i]);
end
else
for i:=t[j-1,1] to t[j,1]-1 do
del(tmp[i]);
if t[j-1,2]<t[j,1] then begin
for i:=t[j,1] to t[j,2] do
begin
ins(tmp[i]);
end;
end
else
begin
for i:=t[j-1,2]+1 to t[j,2] do
begin
ins(tmp[i]);
end;
end;
ans[num[j]]:=rank(t[j,3]);
end;
for i:=1 to m do
begin
write(ans[i]);
end;
end.
2008年8月17日星期日
First Time Splay Tree for PKU 2761
First Time Splay Tree for PKU 2761
Mathematicians' Academic Family Tree
Sometimes, the academic influences from those academic advisors would be extremely important for mathematicians to build their paths to their academic summit.
Here I got one website that records those famous mathematician's Genealogy:
http://genealogy.math.ndsu.nodak.edu/index.php
This is the part of 华罗庚's genealogy profile:
Luo-Geng Hua
Ph.D.
Dissertation:
Advisor: Unknown
Student(s):
Click here to see the students listed in chronological order.
| Name | School | Year | Descendants |
|---|---|---|---|
| Raymond Ayoub | University of Illinois at Urbana-Champaign | 1950 | 7 |
| Jingrun Chen | Chinese Academy of Sciences | ||
| Xiaxi (Xiaqi) Ding | Academia Sinica | 1956 | 8 |
| Zhe-Xian Wan | Academia Sinica | 1 | |
| Yuan Wang | Academia Sinica |
According to our current on-line database, Luo-Geng Hua has 5 students and 21 descendants.
订阅：
博文 (Atom)