某島

… : "…アッカリ~ン . .. . " .. .
August 27, 2011

SPOJ 9392. Play With Sequence

(由於被 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 操作將某個區間的所有樹伸展到某個容易訪問的子樹位置。

那麼,接下來?。。。、打標記?

如圖所示。。(。。。)

這個操作會破壞鍵值。。。也是因為同樣的原因,線段樹 塊狀鏈表 都不奏效。。

。。。這是這個問題的難點所在。。。下面對 鍵值處在某個範圍的數整題加上某個數 這個操作進行進一步的觀察。。

可以得到下面兩個性質。

  1. 選出的序列,在操作的前後相對順序不發生改變。
  2. 在任意時刻,如果兩個數額鍵值相同,那麼今後,它們會一直作為一個整體存在。

….

為了防止有人用第二個性質亂搞。。題目 Ai 值的範圍要儘可能的大。。

第一個性質。。提示我們用 塊狀結構 來解決掉這個問題。。。

標程使用的是 伸展森林 … 字面上的意思,也就是維護一組伸展樹,每次對每棵伸展樹伸展出選定的區間,然後打上標記分離出來(喀嚓!)。。

等到伸展樹的棵樹達到 某個值 (一般設定為 sqrt(n) 然後考慮到 常數,再減小一點。。不判斷塊樹而是每隔一段時間重構一次。。大概用一個對數函數。。。)
的時候。。推掉重練。。(這裡注意一個地方。實際中重構的話用 std::sort 比用堆然後分塊合併要快。。)

這裡的標記只要記錄在根節點即可,不需要下放。。
(一個容易出錯的地方是,雖然我保證中間的數據也不會爆 int32,但是在處理 delta 的時候可能會爆。。所以如果想保持主要的結構都使用 int32 的話這裡要特判一下。。)

一個嚴重的問題就此產生了:

似乎一眼看上去,splay 的顆樹會呈指數爆炸?!。。。

嗯嗯。。這個問題。。我還。。不知道怎麼證明。(什麼!)
。。但是看上去似乎(對於隨機生成的數據)這種情況不會出現 。。

下面我試圖說一點我的想法。。

定義
/theta = sqrt Sigma i, j sqr(Ai – Aj)
為一個數集的 離散程度。(注意不能直接使用方差。。吧。。)

(於是,重新考察前面的性質2,雖然說要中間恰好相等可能不太會出現。
但是有跡象表明,操作過後數列可能在某幾個位置集中。。而這就相當於降低了 N 的規模)。。

對於某一次操作,會發生下面兩種事情之一

  1. 數列的離散程度下降,同時,塊數增多。
  2. 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