###### very good data structure

# rope & pbds::tree

## rope

$\text{rope}$ 就是比較~~粗~~厲害的 $\text{string}$，內部是一棵可持久化平衡樹
大部分的操作都是 $\mathcal{O}(\log n)$
但常數偏大(我在[這](https://cses.fi/problemset/task/2072)[兩](https://cses.fi/problemset/task/2073)題吃爆 $\text{TLE}$ :crying_cat_face:)

#include <bits/stdc++.h>
#include <ext/rope> //<bits/extc++.h>
using namespace __gnu_cxx;
using namespace std;
int main()
{
    rope<int> r, a, b;
    b += 10;                 // {10}
    r += 2;                  // {2}
    r += 3;                  // {2, 3}
    a = r + r + b;           // {2, 3, 2, 3, 10}
    cout << r[0] << endl;    // {2}
    r.pop_back();            // {3}
    r.pop_front();           // empty
    r.push_back(1);          // {1}
    r.push_front(10);        // {10, 1}
    r.erase(0, 1);           // {1}
    r.insert(7, 0);          // worst case O(n) // {7, 1}
    cout << r.at(0) << endl; // 輸出 7
    r.at(0) = 100;           // {100, 1}
    r[0] = 50;               // {50, 1}
}

能做的操作和 $\text{string}$ 差不多。

rope<char> r;
crope r; // 這兩行是一樣的

[**完整函式庫**](https://www.boost.org/sgi/stl/Rope.html)

什麼時候用的到?
好像用的時機不多
通常是只有刪除和 $\text{append}$ 的時候才會用
其實也不一定要用 $\text{rope}$，但有時候用了會好寫很多

### 題目們

[**CSES - Josephus Problem II**](https://cses.fi/problemset/task/2163)
[**CSES - List Removals**](https://cses.fi/problemset/task/1749)
[**TCIRC - b082: Insert and erase**](https://judge.tcirc.tw/ShowProblem?problemid=b082)
[**NEOJ - 一天遊戲只能一小時**](https://neoj.sprout.tw/problem/25/)
[**NOI 2003 - 文本編輯器**](https://www.luogu.com.cn/problem/P4008)

### 持久化 rope

前面提到 $\text{rope}$ 是一棵可持久化平衡樹
那持久化要怎麼弄?

rope<int> *r[100000];
r[i] = new rope<int>(*r[i - 1]);

#### 題目

感謝優質題目

這題一看就是某種持久化的資結
再仔細看 $1,\ 2,\ 4$ 操作
$\text{rope}$ 都能處理
$3$ 再加上持久化就可以處理了
好耶

:::spoiler AC code (155ms)

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_cxx;
#define LL int_fast64_t
#define pLL pair<long long, long long>
#define F first
#define S second
#define pb push_back
#define rz resize
#define all(x) x.begin(), x.end()
#define CH cout << "I'm here" << endl;
#define DEBU
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#ifndef DEBUG
#define endl '\n'
#endif
const LL inv2 = 500000004;
const LL MOD = 1000000007;
const LL INF = 1e18;
void Star_Brust_Stream()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
 
void sol()
{
    LL n, m, q;
    cin >> n >> m >> q;
    vector<rope<LL> *> r(n);
    for (int i = 0; i < n; i++)
    {
        r[i] = new rope<LL>;
    }
    while (q--)
    {
        LL t;
        cin >> t;
        if (t == 1)
        {
            LL a, b;
            cin >> a >> b;
            --a;
            r[a]->pb(b);
        }
        if (t == 2)
        {
            LL a;
            cin >> a;
            --a;
            r[a]->pop_back();
        }
        if (t == 3)
        {
            LL a, b;
            cin >> a >> b;
            --a;
            --b;
            r[a] = new rope<LL>(*r[b]);
        }
        if (t == 4)
        {
            LL a, b;
            cin >> a >> b;
            --a;
            --b;
            cout << r[a]->at(b) << endl;
        }
    }
}
int main()
{
    Star_Brust_Stream();
    LL t = 1;
    // cin >> t;
    while (t--)
    {
        sol();
    }
#ifdef DEBUG
    system("pause");
#endif
    return 0;
}

:::

### 題目

[**E - Notebook**](https://atcoder.jp/contests/abc273/tasks/abc273_e)

## pbds::tree

其實就拿來當 $\text{set/multiset}$ 用

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
/*
#include <bits/extc++.h>
*/
using namespace __gnu_pbds;
using namespace std;
int main()
{
    tree<int, null_type, less<int>, rb_tree_tag, \
         tree_order_statistics_node_update> tr;
    int a = 1;
    int k;
    cin >> k;
    tr.insert(a);
    tr.erase(a);
    tr.lower_bound(a);
    tr.find_by_order(k); // an iterator of the (k+1)th smallest element
    tr.order_of_key(k);  // the number of elements are less than k
}

操作的時間複雜度為 $O(\log n)$
如果想要當 $\text{multiset}$ 來用的話要把 $\text{less}$ 改成 $\text{less_equal}$
但 $\text{lower_bound}$ 會變成 $\text{upper_bound}$
$\text{erase}$ 操作只能用 $\text{iterator (I don't know why)}$

### 逆序數對

**「CDQ? BIT?
why not pbds::tree?」
--- 魯迅**

for (int i = 0; i < n; i++)
{
    ans += tr.size() - tr.order_of_key(v[i] + 1);
    tr.insert(v[i]);
}

### 更多題目

[**CSES - Josephus Problem II**](https://cses.fi/problemset/task/2163) (again)
[**CSES - Nested Ranges Count**](https://cses.fi/problemset/task/2169)
[**CSES - Salary Queries**](https://cses.fi/problemset/task/2169)
[**CSES - Sliding Median**](https://cses.fi/problemset/task/1076)
[**TIOJ - A.逆序數對**](https://tioj.ck.tp.edu.tw/problems/1080)