Untitled - HackMD

真．資料結構EX

成為十萬序列大師

wangyenjen

WHOAMI

喵

JAW

Johnchen902：字串、噁心模擬題、小品、DP、慘題
nonamefour0210：數學、DP、吉祥物！
我：打雜、資結、dp優化、幾何

前備知識

線段樹和BIT
線段樹和BIT
線段樹和BIT

CONTENT

穿越時空的線段樹
切塊、Mo's、分case
擁抱分治，向資結說不

遺珠之憾…

O(1) 求斐波那契數列
把PI、e存在月球上

小複習

線段樹

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

區間開根號

問題：
給你

N

個數字

a_{i} (1 \leq i \leq N)

，跟

Q

個操作，操作有兩種：

query x y: 查詢序列
$a$ 在區間
$[x, y]$ 的和。
sqrt x y: 把
$a_{x}, a_{x + 1}, . . ., a_{y}$ 的值個別開根號後取高斯。

區間開根號

問題：
給你

N

個數字

a_{i} (1 \leq i \leq N)

，跟

Q

個操作，操作有兩種：

query x y: 查詢序列
$a$ 在區間
$[x, y]$ 的和。
sqrt x y: 把
$a_{x}, a_{x + 1}, . . ., a_{y}$ 的值個別開根號後取高斯。

1 \leq N, Q \leq 10^{5}

1 \leq a_{i} \leq 10^{9}

穿越時空的線段樹

先來看看一個問題：
給定一張

N

個點的無向圖，一開始圖上有

M

條邊。
現在有

Q

個操作，每個操作會是以下兩種中的一種：

增加一條連接著編號
$A_{i}$ 與編號
$B_{i}$ 的邊。
刪除一條連接著編號
$A_{i}$ 與編號
$B_{i}$ 的邊（保證這條邊是存在的）。

每次操作完後請輸出當前的連通塊數量。

1 \leq N, Q \leq 10^{5}

1 \leq A_{i}, B_{i} \leq N

當發現一個問題太難的時候，我們往往可以從較簡單的版本著手，試著找出解決難題的方向。

把兩種操作分開來看看吧！

easy version 1.

給定一張

N

個點的無向圖，一開始圖上有

M

條邊。
現在有

Q

個操作，每個操作會是以下形式：

增加一條連接著編號
$A_{i}$ 與編號
$B_{i}$ 的邊。

每次操作完後請輸出當前的連通塊數量。

1 \leq N, Q \leq 10^{5}

1 \leq A_{i}, B_{i} \leq N

並查集(Disjoint Set)的標準應用

並查集可以…

合併兩個連通塊
詢問每個連通塊有多少點
詢問當前有多少連通塊
etc…

easy version 2.

給定一張

N

個點的無向圖，一開始圖上有

M

條邊。
現在有

Q

個操作，每個操作會是以下形式：

刪除一條連接著編號
$A_{i}$ 與編號
$B_{i}$ 的邊（保證這條邊是存在的）。

每次操作完後請輸出當前的連通塊數量。

1 \leq N, Q \leq 10^{5}

1 \leq A_{i}, B_{i} \leq N

似乎沒有現成的資料結構可以維護（？

當題目沒要求強制在線時，往往有簡單的離線做法！

時光倒流

把所有操作先存起來

對於最終的Graph，如果把操作到回去做？

變成只有加邊的問題了！

回到原問題

給定一張

N

個點的無向圖，一開始圖上有

M

條邊。
現在有

Q

個操作，每個操作會是以下兩種中的一種：

增加一條連接著編號
$A_{i}$ 與編號
$B_{i}$ 的邊。
刪除一條連接著編號
$A_{i}$ 與編號
$B_{i}$ 的邊（保證這條邊是存在的）。

每次操作完後請輸出當前的連通塊數量。

1 \leq N, Q \leq 10^{5}

1 \leq A_{i}, B_{i} \leq N

還是不會做

時間線段樹！

時間線段樹，顧名思義就是將線段樹的每個節點當成對應的時間區間，並存放著該時間區間對應的所有>
操作，即在這邊操作是有時效性的。

使用上會把詢問與具有時效性的操作一起當成時間點，將這些時間點所形成的區間視為線段樹上的節點。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →





























