ZOJ 2112 — Dynamic Rankings
要求你维护一个序列,支持两种操作:一种是查询某一个区间上的第k小值,一种是将序列中的某个数更改.
经典的线段树套平衡树+二分答案.太困了,不想多说为什么这样做,想知道的自己查阅资料.
300行程序,对于我来说其实并不多,可是这是没有用Object的行数.那么估计如果用了object,350行是最少的了.
这个东西也不好用object啊,除非写动态的平衡树.
其实挺惊讶于自己今天晚上的准确度,状态奇佳,这么长的程序竟然只出了两个小错(用注释//forgot!标记出来了).不过这两个小错也让我用对拍等手段调了一个多小时…
题目其实还不是很恶心的.Todo List又少了一道题了…不过同时每天也都在多题…
P.S.终于知道正确的二分答案该怎么写了…以前自己写的都太恶心了.
{
ZOJ 2112; Dynamic Rankings
- sqybi’s code
- 线段树+平衡树+二分答案
- Interval Tree, Splay
}
//for my winsty
program zju2112_sqybi;
const
nn = 50000;
mm = 10000;
kk = (mm + nn) * 25;
tt = 1000000000;
var
cases, times, n, m, i, num, x, y, z, l, r, mid, ans: longint;
ch: char;
a: array[1..nn]of longint;
father, data: array[1..kk]of longint;
son: array[0..1, 1..kk]of longint;
size: array[0..kk]of longint;
tree: array[1..nn*4]of record
l, r, root: longint;
end;
procedure rotate(x, w: longint);
var
y, z: longint;
begin
y := father[x];
z := size[y] - size[son[0, y]] - size[son[1, 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;
son[1-w, y] := son[w, x];
if son[w, x] <> 0 then
father[son[w, x]] := y;
son[w, x] := y;
father[y] := x;
size[x] := size[y];
size[y] := z + size[son[0, y]] + size[son[1, y]];
end;
procedure 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(father[x], 1);
rotate(x, 1);
end
else begin
rotate(x, 0);
rotate(x, 1);
end;
end
else begin
if x = son[1, father[x]] then begin
rotate(father[x], 0);
rotate(x, 0);
end
else begin
rotate(x, 1);
rotate(x, 0);
end;
end;
end
else
if x = son[0, father[x]] then
rotate(x, 1)
else
rotate(x, 0);
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 insert(var root: longint; y: longint);
var
x: longint;
begin
x := root;
repeat
inc(size[x]);
if y < data[x] then begin
if son[0, x] = 0 then break;
x := son[0, x];
end
else if y > data[x] then begin
if son[1, x] = 0 then break;
x := son[1, x];
end
else
break;
until false;
inc(num);
addNode(num, x, y);
if y < data[x] then
son[0, x] := num
else if y > data[x] then
son[1, x] := num;
if y <> data[x] then x := num;
root := x;
splay(root, 0);
end;
procedure delete(var root: longint; y: longint);
var
x, z: longint;
begin
x := root;
while data[x] <> y do begin
dec(size[x]);
if y < data[x] then
x := son[0, x]
else
x := son[1, x];
end;
dec(size[x]);
if size[x] - size[son[0, x]] - size[son[1, x]] > 0 then begin
root := x;
splay(x, 0);
exit;
end;
splay(x, 0);
if son[0, x] = 0 then begin
root := son[1, x];
father[son[1, x]] := 0;
end
else if son[1, x] = 0 then begin
root := son[0, x];
father[son[0, x]] := 0;
end
else begin
z := son[0, x];
while son[1, z] <> 0 do z := son[1, z];
splay(z, x);
son[1, z] := son[1, x];
father[son[1, z]] := z;
size[z] := size[z] + size[son[1, z]];
father[z] := 0; //forgot!
root := z;
end;
end;
function place(var root: longint; y: longint): longint;
var
x: longint;
begin
x := root;
repeat
if y < data[x] then begin
if son[0, x] = 0 then break;
x := son[0, x];
end
else if y > data[x] then begin
if son[1, x] = 0 then break;
x := son[1, x];
end
else
break;
until false;
splay(x, 0);
if data[x] > y then begin
if son[0, x] = 0 then begin
place := 0;
root := x; //forgot!
exit;
end;
x := son[0, x];
while son[1, x] <> 0 do x := son[1, x];
splay(x, 0);
end;
root := x;
place := size[x] - size[son[1, x]];
end;
procedure init(x, l, r: longint); //对x结点初始化,左边界l,右边界r
var
i: longint;
begin
tree[x].l := l;
tree[x].r := r;
inc(num);
tree[x].root := num;
addNode(num, 0, a[l]);
for i:=l+1 to r do
insert(tree[x].root, a[i]);
if l = r then exit;
init(x*2, l, (l+r) div 2);
init(x*2+1, (l+r) div 2+1, r);
end;
function get(x, y: longint): longint; //从x结点求第y个位置对应的数字
begin
get := 0;
if (tree[x].l > y) or (tree[x].r < y) then exit;
if tree[x].l = tree[x].r then begin
get := data[tree[x].root];
exit;
end;
get := get(x*2, y) + get(x*2+1, y);
end;
procedure paint(x, y, pre, now: longint); //从x结点开始将包含y结点的段里的pre改为now
begin
if (tree[x].l > y) or (tree[x].r < y) then exit;
if tree[x].l = tree[x].r then begin
data[tree[x].root] := now;
exit;
end;
delete(tree[x].root, pre);
insert(tree[x].root, now);
paint(x*2, y, pre, now);
paint(x*2+1, y, pre, now);
end;
function cal(x, l, r, y: longint): longint; //从x结点计算l到r范围内有多少比y小或相等的
begin
cal := 0;
if (tree[x].l > r) or (tree[x].r < l) then exit;
if (tree[x].l >= l) and (tree[x].r <= r) then begin
cal := place(tree[x].root, y);
exit;
end;
cal := cal(x*2, l, r, y) + cal(x*2+1, l, r, y);
end;
function check(k: longint): boolean;
var
r: longint;
begin
r := cal(1, x, y, k);
check := r >= z;
end;
begin
readln(cases);
for times:=1 to cases do begin
readln(n, m);
for i:=1 to n do read(a[i]);
readln;
num := 0;
init(1, 1, n);
for i:=1 to m do begin
read(ch);
if ch = ‘C’ then begin
readln(x, y);
z := get(1, x);
paint(1, x, z, y);
end
else begin
readln(x, y, z);
l := 0;
r := tt;
ans := -1;
while l <= r do begin
mid := (l + r) div 2;
if check(mid) then begin
ans := mid;
r := mid - 1;
end
else
l := mid + 1;
end;
writeln(ans);
end;
end;
end;
end.
阅读(198 次)