POJ 2985 — The k-th Largest Group [RE]
变态题.做了好久了,刚开始WA,今天晚上下定决心调过,结果RE了.
和cy的AC程序对拍,拍了几十组极限数据都没错,而且我的程序比他的快得多…
现在唯一可能错的地方大概就是那个又臭又长的TBinarySearchTree.delete(x, y: longint);了(名字就又臭又长…),可是还是不知道哪儿有错.
如果你知道这道题有什么阴人的地方…请告诉我…
代码即使没有AC也差不多都对了,所以贴出来.希望有人能帮我看完代码…不过我知道不可能…
{
The k-th Largest Group; cat; POJ 2985
- sqybi’s code
- 并查集+平衡树
- 祝福爱德华多…
}
//for my winsty, for Eduardo
program pku2985_sqybi;
const
nn = 200000;
mm = 200000;
type
TUnionFindSets = object
size, father: array[1..nn]of longint;
procedure init;
function getF(x: longint): longint;
procedure combine(x, y: longint);
end;
TBinarySearchTree = object
root, num: longint;
size: array[0..nn+mm]of longint;
data, father: array[1..nn+mm]of longint;
son: array[0..1, 1..nn+mm]of longint;
procedure init;
procedure rotate(w, x: longint);
procedure splay(x, y: longint);
procedure addNode(x, y, z: longint);
procedure insert(x, y: longint);
procedure delete(x, y: longint);
function rank(x, y: longint): longint;
end;
var
ufs: TUnionFindSets;
bst: TBinarySearchTree;
n, m, i, c, x, y, fx, fy: longint;
procedure TUnionFindSets.init;
var
i: longint;
begin
fillchar(father, sizeof(father), 0);
for i:=1 to n do
size[i] := 1;
end;
function TUnionFindSets.getF(x: longint): longint;
var
y, z: longint;
begin
y := x;
while father[x] <> 0 do
x := father[x];
getF := x;
while y <> x do begin
z := father[y];
father[y] := x;
y := z;
end;
end;
procedure TUnionFindSets.combine(x, y: longint);
begin
father[y] := x;
size[x] := size[x] + size[y];
size[y] := 0;
end;
procedure TBinarySearchTree.init;
begin
root := 1;
num := 1;
size[1] := n;
data[1] := 1;
father[1] := 0;
son[0, 1] := 0;
son[1, 1] := 0;
end;
procedure TBinarySearchTree.rotate(w, x: longint);
var
y, z: longint;
begin
y := father[x];
z := size[y] - size[son[0, y]] - size[son[1, y]];
son[1-w, y] := son[w, x];
if son[w, x] <> 0 then
father[son[w, x]] := y;
son[w, x] := y;
father[x] := father[y];
if father[y] <> 0 then
if y = son[0, father[y]] then
son[0, father[y]] := x
else
son[1, father[y]] := x;
father[y] := x;
size[x] := size[y];
size[y] := z + size[son[0, y]] + size[son[1, y]];
end;
procedure TBinarySearchTree.splay(x, y: longint);
begin
while father[x] <> y do begin
if father[father[x]] <> y then begin
if father[x] = son[0, father[father[x]]] then begin
if x = son[0, father[x]] then begin
rotate(1, father[x]);
rotate(1, x);
end
else begin
rotate(0, x);
rotate(1, x);
end;
end
else begin
if x = son[1, father[x]] then begin
rotate(0, father[x]);
rotate(0, x);
end
else begin
rotate(1, x);
rotate(0, x);
end;
end;
end
else
if x = son[0, father[x]] then
rotate(1, x)
else
rotate(0, x);
end;
end;
procedure TBinarySearchTree.addNode(x, y, z: longint);
begin
father[x] := y;
data[x] := z;
size[x] := 1;
son[0, x] := 0;
son[1, x] := 0;
end;
procedure TBinarySearchTree.insert(x, y: longint);
begin
if root = 0 then begin
inc(num);
addNode(num, 0, y);
root := num;
end;
while data[x] <> y do begin
inc(size[x]);
if y < data[x] then begin
if son[0, x] = 0 then
break
else
x := son[0, x];
end
else begin
if son[1, x] = 0 then
break
else
x := son[1, x];
end;
end;
if data[x] = y then
inc(size[x])
else begin
inc(num);
addNode(num, x, y);
if y < data[x] then
son[0, x] := num
else
son[1, x] := num;
end;
root := x;
splay(root, 0);
end;
procedure TBinarySearchTree.delete(x, y: longint);
begin
while data[x] <> y do
if y < data[x] then
x := son[0, x]
else
x := son[1, x];
if size[x] > 1 then
while x <> 0 do begin
dec(size[x]);
x := father[x];
end
else begin
root := x;
splay(root, 0);
if son[0, x] = 0 then begin
if son[1, x] = 0 then begin
root := 0;
num := 0;
end
else begin
root := son[1, x];
father[son[1, x]] := 0;
end;
end
else begin
y := son[0, x];
while son[1, y] <> 0 do
y := son[1, y];
splay(y, x);
son[1, y] := son[1, x];
father[y] := 0;
if son[1, x] <> 0 then
father[son[1, x]] := y;
size[y] := size[y] + size[son[1, y]];
root := y;
end;
end;
end;
function TBinarySearchTree.rank(x, y: longint): longint;
begin
if size[son[0, x]] >= y then
rank := rank(son[0, x], y)
else if size[x] - size[son[1, x]] >= y then begin
rank := data[x];
root := x;
splay(root, 0);
end
else
rank := rank(son[1, x], y-size[x]+size[son[1, x]]);
end;
begin
readln(n, m);
ufs.init;
bst.init;
for i:=1 to m do begin
read(c);
if c = 0 then begin
readln(x, y);
fx := ufs.getF(x);
fy := ufs.getF(y);
if fx <> fy then begin
bst.delete(bst.root, ufs.size[fx]);
bst.delete(bst.root, ufs.size[fy]);
ufs.combine(fx, fy);
bst.insert(bst.root, ufs.size[fx]);
end;
end
else begin
readln(x);
writeln(bst.rank(bst.root, bst.size[bst.root]-x+1));
end;
end;
end.
阅读(142 次)