void insert_event(vector<Event> tr[], int idx,
        int lb, int rb, int ql, int qr, Event e) {
// tr[] := 時間線段樹存事件所使用的陣列
// idx := 當前在時間線段樹上哪個節點
// 當前節點對應到的時間區間為 [lb, rb]
// 當前要在時間區間 [ql, qr] 插入一個事件e

    // 當前區間 [lb, rb] 完全被 事件區間 [ql, qr] 包含
    if (ql <= lb && rb <= qr) {
        // 插入事件至時間線段樹對應的節點
        tr[idx].push_back(e);
        return;
    }
    int m = (lb + rb) / 2;

    // 事件區間 [ql, qr] 完全位於 mid 左邊
    if (qr <= mid)
        insert_event(tr, idx*2, lb, mid, ql, qr, e);

    // 事件區間  [ql, qr] 完全位於 mid 右邊
    else if (mid < ql)
        insert_event(tr, idx *2+1, mid+1, rb, ql, qr, e);

    // 事件區間  [ql, qr] 跨過 mid 這個時間點
    else {
        insert_event(tr, idx*2, lb, mid, ql, qr, e);
        insert_event(tr, idx*2+1, mid+1, rb, ql, qr, e);
    }
}



















void traversal(vector<Event> tr[], int idx, int lb, int rb)
{
    int cnt = 0; // 用來記錄在這一層做了多少事情
    for (auto e : tr[idx])
        if (do_things(e))
            cnt++;
    if (lb == rb) // 記錄在這個時間點的答案
    else {
        int mid = (lb + rb) / 2;

        // 遍歷時間線段樹的左子樹
        traversal(tr, idx * 2, lb, mid);

        // 遍歷時間線段樹的右子樹
        traversal(tr, idx * 2 + 1, mid + 1, rb);
    }
    while (cnt--)
        undo(); // 將所做的事情進行undo操作
}

如果對於每條邊，我們考慮它存活的時間…

時間線段樹的undo?

並查集again

支援undo操作的並查集





int cc_cnt; // 當前連通塊數量
int sz[MAX_N]; // 用來記錄每個連通塊大小
int par[MAX_N];　// 用來記錄每個節點所指向的父節點
stack<pair<int*, int> > stk_sz;　// 用來記錄每次操作前的sz
stack<pair<int*, int> > stk_par; // 用來記錄每次操作前的par

void init(int n) {
    while (!stk_sz.empty())
        stk_sz.pop();
    while (!stk_par.empty())
        stk_par.pop();
    cc_cnt = n;
    for (int i = 0; i < n; i++) {
        par[i] = i;
        sz[i] = 1;
    }
}

不能路徑壓縮！





int find(int x) { // 找根
    while (x != par[x])
        x = par[x];
    return x;
}

不能路經壓縮，所以一定要啟發式合併！




















bool merge(int x, int y) {
    x = find(x);
    y = find(y);
    if(x == y)
        return 0;

    if (sz[x] < sz[y]) // 啟發式合併
        swap(x , y);

    // 記錄操作前的sz
    stk_sz.push(make_pair(&sz[x], sz[x]));

    //　記錄操作前的par
    stk_par.push(make_pair(&par[y], par[y]));

    cc_cnt--;
    sz[x] += sz[y];
    par[y] = x;
    return 1;
}









void undo() {
    pair<int*, int> p_par = stk_par.back();
    pair<int*, int> p_sz = stk_sz.back();
    stk_par.pop();
    stk_sz.pop();
    *p_par.first = p_par.second; // 將par回復成操作前的par
    *p_sz.first = p_sz.second; // 將sz回復成操作前的sz
    cc_cnt++;
}

至此，對於可undo的並查集，每次merge操作的時間複雜度為

O (\log N)

，每次undo操作為

O (1)

單次插入事件
$O (\log (M + Q))$
merge操作
$O (\log N)$
undo操作
$O (1)$
traversal
$O ((M + Q))$

總時間複雜度為

O ((M + Q) \log N + (M + Q) \log (M + Q))

總結

總結一下，通常題目只要滿足以下兩個條件便可以考慮使用時間線段樹了：

操作具有時效性
搭配的資料結構支援undo操作（一般的資料結構幾乎都可以支援）

小習題 - BZOJ 4025 二分圖

給定一張

n

個點的圖，有

m

條邊與

T

個時間點，每條邊只存在於

(s t, e d]

這些時間點，求每個時間點時這張圖是否為二分圖。

$1 \leq n \leq 10^{5}$
$1 \leq m \leq 2 \times 10^{5}$
$1 \leq T \leq 10^{5}$
$0 \leq s t \leq e d \leq T$

切塊

