(由於被 fgd BS 了英文。。我把題目背景都刪了。。)
Brief description :
You are given a sequence A[1], A[2],…, A[N]. On this sequence you have to apply M operations: Add all the elements whose value are in range [l, r] by d or, ask for a query how many element are in range [l, r].
( 1≤ N ≤ 250,000, M ≤ 50,000), |A[i]| ≤ 1,000,000,000 .)
Analysis :
哎。。我現在已經覺得這個題出的真是失敗啊。。
(嘛。。題目出成這樣我也沒有什麼可辯解的了。。
。。開始覺得這是數據結構 S 級神題的。。)
原題是在 那個操作 的基礎上維護第 K 大的數。。。內測得時候幾乎無人做。。因此簡化成了統計某個區間內數的多少。。。求第 K 大的話在這個基礎上進行二分即可,因為沒有直接的辦法。。
那麼,對於值域在某個區間內的數進行操作,首先想到的是 伸展樹,她的一個神技是兩次 Splay 操作將某個區間的所有樹伸展到某個容易訪問的子樹位置。
那麼,接下來?。。。、打標記?
如圖所示。。(。。。)
這個操作會破壞鍵值。。。也是因為同樣的原因,線段樹 塊狀鏈表 都不奏效。。
。。。這是這個問題的難點所在。。。下面對 鍵值處在某個範圍的數整題加上某個數 這個操作進行進一步的觀察。。
可以得到下面兩個性質。
- 選出的序列,在操作的前後相對順序不發生改變。
- 在任意時刻,如果兩個數額鍵值相同,那麼今後,它們會一直作為一個整體存在。
….
為了防止有人用第二個性質亂搞。。題目 Ai 值的範圍要儘可能的大。。
第一個性質。。提示我們用 塊狀結構 來解決掉這個問題。。。
標程使用的是 伸展森林 … 字面上的意思,也就是維護一組伸展樹,每次對每棵伸展樹伸展出選定的區間,然後打上標記分離出來(喀嚓!)。。
等到伸展樹的棵樹達到 某個值 (一般設定為 sqrt(n) 然後考慮到 常數,再減小一點。。不判斷塊樹而是每隔一段時間重構一次。。大概用一個對數函數。。。)
的時候。。推掉重練。。(這裡注意一個地方。實際中重構的話用 std::sort 比用堆然後分塊合併要快。。)
這裡的標記只要記錄在根節點即可,不需要下放。。
(一個容易出錯的地方是,雖然我保證中間的數據也不會爆 int32,但是在處理 delta 的時候可能會爆。。所以如果想保持主要的結構都使用 int32 的話這裡要特判一下。。)
一個嚴重的問題就此產生了:
似乎一眼看上去,splay 的顆樹會呈指數爆炸?!。。。
嗯嗯。。這個問題。。我還。。不知道怎麼證明。(什麼!)
。。但是看上去似乎(對於隨機生成的數據)這種情況不會出現 。。
下面我試圖說一點我的想法。。
定義
/theta = sqrt Sigma i, j sqr(Ai – Aj)
為一個數集的 離散程度。(注意不能直接使用方差。。吧。。)
(於是,重新考察前面的性質2,雖然說要中間恰好相等可能不太會出現。
但是有跡象表明,操作過後數列可能在某幾個位置集中。。而這就相當於降低了 N 的規模)。。
對於某一次操作,會發生下面兩種事情之一
- 數列的離散程度下降,同時,塊數增多。
- Nothing happend (什麼都沒有發生)。。
…
好吧。。大概就是這樣了。。。
(我以後會繼續考慮這個問題的。。如果有么進展的話會及時更新。。)
—-
我看到賽後很多同學提交了 線段樹 的方法。。。本質上都差不多吧。。
複雜度的話。。是
P = sqrt(n)
O( (M / log P) N log P) = O(NM)..
P 是塊數上限。。 M / log P 是重構頻率。。(= =。。。。)
隨著 M 的增大逐漸向 O(nlogn) 收斂(因為根據 觀察 後期塊數很少再增加。。)
(然後還會 很慢很慢 的 向 O(1) 收斂 。。考慮所有數的值都一樣的時候。。大概隨機情況下要進行一個天文數字次才可能發生吧。哎。。要會一點概率論就好了啊。。。。。)
—-
我把 SPOJ 的時限設定的很。。。喜歡測時間的同學請移步。。
下面給出標程② 。。。
方法是。。。先對整個數列排一次序。。然後使用下面這個東西保存分塊。。。
可以支持原地的二分查找。。
struct Link{ int a, b, d; Link(){} Link(int _a, int _b, int _d):a(_a), b(_b), d(_d){}; void Split(); int Stat(); } L[N]; int sz;
其中 a, b 表示這個分塊的區間,左閉右開 [ )。。
。。。
然後就可以維護了。。
這個方法常數很小。。。(不過分裂的時候似乎會 3 分。!!。)
。這個 方法在 SPOJ 可以跑 14.54 s。。。
/* .................................................................................................................................. */ const int N = 250010, M = 1010, C = 1000000000; int A[N]; char cmd; int cnt; int n, m, a, b, l, r, d; int *_a, *_b; struct Link{ int a, b, d; Link(){} Link(int _a, int _b, int _d):a(_a), b(_b), d(_d){}; void Split(); int Stat(); } L[N]; int sz; #define FIX(x) int(x < -C ? -C : x > C ? C : x) #define GPS _a = lower_bound(A + a, A + b, FIX((LL)::l - d)), _b = upper_bound(A + a, A + b, FIX((LL)::r - d)) void Link::Split(){ GPS, ::a = _a - A, ::b = _b - A; if (::a == ::b || b < ::a || ::b < a) return; int aa = max(::a, a), bb = min(::b, b); if (a < aa) L[sz++] = Link(a, aa, d); if (bb < b) L[sz++] = Link(bb, b, d); a = aa, b = bb, d += ::d; } int Link::Stat(){ GPS; return _b - _a; } void Rebuild(){ REP(i, sz) FOR(j, L[i].a, L[i].b) A[j] += L[i].d; sort(A, A+n), L[0] = Link(0, n, 0), sz = 1; } /* void Patch(){ REP(i, sz){ FOR(j, L[i].a, L[i].b) cout << A[j] + L[i].d << " "; } cout << endl; }*/ int main(){ //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); RD(n, m); REP(i, n) RD(A[i]); sort(A, A+n); L[0] = Link(0, n, 0), sz = 1; int P = sqrt(n) / 11; char cmd; REP(j, m){ scanf(" %c", &cmd); if (cmd == 'C'){ RD(l, r, d); REP_C(i, sz) L[i].Split(); if (sz > P) Rebuild(); //Patch(); } else { RD(l, r); cnt = 0; REP(i, sz) cnt += L[i].Stat(); OT(cnt); } } }
。如何構造一個數據可以殺掉所有 std 呢。。
(、這個問題留給讀者思考。。)
External link :
https://www.spoj.pl/problems/PS11A/
http://acm.hit.edu.cn/judge/show.php?Proid=3054
塊狀結構秒殺一切! by WJMZBMR