權(quán)值數(shù)據(jù)結(jié)構(gòu)水各種題

前置知識(shí)

樹狀數(shù)組, 線段樹, 分塊... 反正任何你能想到的能求和的數(shù)據(jù)結(jié)構(gòu)就行, 只要數(shù)據(jù)結(jié)構(gòu)能單點(diǎn)加求區(qū)間和, 就能當(dāng)權(quán)值數(shù)據(jù)結(jié)構(gòu).

給樹狀數(shù)組和線段樹的鏈接吧, 分塊現(xiàn)在沒有, 以后大概率也沒有 (莫隊(duì)?wèi)?yīng)該會(huì)有).

樹狀數(shù)組及其各種擴(kuò)展

線段樹, 算法競賽掌管區(qū)間的神

還有如果值域過大需要離散化或用動(dòng)態(tài)開點(diǎn)線段樹, 不過動(dòng)態(tài)開點(diǎn)線段樹等Defad下次介紹持久化線段樹和主席樹的時(shí)候再說.

C語言離散化

什么是權(quán)值, 以及什么是權(quán)值數(shù)據(jù)結(jié)構(gòu)

Defad對于權(quán)值的理解是一個(gè)值出現(xiàn)的次數(shù) (和圖論的邊權(quán)不一樣), 就是說一個(gè)值出現(xiàn)了幾次.

權(quán)值數(shù)據(jù)結(jié)構(gòu)就是維護(hù)權(quán)值的數(shù)據(jù)結(jié)構(gòu).

一個(gè)題簡單理解權(quán)值數(shù)據(jù)結(jié)構(gòu)

堆板子

VJudge LuoGu

插入就是插入的值的權(quán)值 \(+ 1\), 刪除就是在第一個(gè)有權(quán)值的點(diǎn) \(- 1\), 查詢就是輸出第一個(gè)有權(quán)值的點(diǎn).

這里我們有一個(gè)巨大的優(yōu)化, 線段樹上二分 (Defad用線段樹舉例但同學(xué)們可以用任何的可以單點(diǎn)加求區(qū)間和的數(shù)據(jù)結(jié)構(gòu), 不過線段樹上二分可以 \(O(\log N)\) (改變不了常數(shù)巨大的事實(shí)), 但別的數(shù)據(jù)結(jié)構(gòu)都是 \(O(k \log N)\) 其中 \(k\) 是單次查詢復(fù)雜度).

線段樹上二分其實(shí)很簡單, 左邊滿足條件就查左邊, 否則查右邊, 給一個(gè)查詢 \(k\) 的下標(biāo)的板子.

int kth(int x, int l, int r, int k) {
  if (l == r) { // 遞歸到葉子了
    return l; // l 和 r 相等, 隨便返回一個(gè)就是下標(biāo)
  } else {
    int m(l + r >> 1);
    // 權(quán)值數(shù)據(jù)結(jié)構(gòu)一般不用區(qū)間修改, 所以沒有 pushdown
    if (k <= val[x << 1]) // k 比左邊的值小
      return kth(x << 1, l, m, k); // 查左邊
    else if (k <= val[x]) // k 比當(dāng)前點(diǎn)值小
      return kth(x << 1 | 1, m + 1, r, k - val[x << 1]); // 扣掉左邊再查右邊
    else // 這個(gè)其實(shí)可以不用, 但Defad習(xí)慣寫
      return -1;
  }
}

所以說這個(gè)堆板子就比較容易寫了.

因?yàn)镈efad懶得寫離散化, 這里只給權(quán)值加, 查詢第 \(k\) 大, 刪第 \(k\) 大, 調(diào)用的時(shí)候在 \(k\) 的參數(shù)位置寫 \(1\) 就好了 (Tips: 離散化是離線的, 動(dòng)態(tài)開點(diǎn)可以在線).

void chg(int x, int l, int r, int I, int k) { // 這里的 k 是加的權(quán)值, 一般是 1
  if (l == r) { // 單點(diǎn)加
    val[x] += k;
  } else {
    int m(l + r >> 1);
    if (I <= m)
      chg(x << 1, l, m, I, k);
    else
      chg(x << 1 | 1, m + 1, r, I, k);
    val[x] = val[x << 1] + val[x << 1 | 1];
  }
}

int kth(int x, int l, int r, int k) {
  if (l == r) {
    return l;
  } else {
    int m(l + r >> 1);
    if (k <= val[x << 1])
      return kth(x << 1, l, m, k);
    else if (k <= val[x])
      return kth(x << 1 | 1, m + 1, r, k - val[x << 1]);
    else
      return -1;
  }
}

void del(int x, int l, int r, int k) {
  if (l == r) {
    val[x] -= 1;
  } else {
    int m(l + r >> 1);
    if (k <= val[x << 1])
      del(x << 1, l, m, k);
    else
      del(x << 1 | 1, m + 1, r, k - val[x << 1]);
    val[x] = val[x << 1] + val[x << 1 | 1];
  }
}

VJudge LuoGu

作為指針神教現(xiàn)任教主, 這題是Defad當(dāng)年用指針線段樹過的.

說一下怎么統(tǒng)計(jì)答案, 遍歷數(shù)組, 加上當(dāng)前值后統(tǒng)計(jì)i - qry(1, 1, N, 1, a[i]) (這里的qry是求區(qū)間和), 用于統(tǒng)計(jì)的變量記得開long long.

平衡樹

VJudge LuoGu

剛才我們都打過堆板子了, 平衡樹其實(shí)也可以用權(quán)值線段樹水過去.

應(yīng)該不用Defad再說怎么做每個(gè)操作了吧?

稍微放個(gè)簡單題, 最大 \(M\) 寬區(qū)間和

VJudge LuoGu

亮度就是權(quán)值, 這個(gè)題好像沒法離散化, 因?yàn)樾枰笏袑挒?\(M\) 的區(qū)間的和的最值.

郁悶的出納員

VJudge LuoGu

Defad感覺這題細(xì)節(jié)挺多的, 就說一個(gè)最重要的, 權(quán)值平移操作.

權(quán)值線段樹的權(quán)值不太方便平移, 所以可以用一個(gè)輔助變量 \(level\) 的加減實(shí)現(xiàn)平移操作, 此時(shí)的kth的答案應(yīng)該是 \(l + level\).