先來看個問題吧！

給你一個長度

N

的序列

A [0], A [1], . . ., A [N - 1]

緊接著

Q

筆詢問，每筆詢問是一個數對

x, y

請你回答

m i n

{

A [x], A [x + 1], . . ., A [y]

}

A = {5, 2, 8, 1, 7}
Query = {(0, 2), (1, 4), (2, 2)}
答案：2 1 8




int ans = A[x];

for (int i = x + 1; i <= y; i++)
    ans = min(ans, A[i]);

時間複雜度

O (Q N)

特性：

m i n (a, b, c) = m i n (a, m i n (b, c))

可以對一部分數字先求最小值，再從每個部份的最小值中取最小的！

一部分？
每連續

k

個分一組，先把每組的最小值算好並存下來
對於詢問
Imgur

綠色每塊都先算好了，時間花費是塊數：最多

\frac{N}{k}

紅色部份每個數字跑一遍，時間花費是一塊大小：最多

2 k

每次詢問

O (\frac{N}{k} + k)

取個好的

k

？

算幾不等式：

\frac{N}{k} + k \leq 2 \times s q r t (\frac{N}{k} * k) = 2 \times s q r t (N)

在

\frac{N}{k} = k

也就是

k = s q r t (N)

時最小

所以取

k

為

s q r t (N)

就有了每次詢問

O (s q r t (N))

的解法了

分塊的好處

1.大部分的區間詢問問題都需要用某種平衡二元搜尋樹來維護，若能用set,map,或是簡單的線段樹維護那還好，但如果性質很難維護或是要用到複雜的資料結構，寫起來會比較久也比較難debug。

2.分塊時跟陣列一樣只有一層，比較好想我們要維護什麼

3.code易懂

IOI 2011 Elephants

有

N

隻可愛的大象在舞台上排成一條線跳舞。
接下來有

M

次操作，每次操作可以把左邊數來第

a

隻大象移動到數線上的位置

b

，每次操作完後請輸出最少需要幾張照片才可以拍到所有的大象。
（每張照片可以cover一個長度為

L

的區間）

1 \leq N, M \leq 150000, 0 \leq b \leq 10^{9}

如果大象不會移動位置？

Greedy！

將大象序列切成
$K$ 塊吧！

對於每一隻大象我們可以紀錄如果從他開始，我們要幾台相機才能蓋滿該塊的所有大象，且最後會蓋到哪個位置。

操作

對某一塊加一隻大象，對某一塊刪除一隻大象

如果某塊大象太多？

令一塊大小為

X

，如此修改時間為

O (X \log X)

，查詢時間便是

O (K \log X)

，
但悲劇的是每次操作後每一塊大小並不是固定的，
在經過

Q

次操作後，我們也許會獲得

X = \frac{N}{K} + Q \leq N

打掉重練！

當有一塊過大時（可以定為

\frac{2 N}{K}

），我們便整個打掉重新分塊

我們令

K = \sqrt{N}

建表時間為

O (N \log N)

，
每次修改與查詢的時間複雜度為

O (\sqrt{N} \log \sqrt{N})

重建表總時間為

O (\frac{Q}{\sqrt{N}} \times N \log N) = O (Q \sqrt{N} \log N)

mo's

經典問題 - 區間眾數

給定一個序列

S_{1}, \dots, S_{N}

，接著有

Q

組詢問，
每次詢問

[L_{i}, R_{i}]

出現最多的數字出現幾次。

(1 \leq N, Q \leq 10^{5})

a p p [x] :=

數字

x

出現幾次

c n t [y] :=

有

c n t [y]

個數字出現過

y

次

c n t [0]

初始為

N

。













void add(int x) {                                   
    int now = ++app[x];
    cnt[now - 1]--;
    cnt[now]++;
    curMax = max(curMax, now);
}
void sub(int x) {
    int now = --app[x];
    cnt[now + 1]--;
    cnt[now]++;
    if (!cnt[curMax])
        curMax--;
}



















for (int i = 1, curL = 1, curR = 0; i <= Q; i++) {
    while (curR < qry[i].R) {
        curR++;
        add(S[curR]);
    }
    while (curR > qry[i].R) {
        sub(S[curR]);
        curR--;
    }
    while (curL > qry[i].L) {
        curL--;
        add(S[curL]);
    }
    while (curL < qry[i].L) {
        sub(S[curL]);
        curL++;
    }
    answer[qry[i].qid] = curMax;
}

對於左界

