Tsinsen A1377. 樓房重建

Brief description:

。。維護一個區間。。每個位置有一個樓房。。。問一個人站在 (0, 0) 位置。。抬頭最多能看到多少樓房。。
。。(。支持單點修改。

Analysis:

(。這個題線段樹的做法有點厲害。。。以下直接貼 Seter 題解。。。

半年前和主席討論過類似的問題,得出的結論是只能sqrtnlgn,再怎麼優化也只能sqrtn。。
結果居然有線段樹做法。。
首先我們把每個房屋的Y除以X,再在最左邊加個0,這樣的話,答案就是從0開始,每次往右邊跳到嚴格比它大的第一個數上,直到不能跳為止,總共跳了幾次。。
比如得出來是0 2 1.5 2.333,那就是跳了2次,答案就是2。
當時只想出了分塊。。問了一些神犇他們都不肯好好幫忙想。。於是就擱置了。。
標程是一種線段樹做法。。
首先注意到,在一段中跳,最後必定在最大的那個數上停下來。
每個點代表一個區間,維護兩個東西:這個區間的最大數和這個區間的最左邊加個0後從0開始往右跳能跳幾次。

const int _N = 100009, N = _N * 4;
int lc[N], rc[N]; DB mm[N]; int jp[N]; // 這個區間的最大數和這個區間的最左邊加個 0 後從 0 開始往右跳能跳幾次。 
int nn; int xx, yy; DB slop;
int n, root;
.. .

然後每個節點再支持一個操作:假設最左邊來了個x,在這個區間中,從 x 開始往右跳能跳幾次。
這個操作有哪些用處呢?
第一就是x=0時,得出的答案恰好就是這個點中要維護的那個東西。
第二就是,我可以合併兩個相鄰區間的從0開始跳的答案了!因為我必定是從0開始跳到左兒子的最大數上,然後再從左兒子的最大數開始往右兒子跳。

void Upd(int x){
    mm[x] = max(mm[lx], mm[rx]);
    jp[x] = jp[lx] + Jmp(rx, mm[lx]);
}
.. .

則整個區間的答案就是,左兒子從0開始跳的答案(這個直接維護了),加上右兒子從左兒子最大數(這個也直接維護了)開始跳的答案(這個遞歸下去算)。
由於每次只遞歸右兒子,所以每個點算答案還是lgn的,這樣就可以lg^2n修改了。
—————————————————————————————————————————–
那怎麼才能實現這個操作呢?
我們發現,如果x比左兒子的最大數還要大,那麼左兒子就是沒有用的,直接返回右兒子的答案就可以了。
否則呢?難道要返回左兒子從x開始跳的答案加上右兒子從左兒子最大數開始跳的答案嗎?可是這樣兩邊都要遞歸了,複雜度就壞掉了。。
我們再來看看上面提到的合併區間的方法:
「則整個區間的答案就是,左兒子從0開始跳的答案(這個直接維護了),加上右兒子從左兒子最大數(這個也直接維護了)開始跳的答案(這個遞歸下去算)。」
換句話說,右兒子從左兒子最大數開始跳的答案,就是整個區間從0開始跳的答案減去左兒子從0開始跳的答案,而這兩個答案都直接維護了!
所以這也只需要遞歸一個兒子即可。

int Jmp(int x, DB h){
    if (lx) return mm[lx] <= h ? Jmp(rx, h) : jp[x] - jp[lx] + Jmp(lx, h);
    return h < mm[x];
}
.. .

整體複雜度是lg^2n的。

高端線段樹
。高端線段樹。(堆式存儲。。

External link:

http://www.tsinsen.com/A1377