（由於被 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