左界屬於同一塊的詢問，每次都不會移動超過

\frac{N}{K}

次；
而左界屬於不同塊的操作，移動次數加起來也不超過

N

次。
所以左界移動的時間複雜度為

O (\frac{N Q}{K})

。

對於右界

相同塊：因為

R_{i}

是遞增的，所以對於同一塊最多花費

O (N)

的時間。
對於不同塊因為交界最多只有

O (K)

次，每次最多也花費

O (N)

，故維護右界的時間複雜度為

O (K N)

。

取

K = \sqrt{N}

，於是我們得到一個時間複雜度為

O (\frac{N Q}{K} + K N) = O (Q \sqrt{N} + N \sqrt{N})

的做法

分case

遺珠QQ

擁抱分治，向資結說不

WHY 離線?

在線作法不好做
在線太久太滿太胖

整體二分

METEOR

長度

M

的序列，一開始都是

0

N

個人瓜分這個序列，每個人有他的目標

g_{i}

K

次操作，每次都是序列某個區間全部加上

x_{i} > 0

問每個人什麼時候達到目標
也就是擁有的元素加起來

\geq g_{i}

每個人二分搜何時達到目標
用可持久線段樹維護每個操作做完的序列長相

時間

O ((M + N) \log K \log M)

空間

O (K \log M)

MLE
mempry limit: 64 mb

開

K

棵線段樹真的太虧了
看來不能每個人各自二分搜了
















typedef vector< int > VI;
void totBS( int s , int e , VI nation ) {
  if(s > e || nation.size() == 0)
    return ;
  int mid = (s + e) / 2;

  do_things( s , mid );

  VI ok, notok;
  split( mid , nation , ok , notok );

  undo_things( s , mid );

  totBS( s , mid-1 , ok );
  totBS( mid+1 , e , notok );
}

看那些人可以在 mid 之前達到目標
可以的丟去二分搜

[s, m i d - 1]

不行的丟去二分搜

[m i d + 1, e]

把 [s,mid] 的操作作用一番
BIT 維護之








void do_things( int s , int mid ) {
  for( int i = s ; i <= mid ; i++ ) {
    int nl = in[ i ].l , nr = in[ i ].r;
    ll nnu = in[ i ].nu;
    bit.upd(nl, nnu);
    bit.upd(nr+1, -nnu);
  }
}

看那些人在 mid 前可以被滿足
並且更新他們的目標 (把 [s,mid] 對他們貢獻扣掉)





















void split( int mid , VI& nation , VI& ok , VI& notok ) {
  for( int nat : nation ) {
    tem[nat] = 0ll;
    for( int it : satel[ nat ] ) {
      tem[nat] += bit.qry(it);
      if(tem[nat] >= need[nat])
        break;
    }
    if(tem[nat] >= need[nat]) {
      ok.push_back(nat);
      if(ans[nat] > 0) ans[nat] = min(ans[nat], mid);
      else ans[nat] = mid;
    }
    else {
      need[nat] -= tem[nat];
      notok.push_back(nat);
    }
  }
  // 真的把 nation 佔的記憶體釋放掉
  VI ().swap( nation );
}

把 BIT 還原
還給子孫乾淨的 BIT








void undo_things( int s , int mid ) {
  for(int i = s; i <= mid; i++) {
    int nl = in[i].l, nr = in[i].r;
    ll nnu = in[i].nu;
    bit.upd(nl, -nnu);
    bit.upd(nr+1, nnu);
  }
}

時間：

O ((N + M + K) \log M \log K)

空間：

O (M)

(這寫法空間真的是線性嗎^^)

MLE

AC
其實這作法好好寫可以不用 BIT
時間少一個 O(logM)
空間也是好好線性

操作分治

在線好難做
把操作們整理成方便處理的順序
變得好做

MACHINE WORKS

給你

N, t_{i}, g_{i}, r_{i}, p_{i}

1 \leq N \leq 10^{5}

t_{i}

遞增
計算下列 DP 式 :

d p [i] = m a x_{j < i}

{

g_{j} \times t_{i} + (r_{j} - p_{j} + d p [j] - (t_{j} + 1) \times g_{j})

}

阿不就斜率優化 DP
deque 做過去就沒啦

可是

g_{j}

沒有單調性
慘

用平衡樹維護下凸包
算好一個

d p [i]

後
把

y = g_{i} \times x + (r_{j} - p_{j} + d p [i] - (t_{j} + 1) \times g_{j})

