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 winstyprogram 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 […]