塞進去
把附近斜率不必要的線拔掉
一堆邊界條件好難寫

好希望
$g_{j}$ 有單調性阿~~

想想分治
先把

d p [1 \dots \frac{N}{2}]

做完
按照

g_{j}

排好
那就可以輕鬆做

d p [\frac{N}{2} + 1 \dots N]

了耶

所以可以得到長這樣的作法








void solve( int l , int r ) {
  if( l == r ) return ;
  int mid = ( l + r ) / 2;
  solve( l , mid );
  // 把 [l, mid] 整理好
  // 算 [l, mid] 對 [mid+1, r] 答案的影響
  solve( mid+1 , r );
}

整理好就只是
先把線做出來，排序好












vector< Line > lns , stk;
lns.clear();
for( int i = l ; i <= mid ; i++ )
  if( in[ i ].dp >= in[ i ].P ) {
    Ln l1{
      in[ i ].G ,
      in[ i ].dp-in[ i ].P+in[ i ].R
      -( in[ i ].D+1ll )*in[ i ].G
    };
    lns.push_back( l1 );
  }
sort( lns.begin() , lns.end() );

然後做出下凸包，把不必要的線拿走













stk.clear();
for( Ln l1 : lns ) {
  while( stk.size()
      && stk.back().m == l1.m
      && stk.back().b < l1.b )
    stk.pop_back();
  if( stk.size() && stk.back().m == l1.m ) continue ;
  while( stk.size() >= 2
      && !ok( stk[ stk.size() - 2 ] ,
              stk[ stk.size() - 1 ] , l1 ) )
    stk.pop_back();
  stk.push_back( l1 );
}

不必要的線？

像圖中紅色的線就是爛線
Imgur

接下來就是要去更新

[m i d + 1, r]

的

d p

值了









int j = 0;
for( int i = mid+1 ; i <= r ; i++ ) {
  ll x = in[ i ].D;
  while( j + 1 < (int)stk.size()
      && stk[ j ]( x ) < stk[ j+1 ]( x ) )
    j++;
  in[ i ].dp = max( in[ i ].dp , stk[ j ]( x ) );
}
dq( mid + 1 , r );

這裡只處理

[l, m i d]

對

d p [i]

的影響

[m i d + 1, i - 1]

的影響透過

d q (m i d + 1, r)

遞迴搞定

好好 merge sort 線的斜率的話
時間 :

O (N \log N)

矩形面積和

在一個二維平面上有

n

個點，大家都知道，任兩個點可以形成一個矩形，而現在要你求出所有任兩點形成的矩形(共

n * (n - 1) / 2

個矩形)面積和。

2 \leq n \leq 100000

0 \leq x_{i}, y_{i} \leq 10000

ADA Farm

在ADA農場中有

N

隻貓咪，第

i

貓咪位於

(x_{i}, y_{i})

。

貓咪如果上下左右移動的話，會耗費

1

單位時間。
貓咪如果走日字形移動的話，會耗費

2

單位時間。

定義

D (i, j)

代表第

j

隻貓咪走到第

i

隻貓咪所在位置的最小花費時間

對於每隻貓咪

i

，請求出

D (i, 1) + D (i, 2) + \dots + D (i, N)





int calc(int dx, int dy) {
  if (dx < dy) swap(dx, dy);
  if (dx >= 2 * dy) return dx;
  else return 2 * (dx + dy + 1) / 3;
}

真．資料結構EX

成為十萬序列大師

wangyenjen

WHOAMI

JAW

前備知識

小複習

線段樹

區間開根號

區間開根號

穿越時空的線段樹

easy version 1.

並查集(Disjoint Set)的標準應用

easy version 2.

時光倒流

回到原問題

還是不會做

時間線段樹！

時間線段樹的undo?

並查集again

支援undo操作的並查集

總結

小習題 - BZOJ 4025 二分圖

切塊

先來看個問題吧！

分塊的好處

IOI 2011 Elephants

如果大象不會移動位置？

將大象序列切成K塊吧！

操作

如果某塊大象太多？

打掉重練！

mo's

經典問題 - 區間眾數

對於左界

對於右界

分case

擁抱分治，向資結說不

WHY 離線?

整體二分

METEOR

操作分治

MACHINE WORKS

好希望 gj 有單調性阿~~

不必要的線？

矩形面積和

ADA Farm

Q&A

將大象序列切成
$K$ 塊吧！

好希望
$g_{j}$ 有單調性阿~~