「学习总结」数据结构

📅 Last Updated: 2020-12-20

📊 Word Count: 1123

⏱️ Estimated Reading Time: 7 minutes

📄 PDF 📝 Source

~~真的好爱 Splay!~~

好像只有 LCT 中才有必要写 Splay 吧…… 其实 非旋 Treap 真的是又短，有小，又快……

数据结构

平衡树

Splay

删除结点时，不是 Splay 到根然后合并两边的子树，而是将待删除的结点前驱 Splay 到根节点，后继 Splay 到根节点右儿子，那么待删除的结点就在 ls(rs(rt)) 上。这样可以删除集合内一个区间的元素，也方便后面维护序列。

void erase(int v){
    PII pre = _pred(v), nxt = _nxtd(v);
    splay(pre.se); splay(nxt.se, rt);
    int &target = ls(rs(rt)); cnt[target] --; si[target]--;
    if(!cnt[target]) target = 0;
    maintain(rs(rt)); maintain(ls(rt));  maintain(rt);
}

如果空间要求较严格，可以考虑手写一个小的内存管理函数，删除时回收内存，新增元素时优先使用之前删除的结点内存。

stack<int> Mem;
int make(){
    int t; int o = (Mem.empty() ? ++tot : (t = Mem.top(), Mem.pop(), t)); 
    ch[o][1] = ch[o][0] = v[o] = fa[o] = 0;
    si[o] = 1;
    return o;
}
void recycle(int o = -1) { if(o == -1) o = rt; if(!o) return ; Mem.push(o); recycle(ls(o)); recycle(rs(o)); }

如果需要开多棵 Splay，可以考虑只封装每棵 Splay 的根节点，对于结点内存的申请和释放统一管理
一个很方便的调试 Splay 的函数：

void dfs(int o = -1, int indent = 0){
    if(o == -1) o = rt;
    if(!o)  { cerr << string(indent, ' ') << "# null" << endl; return ; }
    push(o);
    assert(!rs(o) || fa[rs(o)] == o); dfs(rs(o), indent + 10);
    cerr << string(indent, ' ') << "# v=" << val[o] << " ans=" << v[o].ans << endl;
    assert(!ls(o) || fa[ls(o)] == o); dfs(ls(o), indent + 10);
}

建立哨兵结点作为整个 Splay 的最小最大值是一个通用技巧，删除操作依赖于前驱和后继结点，所以哨兵结点时必要的。维护序列时注意消除哨兵结点对答案的影响。

维护集合

一种动态维护集合元素，查询集合元素信息的解决方案。 - 为了优化常数和简化代码，查询前驱后继不再采用 插入-删除 式查询。查询元素排名之后直接选取前驱和后继即可。

PII _pred(int v){
    PII res = rank(rt, v);
    return select(rt, res.fi - 1);
} int pred(int v) { PII res = _pred(v); splay(res.se); return res.fi; }

rank 和 select 返回值为 pair<int, int> 其中，前一个指答案，后一个是作用结点，方便后期获取结点信息（Splay）。 int rank(int v) { PII res = rank(rt, v); if(res.se) splay(res.se); return res.fi - 1; }

struct Splay_t{
    int ch[_][2], cnt[_], si[_], v[_], fa[_], tot, rt;
    typedef pair<int, int> PII;
    #define ls(o) (ch[o][0])
    #define rs(o) (ch[o][1])
    #define maintain(o) (si[o] = si[ls(o)] + cnt[o] + si[rs(o)])
    #define get(o) (o == ch[fa[o]][1])
    int make(int f, int V){
        tot++;
        ch[tot][1] = ch[tot][0] = 0;
        si[tot] = cnt[tot] = 1;
        fa[tot] = f; v[tot] = V;
        if(f) ch[f][v[f] < V] = tot;
        return tot;
    }
    void rotate(int o){
        int p = fa[o], gp = fa[fa[o]], chk = get(o);
        ch[p][chk] = ch[o][chk^1]; fa[ch[o][chk^1]] = p;
        ch[o][chk^1] = p; fa[p] = o;
        fa[o] = gp; if(gp) ch[gp][ch[gp][1] == p] = o;
        maintain(p); maintain(o);
    }
    void splay(int o, int tgp = 0){
        for(int f = fa[o]; f = fa[o], f != tgp; rotate(o)) if(fa[f] != tgp) rotate(get(o) == get(f) ? f : o);
        if(!tgp) rt = o;
    }
    int ins(int o, int f, int V){
        if(!o) return make(f, V);
        if(v[o] == V) return (cnt[o]++, si[o]++, o);
        int r; return (r = ins(V < v[o] ? ls(o) : rs(o), o, V), maintain(o), r);
    } void ins(int v) { int t = ins(rt, 0, v); splay(t); }
    
    PII rank(int o, int V){
        if(!o) return mp(1, 0);
        if(V == v[o]) return mp(si[ls(o)] + 1, o);
        PII res; 
        if(V < v[o]) return rank(ls(o), V); 
        else return (res = rank(rs(o), V), res.fi += cnt[o] + si[ls(o)], res);
    } int rank(int v) { PII res = rank(rt, v); if(res.se) splay(res.se); return res.fi - 1; }
    
    PII select(int o, int k){
        if(k <= si[ls(o)]) return select(ls(o), k);
        else {
            if(k <= si[ls(o)] + cnt[o]) return mp(v[o], o);
            else return select(rs(o), k - cnt[o] - si[ls(o)]);
        }
    } int select(int k) { PII res = select(rt, k + 1); splay(res.se); return res.fi; }
    
    PII _pred(int v){
        PII res = rank(rt, v);
        return select(rt, res.fi - 1);
    } int pred(int v) { PII res = _pred(v); splay(res.se); return res.fi; }

    PII _nxtd(int v){
        PII res = rank(rt, v);
        return select(rt, res.fi + cnt[res.se]);
    } int nxtd(int v) { PII res = _nxtd(v); splay(res.se); return res.fi; }
    
    void erase(int v){
        PII pre = _pred(v), nxt = _nxtd(v);
        splay(pre.se); splay(nxt.se, rt);
        int &target = ls(rs(rt)); cnt[target] --; si[target]--;
        if(!cnt[target]) target = 0;
        maintain(rs(rt)); maintain(ls(rt));  maintain(rt);
    }
    Splay_t(){ tot = rt = 0; ins(INT_MAX); ins(INT_MIN); }
};

维护序列

一种支持增删元素的，线段树替代方案。本质上和线段的思想很相似，一样采用信息合并和懒标记优化复杂度，每个结点也和线段树一样存储一个子区间的信息。唯一不同的就是线段树是一种 Leafy Tree，即所有信息都只存储在叶子结点上，其结构导致无法删除和新增元素。 - 注意懒标记和线段树的定义是一样的，其作用节点的信息首先被修改。类比线段树的懒标记直接写就好了。 - 平衡树合并信息和线段树合并信息不同点在于：线段树是合并两边的信息，平衡树是先合并左子结点信息和中间结点信息再与有子结点合并，其实还是因为线段树是一种 Leafy Tree —— 和平衡树有本质区别。 - 因为 Splay 可以相对较好的控制树的形态，可以让一个子树组成任意区间，所以能够很好的维护序列。 - 核心操作：

void Make_Range(int L, int R){
    int pre = find(rt, L - 1), suf = find(rt, R + 1);
    splay(pre); splay(suf, rt);
}

const int _ = 5e5 + 10;
struct Splay_t{
    stack<int> Mem;
    #define none (-30000)
    struct data_t{
        int sum, per, suf, ans;
        data_t(){ per = suf = ans = -1e9; sum = 0; };
        data_t(int V) { sum = per = suf = ans = V; }
        void ret(int v, int len){
            if(v <= 0) suf = per = ans = v, sum = v * len; // changed `sum = v` to `sum = v * len`.
            else       sum = suf = per = ans = v * len;
        }
        void rev() { swap(per, suf); }
        data_t operator + (const data_t & B) {
            data_t A = *this, res;
            res.sum = A.sum + B.sum;
            res.per = max(A.per, A.sum + B.per);
            res.suf = max(A.suf + B.sum, B.suf);
            res.ans = max(max(A.ans, B.ans), A.suf + B.per);
            return res;
        }
    };

    int ch[_][2], fa[_], si[_], rt, tot; data_t v[_];
    short val[_];
    bool tag_rev[_]; short tag_ret[_];
    #define ls(o) (ch[o][0])
    #define rs(o) (ch[o][1])
    #define maintain(o) (si[o] = si[ls(o)] + si[rs(o)] + 1, v[o] = v[ls(o)] + data_t(val[o]) + v[rs(o)])
    #define get(o) (ch[fa[o]][1] == o)
    int make(){
        if(!Mem.empty()){
            int o = Mem.top(); Mem.pop();
            tag_ret[o] = none;
            tag_rev[o] = false;
            ch[o][1] = ch[o][0] = si[o] = val[o] = fa[o] = 0;
            v[o] = data_t();
            return o;
        } else {
            tot++;
            tag_ret[tot] = none;
            tag_rev[tot] = false;
            ch[tot][1] = ch[tot][0] = si[tot] = val[tot] = fa[tot] = 0;
            v[tot] = data_t();
            return tot;
        }
        
    }
    void recycle(int o){ if(!o) return ; Mem.push(o); recycle(ls(o)); recycle(rs(o)); }

    Splay_t() { rt = tot = 0; }
    void tar_rev(int o){
        v[o].rev();
        swap(ls(o), rs(o));
        tag_rev[o] ^= 1;
    }
    void tar_ret(int o, int V){
        v[o].ret(V, si[o]);
        val[o] = V;
        tag_ret[o] = V;
    }
    void push(int o){
        if(tag_ret[o] != none){
            if(ls(o)) tar_ret(ls(o), tag_ret[o]);
            if(rs(o)) tar_ret(rs(o), tag_ret[o]);
            tag_ret[o] = none;
        }
        if(tag_rev[o]){
            if(ls(o))tar_rev(ls(o));
            if(rs(o))tar_rev(rs(o));
            tag_rev[o] = 0;
        }
    }
    void rotate(int o){
        int p = fa[o], gp = fa[fa[o]], chk = get(o);
        ch[p][chk] = ch[o][chk ^ 1]; fa[ch[o][chk ^ 1]] = p;
        ch[o][chk ^ 1] = p; fa[p] = o;
        fa[o] = gp; if(gp) ch[gp][ch[gp][1] == p] = o;
        maintain(p); maintain(o);
    }
    void splay(int o, int tgp = 0){
        for(int f = fa[o]; f = fa[o], f != tgp; rotate(o)){
            push(f); push(o);
            if(fa[f] != tgp) rotate(get(o) == get(f) ? f : o);
        }
        if(!tgp) rt = o; // changed `rt = tgp`  to `rt = o`.
    }
    void build_sub(int &o, int f, int L, int R, int *A){
        if(L > R) return ;
        int mid = (L + R) >> 1;
        o = make(); fa[o] = f; val[o] = A[mid]; v[o] = data_t(A[mid]); si[o] = 1;
        if(L == R) return ;
        if(L <= mid - 1) build_sub(ls(o), o, L, mid - 1, A);
        if(mid + 1 <= R) build_sub(rs(o), o, mid + 1, R, A);
        maintain(o);
    } 
    void build(int L, int R, int *A){ 
        build_sub(rt, 0, L, R, A); 
    }
    
    int insert(int &o, int f, int target, int *A, int len){
        if(!o) return build_sub(o, f, 1, len, A), o;
        int r = 0; push(o);
        if(target <= si[ls(o)]) r = insert(ls(o), o, target, A, len);
        else r = insert(rs(o), o, target - si[ls(o)] - 1, A, len);
        maintain(o); return r;
    } void insert(int *A, int pos, int len) { int r = insert(rt, 0, pos, A, len); splay(r); }

    int find(int o, int k){
        push(o);
        if(k <= si[ls(o)]) return find(ls(o), k);
        else {
            if(k <= si[ls(o)] + 1) return o;
            else return find(rs(o), k - 1 - si[ls(o)]);
        }
    }
    void Make_Range(int L, int R){
        int per = find(rt, L - 1), suf = find(rt, R + 1);
        splay(per); splay(suf, rt);
    }
    void erase(int L, int R){
        Make_Range(L, R);
        int & target = ls(rs(rt));
        recycle(target); target = 0; maintain(rs(rt)); maintain(rt);
    }
    void rev(int L, int R){
        Make_Range(L, R);
        int & target = ls(rs(rt));
        tar_rev(target); maintain(rs(rt)); maintain(rt);
    }
    void ret(int L, int R, int V){
        Make_Range(L, R);
        int & target = ls(rs(rt));
        tar_ret(target, V); maintain(rs(rt)); maintain(rt);
    }
    int query_sum(int L, int R){
        Make_Range(L, R);
        int & target = ls(rs(rt));
        return v[target].sum;
    }
    int query_ans(){
        return v[rt].ans;
    }
   void dfs(int o = -1, int indent = 0){
    if(o == -1) o = rt;
    if(!o)  { cerr << string(indent, ' ') << "# null" << endl; return ; }
    push(o);
    if(rs(o)) assert(fa[rs(o)] == o); dfs(rs(o), indent + 10);
    cerr << string(indent, ' ') << "# v=" << val[o] << " ans=" << v[o].ans << endl;
    if(ls(o)) assert(fa[ls(o)] == o); dfs(ls(o), indent + 10);
    }
};
Splay_t t;
int A[_], n, m;
char opt[100];
int main(){ //freopen(".in", "r", stdin); freopen(".out", "w", stdout);
    Read(n)(m); n += 2; rep(i, 2, n - 1) Read(A[i]); 
    A[1] = A[n] = none; // added line `A[1] = A[n] = -inf`. 
    t.build(1, n, A);
    rep(tt, 1, m){
        scanf("%s", opt); char sign0 = opt[0], sign1 = opt[3];
        if(sign0 == 'I') { // Insert a sequence.
            int pos, tot; Read(pos)(tot); rep(i, 1, tot) Read(A[i]); pos++;
            t.insert(A, pos, tot);
        } else if(sign0 == 'D'){ // Delete a sequence.
            int pos, tot; Read(pos)(tot); pos++;
            t.erase(pos, pos + tot - 1);
        } else if(sign0 == 'R'){ // Reverse a sequence.
            int pos, tot; Read(pos)(tot); pos++;
            t.rev(pos, tot + pos - 1);
        } else if(sign0 == 'G'){ // calc the sum of sequence.
            int pos, tot; Read(pos)(tot); pos++;
            printf("%d\n", t.query_sum(pos, pos + tot - 1));
        } else if(sign1 == '-'){ // calc the max sum sub sequence.
            printf("%d\n", t.query_ans());
        } else { // make same on the sequence.
            int pos, tot, c; Read(pos)(tot)(c); pos++;
            t.ret(pos, pos + tot - 1, c);
        }
    }
    return 0;
}

非旋 Treap

udp：2021/01/02. u1s1，这东西又短又小又快。splay 可能真的只有 LCT 里面才出场了。

int rand(){
    static int seed = 1020031005;
    return seed = ((seed +0ll+ 20031006) % 998244353);
}
namespace FHQ{
    const int _ = 1e5 + 100;
    int ch[_][2], si[_], v[_], tot = 0, rt = 0;
    #define ls(o) (ch[o][0])
    #define rs(o) (ch[o][1])
    #define maintain(o) (void)(si[o] = si[ls(o)] + si[rs(o)] + 1)
    #define make(vs) (++tot, v[tot] = vs, si[tot] = 1, ch[tot][0] = ch[tot][1] = 0, tot)
    #define mg(a, b, c) (merge(merge(a, b), c))
    void split(int o, int V, int &x, int &y){
        if(!o) return (void)(x = y = 0);
        if(v[o] <= V) return x = o, split(rs(o), V, rs(o), y), maintain(o);
        return y = o, split(ls(o), V, x, ls(o)), maintain(o);
    }
    int merge(int x, int y){
        if(x == 0 || y == 0) return x + y;
        if(rand() % (si[x] + si[y]) + 1 <= si[x]) return rs(x) = merge(rs(x), y), maintain(x), x;
        else return ls(y) = merge(x, ls(y)), maintain(y), y;
    }
    void ins(int x){ int t0, t1 = make(x), t2; split(rt, x, t0, t2); rt = mg(t0, t1, t2); }
    void erase(int V){ int x, y, z; split(rt, V, y, z); split(y, V - 1, x, y); y = merge(ls(y), rs(y)); rt = mg(x, y, z); }
    int rank(int V) { int x, y; split(rt, V - 1, x, y); int res = si[x]; rt = merge(x, y); return res + 1; }
    int select(int V, int o = -1){ if(o == -1) o = rt; if(V <= si[ls(o)]) return select(V, ls(o)); else { if(V <= si[ls(o)] + 1) return v[o]; else return select(V - si[ls(o)] - 1, rs(o)); } }
    int pred(int V){ int x, y; split(rt, V - 1, x, y); int res = select(si[x], x); rt = merge(x, y); return res; }
    int succ(int V){ int x, y; split(rt, V, x, y); int res = select(1, y); rt = merge(x, y); return res; }
} using FHQ:: ins ;using FHQ:: erase ;using FHQ:: select ;using FHQ:: rank ;using FHQ:: pred ;using FHQ:: succ ;

📚 Version History

Source Code Change History

v1 📅 2020-12-20 21:34:36

🔗 Source Hash: 3f983f205f9165e3106268572e9af37c3b96c83293476ec503dd6a7fc186062b

Build Logs

Build Log - Filtered
================================================

📋 Information:
• Path information has been filtered for privacy protection
• File names are preserved for debugging purposes  
• All build status and error messages are kept intact

🔍 Filter Rules:
• /absolute/path/file.ext → .../file.ext
• /home/username → .../[user]
• /tmp/files → .../[temp]
• /usr/share/packages → .../[system]

================================================

html log:
CMD: ['pandoc', '-s', 'cache/oi-blog_「学习总结」数据结构.md', '--filter', 'pandoc-crossref', '--filter', 'pandoc-katex', '--template=cache/pandoc_html_template.html', '-o', 'cache.../oi-blog_「学习总结」数据结构.md.html', '--metadata', '--verbose', '--highlight-style=tango']
STDOUT: 
STDERR: WARNING: pandoc-crossref was compiled with pandoc 3.6.2 but is being run through 3.6.4. This is not supported. Strange things may (and likely will) happen silently.

====================================================================================================
pdf log:
CMD: ['pandoc', '-s', 'cache.../d7b80b92ac.pdf.md', '-o', 'cache/d7b80b92ac.pdf', '-H', 'static/pandoc.header.tex', '--pdf-engine=xelatex', '--verbose']
STDOUT: 
STDERR: [INFO] Loaded static.../pandoc.header.tex from static.../pandoc.header.tex
[INFO] Not rendering RawBlock (Format "html") ""
[INFO] Not rendering RawInline (Format "html") ""
[INFO] [makePDF] Temp dir:
  .../[temp]
[INFO] [makePDF] Command line:
  xelatex "-halt-on-error" "-interaction" "nonstopmode" "-output-directory" ".../[temp] ".../[temp]
[INFO] [makePDF] Relevant environment variables:
  ("TEXINPUTS",".../[temp]
  ("TEXMFOUTPUT",".../[temp]
  ("SHELL","/bin/bash")
  ("PWD",".../[user]/projects/blog")
  ("HOME",".../[user]
  ("LANG","zh_CN.UTF-8")
  ("PATH",".../[user]/.local/bin:.../[user]/.cargo/bin:.../[user]/miniconda3/envs/myblog/bin:.../[user]/miniconda3/condabin:.../[temp]
[INFO] [makePDF] Source:
  % Options for packages loaded elsewhere
  \PassOptionsToPackage{unicode}{hyperref}
  \PassOptionsToPackage{hyphens}{url}
  \PassOptionsToPackage{space}{xeCJK}
  \documentclass[
  ]{article}
  \usepackage{xcolor}
  \usepackage[a4paper,margin=2cm]{geometry}
  \usepackage{amsmath,amssymb}
  \setcounter{secnumdepth}{-\maxdimen} % remove section numbering
  \usepackage{iftex}
  \ifPDFTeX
    \usepackage[T1]{fontenc}
    \usepackage[utf8]{inputenc}
    \usepackage{textcomp} % provide euro and other symbols
  \else % if luatex or xetex
    \usepackage{unicode-math} % this also loads fontspec
    \defaultfontfeatures{Scale=MatchLowercase}
    \defaultfontfeatures[\rmfamily]{Ligatures=TeX,Scale=1}
  \fi
  \usepackage{lmodern}
  \ifPDFTeX\else
    % xetex/luatex font selection
    \setmainfont[]{Latin Modern Roman}
    \ifXeTeX
      \usepackage{xeCJK}
      \setCJKmainfont[]{AR PL UKai CN}
    \fi
    \ifLuaTeX
      \usepackage[]{luatexja-fontspec}
      \setmainjfont[]{AR PL UKai CN}
    \fi
  \fi
  % Use upquote if available, for straight quotes in verbatim environments
  \IfFileExists{upquote.sty}{\usepackage{upquote}}{}
  \IfFileExists{microtype.sty}{% use microtype if available
    \usepackage[]{microtype}
    \UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
  }{}
  \usepackage{setspace}
  \makeatletter
  \@ifundefined{KOMAClassName}{% if non-KOMA class
    \IfFileExists{parskip.sty}{%
      \usepackage{parskip}
    }{% else
      \setlength{\parindent}{0pt}
      \setlength{\parskip}{6pt plus 2pt minus 1pt}}
  }{% if KOMA class
    \KOMAoptions{parskip=half}}
  \makeatother
  \usepackage{color}
  \usepackage{fancyvrb}
  \newcommand{\VerbBar}{|}
  \newcommand{\VERB}{\Verb[commandchars=\\\{\}]}
  \DefineVerbatimEnvironment{Highlighting}{Verbatim}{commandchars=\\\{\}}
  % Add ',fontsize=\small' for more characters per line
  \newenvironment{Shaded}{}{}
  \newcommand{\AlertTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{#1}}}
  \newcommand{\AnnotationTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
  \newcommand{\AttributeTok}[1]{\textcolor[rgb]{0.49,0.56,0.16}{#1}}
  \newcommand{\BaseNTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
  \newcommand{\BuiltInTok}[1]{\textcolor[rgb]{0.00,0.50,0.00}{#1}}
  \newcommand{\CharTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
  \newcommand{\CommentTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textit{#1}}}
  \newcommand{\CommentVarTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
  \newcommand{\ConstantTok}[1]{\textcolor[rgb]{0.53,0.00,0.00}{#1}}
  \newcommand{\ControlFlowTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{\textbf{#1}}}
  \newcommand{\DataTypeTok}[1]{\textcolor[rgb]{0.56,0.13,0.00}{#1}}
  \newcommand{\DecValTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
  \newcommand{\DocumentationTok}[1]{\textcolor[rgb]{0.73,0.13,0.13}{\textit{#1}}}
  \newcommand{\ErrorTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{#1}}}
  \newcommand{\ExtensionTok}[1]{#1}
  \newcommand{\FloatTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
  \newcommand{\FunctionTok}[1]{\textcolor[rgb]{0.02,0.16,0.49}{#1}}
  \newcommand{\ImportTok}[1]{\textcolor[rgb]{0.00,0.50,0.00}{\textbf{#1}}}
  \newcommand{\InformationTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
  \newcommand{\KeywordTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{\textbf{#1}}}
  \newcommand{\NormalTok}[1]{#1}
  \newcommand{\OperatorTok}[1]{\textcolor[rgb]{0.40,0.40,0.40}{#1}}
  \newcommand{\OtherTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{#1}}
  \newcommand{\PreprocessorTok}[1]{\textcolor[rgb]{0.74,0.48,0.00}{#1}}
  \newcommand{\RegionMarkerTok}[1]{#1}
  \newcommand{\SpecialCharTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
  \newcommand{\SpecialStringTok}[1]{\textcolor[rgb]{0.73,0.40,0.53}{#1}}
  \newcommand{\StringTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
  \newcommand{\VariableTok}[1]{\textcolor[rgb]{0.10,0.09,0.49}{#1}}
  \newcommand{\VerbatimStringTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
  \newcommand{\WarningTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
  \ifLuaTeX
    \usepackage{luacolor}
    \usepackage[soul]{lua-ul}
  \else
    \usepackage{soul}
    \ifXeTeX
      % soul's \st doesn't work for CJK:
      \usepackage{xeCJKfntef}
      \renewcommand{\st}[1]{\sout{#1}}
    \fi
  \fi
  \setlength{\emergencystretch}{3em} % prevent overfull lines
  \providecommand{\tightlist}{%
    \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
  % \usepackage{xeCJK}
  % \setCJKmainfont{AR PL UKai CN}
  % \usepackage{unicode-math}
  
  \setmathfont{Latin Modern Math}
  \usepackage{bookmark}
  \IfFileExists{xurl.sty}{\usepackage{xurl}}{} % add URL line breaks if available
  \urlstyle{same}
  \hypersetup{
    pdftitle={「学习总结」数据结构},
    pdfauthor={Jiayi Su (ShuYuMo)},
    hidelinks,
    pdfcreator={LaTeX via pandoc}}
  
  \title{「学习总结」数据结构}
  \author{Jiayi Su (ShuYuMo)}
  \date{2020-12-20 21:34:36}
  
  \begin{document}
  \maketitle
  
  \setstretch{1.3}
  \st{真的好爱 \mbox{\texttt{Splay}}!}
  
  好像只有 \texttt{LCT} 中才有必要写 \texttt{Splay} 吧…… 其实
  \texttt{非旋\ Treap} 真的是又短，有小，又快……
  
  \section{数据结构}\label{ux6570ux636eux7ed3ux6784}
  
  \subsection{平衡树}\label{ux5e73ux8861ux6811}
  
  \subsubsection{Splay}\label{splay}
  
  \begin{itemize}
  \tightlist
  \item
    删除结点时，不是 \texttt{Splay}
    到根然后合并两边的子树，而是将待删除的结点前驱 \texttt{Splay}
    到根节点， 后继 \texttt{Splay} 到根节点右儿子，那么待删除的结点就在
    \texttt{ls(rs(rt))}
    上。这样可以删除集合内一个区间的元素，也方便后面维护序列。
  \end{itemize}
  
  \begin{Shaded}
  \begin{Highlighting}[]
  \DataTypeTok{void}\NormalTok{ erase}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ v}\OperatorTok{)\{}
  \NormalTok{    PII pre }\OperatorTok{=}\NormalTok{ \_pred}\OperatorTok{(}\NormalTok{v}\OperatorTok{),}\NormalTok{ nxt }\OperatorTok{=}\NormalTok{ \_nxtd}\OperatorTok{(}\NormalTok{v}\OperatorTok{);}
  \NormalTok{    splay}\OperatorTok{(}\NormalTok{pre}\OperatorTok{.}\NormalTok{se}\OperatorTok{);}\NormalTok{ splay}\OperatorTok{(}\NormalTok{nxt}\OperatorTok{.}\NormalTok{se}\OperatorTok{,}\NormalTok{ rt}\OperatorTok{);}
      \DataTypeTok{int} \OperatorTok{\&}\NormalTok{target }\OperatorTok{=}\NormalTok{ ls}\OperatorTok{(}\NormalTok{rs}\OperatorTok{(}\NormalTok{rt}\OperatorTok{));}\NormalTok{ cnt}\OperatorTok{[}\NormalTok{target}\OperatorTok{]} \OperatorTok{{-}{-};}\NormalTok{ si}\OperatorTok{[}\NormalTok{target}\OperatorTok{]{-}{-};}
      \ControlFlowTok{if}\OperatorTok{(!}\NormalTok{cnt}\OperatorTok{[}\NormalTok{target}\OperatorTok{])}\NormalTok{ target }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
  \NormalTok{    maintain}\OperatorTok{(}\NormalTok{rs}\OperatorTok{(}\NormalTok{rt}\OperatorTok{));}\NormalTok{ maintain}\OperatorTok{(}\NormalTok{ls}\OperatorTok{(}\NormalTok{rt}\OperatorTok{));}\NormalTok{  maintain}\OperatorTok{(}\NormalTok{rt}\OperatorTok{);}
  \OperatorTok{\}}
  \end{Highlighting}
  \end{Shaded}
  
  \begin{itemize}
  \tightlist
  \item
    如果空间要求较严格，可以考虑手写一个小的内存管理函数，删除时回收内存，新增元素时优先使用之前删除的结点内存。
  \end{itemize}
  
  \begin{Shaded}
  \begin{Highlighting}[]
  \NormalTok{stack}\OperatorTok{\textless{}}\DataTypeTok{int}\OperatorTok{\textgreater{}}\NormalTok{ Mem}\OperatorTok{;}
  \DataTypeTok{int}\NormalTok{ make}\OperatorTok{()\{}
      \DataTypeTok{int}\NormalTok{ t}\OperatorTok{;} \DataTypeTok{int}\NormalTok{ o }\OperatorTok{=} \OperatorTok{(}\NormalTok{Mem}\OperatorTok{.}\NormalTok{empty}\OperatorTok{()} \OperatorTok{?} \OperatorTok{++}\NormalTok{tot }\OperatorTok{:} \OperatorTok{(}\NormalTok{t }\OperatorTok{=}\NormalTok{ Mem}\OperatorTok{.}\NormalTok{top}\OperatorTok{(),}\NormalTok{ Mem}\OperatorTok{.}\NormalTok{pop}\OperatorTok{(),}\NormalTok{ t}\OperatorTok{));} 
  \NormalTok{    ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\DecValTok{1}\OperatorTok{]} \OperatorTok{=}\NormalTok{ ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\DecValTok{0}\OperatorTok{]} \OperatorTok{=}\NormalTok{ v}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{=}\NormalTok{ fa}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{=} \DecValTok{0}\OperatorTok{;}
  \NormalTok{    si}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{=} \DecValTok{1}\OperatorTok{;}
      \ControlFlowTok{return}\NormalTok{ o}\OperatorTok{;}
  \OperatorTok{\}}
  \DataTypeTok{void}\NormalTok{ recycle}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o }\OperatorTok{=} \OperatorTok{{-}}\DecValTok{1}\OperatorTok{)} \OperatorTok{\{} \ControlFlowTok{if}\OperatorTok{(}\NormalTok{o }\OperatorTok{==} \OperatorTok{{-}}\DecValTok{1}\OperatorTok{)}\NormalTok{ o }\OperatorTok{=}\NormalTok{ rt}\OperatorTok{;} \ControlFlowTok{if}\OperatorTok{(!}\NormalTok{o}\OperatorTok{)} \ControlFlowTok{return} \OperatorTok{;}\NormalTok{ Mem}\OperatorTok{.}\NormalTok{push}\OperatorTok{(}\NormalTok{o}\OperatorTok{);}\NormalTok{ recycle}\OperatorTok{(}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{));}\NormalTok{ recycle}\OperatorTok{(}\NormalTok{rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{));} \OperatorTok{\}}
  \end{Highlighting}
  \end{Shaded}
  
  \begin{itemize}
  \tightlist
  \item
    如果需要开多棵 \texttt{Splay}，可以考虑只封装每棵 \texttt{Splay}
    的根节点，对于结点内存的申请和释放统一管理
  \item
    一个很方便的调试 \texttt{Splay} 的函数：
  \end{itemize}
  
  \begin{Shaded}
  \begin{Highlighting}[]
  \DataTypeTok{void}\NormalTok{ dfs}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o }\OperatorTok{=} \OperatorTok{{-}}\DecValTok{1}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ indent }\OperatorTok{=} \DecValTok{0}\OperatorTok{)\{}
      \ControlFlowTok{if}\OperatorTok{(}\NormalTok{o }\OperatorTok{==} \OperatorTok{{-}}\DecValTok{1}\OperatorTok{)}\NormalTok{ o }\OperatorTok{=}\NormalTok{ rt}\OperatorTok{;}
      \ControlFlowTok{if}\OperatorTok{(!}\NormalTok{o}\OperatorTok{)}  \OperatorTok{\{}\NormalTok{ cerr }\OperatorTok{\textless{}\textless{}}\NormalTok{ string}\OperatorTok{(}\NormalTok{indent}\OperatorTok{,} \CharTok{\textquotesingle{} \textquotesingle{}}\OperatorTok{)} \OperatorTok{\textless{}\textless{}} \StringTok{"\# null"} \OperatorTok{\textless{}\textless{}}\NormalTok{ endl}\OperatorTok{;} \ControlFlowTok{return} \OperatorTok{;} \OperatorTok{\}}
  \NormalTok{    push}\OperatorTok{(}\NormalTok{o}\OperatorTok{);}
      \OtherTok{assert}\OperatorTok{(!}\NormalTok{rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{)} \OperatorTok{||}\NormalTok{ fa}\OperatorTok{[}\NormalTok{rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{)]} \OperatorTok{==}\NormalTok{ o}\OperatorTok{);}\NormalTok{ dfs}\OperatorTok{(}\NormalTok{rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{),}\NormalTok{ indent }\OperatorTok{+} \DecValTok{10}\OperatorTok{);}
  \NormalTok{    cerr }\OperatorTok{\textless{}\textless{}}\NormalTok{ string}\OperatorTok{(}\NormalTok{indent}\OperatorTok{,} \CharTok{\textquotesingle{} \textquotesingle{}}\OperatorTok{)} \OperatorTok{\textless{}\textless{}} \StringTok{"\# v="} \OperatorTok{\textless{}\textless{}}\NormalTok{ val}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{\textless{}\textless{}} \StringTok{" ans="} \OperatorTok{\textless{}\textless{}}\NormalTok{ v}\OperatorTok{[}\NormalTok{o}\OperatorTok{].}\NormalTok{ans }\OperatorTok{\textless{}\textless{}}\NormalTok{ endl}\OperatorTok{;}
      \OtherTok{assert}\OperatorTok{(!}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{)} \OperatorTok{||}\NormalTok{ fa}\OperatorTok{[}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{)]} \OperatorTok{==}\NormalTok{ o}\OperatorTok{);}\NormalTok{ dfs}\OperatorTok{(}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{),}\NormalTok{ indent }\OperatorTok{+} \DecValTok{10}\OperatorTok{);}
  \OperatorTok{\}}
  \end{Highlighting}
  \end{Shaded}
  
  \begin{itemize}
  \tightlist
  \item
    建立哨兵结点作为整个 \texttt{Splay}
    的最小最大值是一个通用技巧，删除操作依赖于前驱和后继结点，所以哨兵结点时必要的。维护序列时注意消除哨兵结点对答案的影响。
  \end{itemize}
  
  \paragraph{维护集合}\label{ux7ef4ux62a4ux96c6ux5408}
  
  一种动态维护集合元素，查询集合元素信息的解决方案。 -
  为了优化常数和简化代码，查询前驱后继不再采用 \texttt{插入-删除}
  式查询。查询元素排名之后直接选取前驱和后继即可。
  
  \begin{Shaded}
  \begin{Highlighting}[]
  \NormalTok{PII \_pred}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ v}\OperatorTok{)\{}
  \NormalTok{    PII res }\OperatorTok{=}\NormalTok{ rank}\OperatorTok{(}\NormalTok{rt}\OperatorTok{,}\NormalTok{ v}\OperatorTok{);}
      \ControlFlowTok{return}\NormalTok{ select}\OperatorTok{(}\NormalTok{rt}\OperatorTok{,}\NormalTok{ res}\OperatorTok{.}\NormalTok{fi }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{);}
  \OperatorTok{\}} \DataTypeTok{int}\NormalTok{ pred}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ v}\OperatorTok{)} \OperatorTok{\{}\NormalTok{ PII res }\OperatorTok{=}\NormalTok{ \_pred}\OperatorTok{(}\NormalTok{v}\OperatorTok{);}\NormalTok{ splay}\OperatorTok{(}\NormalTok{res}\OperatorTok{.}\NormalTok{se}\OperatorTok{);} \ControlFlowTok{return}\NormalTok{ res}\OperatorTok{.}\NormalTok{fi}\OperatorTok{;} \OperatorTok{\}}
  \end{Highlighting}
  \end{Shaded}
  
  \begin{itemize}
  \tightlist
  \item
    \texttt{rank} 和 \texttt{select} 返回值为
    \texttt{pair\textless{}int,\ int\textgreater{}}
    其中，前一个指答案，后一个是作用结点，方便后期获取结点信息（\texttt{Splay}）。
    \texttt{int\ rank(int\ v)\ \{\ PII\ res\ =\ rank(rt,\ v);\ if(res.se)\ splay(res.se);\ return\ res.fi\ -\ 1;\ \}}
  \end{itemize}
  
  \begin{Shaded}
  \begin{Highlighting}[]
  \KeywordTok{struct} \DataTypeTok{Splay\_t}\OperatorTok{\{}
      \DataTypeTok{int}\NormalTok{ ch}\OperatorTok{[}\NormalTok{\_}\OperatorTok{][}\DecValTok{2}\OperatorTok{],}\NormalTok{ cnt}\OperatorTok{[}\NormalTok{\_}\OperatorTok{],}\NormalTok{ si}\OperatorTok{[}\NormalTok{\_}\OperatorTok{],}\NormalTok{ v}\OperatorTok{[}\NormalTok{\_}\OperatorTok{],}\NormalTok{ fa}\OperatorTok{[}\NormalTok{\_}\OperatorTok{],}\NormalTok{ tot}\OperatorTok{,}\NormalTok{ rt}\OperatorTok{;}
      \KeywordTok{typedef}\NormalTok{ pair}\OperatorTok{\textless{}}\DataTypeTok{int}\OperatorTok{,} \DataTypeTok{int}\OperatorTok{\textgreater{}}\NormalTok{ PII}\OperatorTok{;}
      \PreprocessorTok{\#define ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{)}\PreprocessorTok{ }\OperatorTok{(}\NormalTok{ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\DecValTok{0}\OperatorTok{])}
      \PreprocessorTok{\#define rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{)}\PreprocessorTok{ }\OperatorTok{(}\NormalTok{ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\DecValTok{1}\OperatorTok{])}
      \PreprocessorTok{\#define maintain}\OperatorTok{(}\NormalTok{o}\OperatorTok{)}\PreprocessorTok{ }\OperatorTok{(}\NormalTok{si}\OperatorTok{[}\NormalTok{o}\OperatorTok{]}\PreprocessorTok{ }\OperatorTok{=}\PreprocessorTok{ }\NormalTok{si}\OperatorTok{[}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{)]}\PreprocessorTok{ }\OperatorTok{+}\PreprocessorTok{ }\NormalTok{cnt}\OperatorTok{[}\NormalTok{o}\OperatorTok{]}\PreprocessorTok{ }\OperatorTok{+}\PreprocessorTok{ }\NormalTok{si}\OperatorTok{[}\NormalTok{rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{)])}
      \PreprocessorTok{\#define get}\OperatorTok{(}\NormalTok{o}\OperatorTok{)}\PreprocessorTok{ }\OperatorTok{(}\NormalTok{o}\PreprocessorTok{ }\OperatorTok{==}\PreprocessorTok{ }\NormalTok{ch}\OperatorTok{[}\NormalTok{fa}\OperatorTok{[}\NormalTok{o}\OperatorTok{]][}\DecValTok{1}\OperatorTok{])}
      \DataTypeTok{int}\NormalTok{ make}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ f}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ V}\OperatorTok{)\{}
  \NormalTok{        tot}\OperatorTok{++;}
  \NormalTok{        ch}\OperatorTok{[}\NormalTok{tot}\OperatorTok{][}\DecValTok{1}\OperatorTok{]} \OperatorTok{=}\NormalTok{ ch}\OperatorTok{[}\NormalTok{tot}\OperatorTok{][}\DecValTok{0}\OperatorTok{]} \OperatorTok{=} \DecValTok{0}\OperatorTok{;}
  \NormalTok{        si}\OperatorTok{[}\NormalTok{tot}\OperatorTok{]} \OperatorTok{=}\NormalTok{ cnt}\OperatorTok{[}\NormalTok{tot}\OperatorTok{]} \OperatorTok{=} \DecValTok{1}\OperatorTok{;}
  \NormalTok{        fa}\OperatorTok{[}\NormalTok{tot}\OperatorTok{]} \OperatorTok{=}\NormalTok{ f}\OperatorTok{;}\NormalTok{ v}\OperatorTok{[}\NormalTok{tot}\OperatorTok{]} \OperatorTok{=}\NormalTok{ V}\OperatorTok{;}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{f}\OperatorTok{)}\NormalTok{ ch}\OperatorTok{[}\NormalTok{f}\OperatorTok{][}\NormalTok{v}\OperatorTok{[}\NormalTok{f}\OperatorTok{]} \OperatorTok{\textless{}}\NormalTok{ V}\OperatorTok{]} \OperatorTok{=}\NormalTok{ tot}\OperatorTok{;}
          \ControlFlowTok{return}\NormalTok{ tot}\OperatorTok{;}
      \OperatorTok{\}}
      \DataTypeTok{void}\NormalTok{ rotate}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{)\{}
          \DataTypeTok{int}\NormalTok{ p }\OperatorTok{=}\NormalTok{ fa}\OperatorTok{[}\NormalTok{o}\OperatorTok{],}\NormalTok{ gp }\OperatorTok{=}\NormalTok{ fa}\OperatorTok{[}\NormalTok{fa}\OperatorTok{[}\NormalTok{o}\OperatorTok{]],}\NormalTok{ chk }\OperatorTok{=}\NormalTok{ get}\OperatorTok{(}\NormalTok{o}\OperatorTok{);}
  \NormalTok{        ch}\OperatorTok{[}\NormalTok{p}\OperatorTok{][}\NormalTok{chk}\OperatorTok{]} \OperatorTok{=}\NormalTok{ ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\NormalTok{chk}\OperatorTok{\^{}}\DecValTok{1}\OperatorTok{];}\NormalTok{ fa}\OperatorTok{[}\NormalTok{ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\NormalTok{chk}\OperatorTok{\^{}}\DecValTok{1}\OperatorTok{]]} \OperatorTok{=}\NormalTok{ p}\OperatorTok{;}
  \NormalTok{        ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\NormalTok{chk}\OperatorTok{\^{}}\DecValTok{1}\OperatorTok{]} \OperatorTok{=}\NormalTok{ p}\OperatorTok{;}\NormalTok{ fa}\OperatorTok{[}\NormalTok{p}\OperatorTok{]} \OperatorTok{=}\NormalTok{ o}\OperatorTok{;}
  \NormalTok{        fa}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{=}\NormalTok{ gp}\OperatorTok{;} \ControlFlowTok{if}\OperatorTok{(}\NormalTok{gp}\OperatorTok{)}\NormalTok{ ch}\OperatorTok{[}\NormalTok{gp}\OperatorTok{][}\NormalTok{ch}\OperatorTok{[}\NormalTok{gp}\OperatorTok{][}\DecValTok{1}\OperatorTok{]} \OperatorTok{==}\NormalTok{ p}\OperatorTok{]} \OperatorTok{=}\NormalTok{ o}\OperatorTok{;}
  \NormalTok{        maintain}\OperatorTok{(}\NormalTok{p}\OperatorTok{);}\NormalTok{ maintain}\OperatorTok{(}\NormalTok{o}\OperatorTok{);}
      \OperatorTok{\}}
      \DataTypeTok{void}\NormalTok{ splay}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ tgp }\OperatorTok{=} \DecValTok{0}\OperatorTok{)\{}
          \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ f }\OperatorTok{=}\NormalTok{ fa}\OperatorTok{[}\NormalTok{o}\OperatorTok{];}\NormalTok{ f }\OperatorTok{=}\NormalTok{ fa}\OperatorTok{[}\NormalTok{o}\OperatorTok{],}\NormalTok{ f }\OperatorTok{!=}\NormalTok{ tgp}\OperatorTok{;}\NormalTok{ rotate}\OperatorTok{(}\NormalTok{o}\OperatorTok{))} \ControlFlowTok{if}\OperatorTok{(}\NormalTok{fa}\OperatorTok{[}\NormalTok{f}\OperatorTok{]} \OperatorTok{!=}\NormalTok{ tgp}\OperatorTok{)}\NormalTok{ rotate}\OperatorTok{(}\NormalTok{get}\OperatorTok{(}\NormalTok{o}\OperatorTok{)} \OperatorTok{==}\NormalTok{ get}\OperatorTok{(}\NormalTok{f}\OperatorTok{)} \OperatorTok{?}\NormalTok{ f }\OperatorTok{:}\NormalTok{ o}\OperatorTok{);}
          \ControlFlowTok{if}\OperatorTok{(!}\NormalTok{tgp}\OperatorTok{)}\NormalTok{ rt }\OperatorTok{=}\NormalTok{ o}\OperatorTok{;}
      \OperatorTok{\}}
      \DataTypeTok{int}\NormalTok{ ins}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ f}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ V}\OperatorTok{)\{}
          \ControlFlowTok{if}\OperatorTok{(!}\NormalTok{o}\OperatorTok{)} \ControlFlowTok{return}\NormalTok{ make}\OperatorTok{(}\NormalTok{f}\OperatorTok{,}\NormalTok{ V}\OperatorTok{);}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{v}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{==}\NormalTok{ V}\OperatorTok{)} \ControlFlowTok{return} \OperatorTok{(}\NormalTok{cnt}\OperatorTok{[}\NormalTok{o}\OperatorTok{]++,}\NormalTok{ si}\OperatorTok{[}\NormalTok{o}\OperatorTok{]++,}\NormalTok{ o}\OperatorTok{);}
          \DataTypeTok{int}\NormalTok{ r}\OperatorTok{;} \ControlFlowTok{return} \OperatorTok{(}\NormalTok{r }\OperatorTok{=}\NormalTok{ ins}\OperatorTok{(}\NormalTok{V }\OperatorTok{\textless{}}\NormalTok{ v}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{?}\NormalTok{ ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{)} \OperatorTok{:}\NormalTok{ rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{),}\NormalTok{ o}\OperatorTok{,}\NormalTok{ V}\OperatorTok{),}\NormalTok{ maintain}\OperatorTok{(}\NormalTok{o}\OperatorTok{),}\NormalTok{ r}\OperatorTok{);}
      \OperatorTok{\}} \DataTypeTok{void}\NormalTok{ ins}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ v}\OperatorTok{)} \OperatorTok{\{} \DataTypeTok{int}\NormalTok{ t }\OperatorTok{=}\NormalTok{ ins}\OperatorTok{(}\NormalTok{rt}\OperatorTok{,} \DecValTok{0}\OperatorTok{,}\NormalTok{ v}\OperatorTok{);}\NormalTok{ splay}\OperatorTok{(}\NormalTok{t}\OperatorTok{);} \OperatorTok{\}}
      
  \NormalTok{    PII rank}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ V}\OperatorTok{)\{}
          \ControlFlowTok{if}\OperatorTok{(!}\NormalTok{o}\OperatorTok{)} \ControlFlowTok{return}\NormalTok{ mp}\OperatorTok{(}\DecValTok{1}\OperatorTok{,} \DecValTok{0}\OperatorTok{);}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{V }\OperatorTok{==}\NormalTok{ v}\OperatorTok{[}\NormalTok{o}\OperatorTok{])} \ControlFlowTok{return}\NormalTok{ mp}\OperatorTok{(}\NormalTok{si}\OperatorTok{[}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{)]} \OperatorTok{+} \DecValTok{1}\OperatorTok{,}\NormalTok{ o}\OperatorTok{);}
  \NormalTok{        PII res}\OperatorTok{;} 
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{V }\OperatorTok{\textless{}}\NormalTok{ v}\OperatorTok{[}\NormalTok{o}\OperatorTok{])} \ControlFlowTok{return}\NormalTok{ rank}\OperatorTok{(}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{),}\NormalTok{ V}\OperatorTok{);} 
          \ControlFlowTok{else} \ControlFlowTok{return} \OperatorTok{(}\NormalTok{res }\OperatorTok{=}\NormalTok{ rank}\OperatorTok{(}\NormalTok{rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{),}\NormalTok{ V}\OperatorTok{),}\NormalTok{ res}\OperatorTok{.}\NormalTok{fi }\OperatorTok{+=}\NormalTok{ cnt}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{+}\NormalTok{ si}\OperatorTok{[}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{)],}\NormalTok{ res}\OperatorTok{);}
      \OperatorTok{\}} \DataTypeTok{int}\NormalTok{ rank}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ v}\OperatorTok{)} \OperatorTok{\{}\NormalTok{ PII res }\OperatorTok{=}\NormalTok{ rank}\OperatorTok{(}\NormalTok{rt}\OperatorTok{,}\NormalTok{ v}\OperatorTok{);} \ControlFlowTok{if}\OperatorTok{(}\NormalTok{res}\OperatorTok{.}\NormalTok{se}\OperatorTok{)}\NormalTok{ splay}\OperatorTok{(}\NormalTok{res}\OperatorTok{.}\NormalTok{se}\OperatorTok{);} \ControlFlowTok{return}\NormalTok{ res}\OperatorTok{.}\NormalTok{fi }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{;} \OperatorTok{\}}
      
  \NormalTok{    PII select}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ k}\OperatorTok{)\{}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{k }\OperatorTok{\textless{}=}\NormalTok{ si}\OperatorTok{[}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{)])} \ControlFlowTok{return}\NormalTok{ select}\OperatorTok{(}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{),}\NormalTok{ k}\OperatorTok{);}
          \ControlFlowTok{else} \OperatorTok{\{}
              \ControlFlowTok{if}\OperatorTok{(}\NormalTok{k }\OperatorTok{\textless{}=}\NormalTok{ si}\OperatorTok{[}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{)]} \OperatorTok{+}\NormalTok{ cnt}\OperatorTok{[}\NormalTok{o}\OperatorTok{])} \ControlFlowTok{return}\NormalTok{ mp}\OperatorTok{(}\NormalTok{v}\OperatorTok{[}\NormalTok{o}\OperatorTok{],}\NormalTok{ o}\OperatorTok{);}
              \ControlFlowTok{else} \ControlFlowTok{return}\NormalTok{ select}\OperatorTok{(}\NormalTok{rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{),}\NormalTok{ k }\OperatorTok{{-}}\NormalTok{ cnt}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{{-}}\NormalTok{ si}\OperatorTok{[}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{)]);}
          \OperatorTok{\}}
      \OperatorTok{\}} \DataTypeTok{int}\NormalTok{ select}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ k}\OperatorTok{)} \OperatorTok{\{}\NormalTok{ PII res }\OperatorTok{=}\NormalTok{ select}\OperatorTok{(}\NormalTok{rt}\OperatorTok{,}\NormalTok{ k }\OperatorTok{+} \DecValTok{1}\OperatorTok{);}\NormalTok{ splay}\OperatorTok{(}\NormalTok{res}\OperatorTok{.}\NormalTok{se}\OperatorTok{);} \ControlFlowTok{return}\NormalTok{ res}\OperatorTok{.}\NormalTok{fi}\OperatorTok{;} \OperatorTok{\}}
      
  \NormalTok{    PII \_pred}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ v}\OperatorTok{)\{}
  \NormalTok{        PII res }\OperatorTok{=}\NormalTok{ rank}\OperatorTok{(}\NormalTok{rt}\OperatorTok{,}\NormalTok{ v}\OperatorTok{);}
          \ControlFlowTok{return}\NormalTok{ select}\OperatorTok{(}\NormalTok{rt}\OperatorTok{,}\NormalTok{ res}\OperatorTok{.}\NormalTok{fi }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{);}
      \OperatorTok{\}} \DataTypeTok{int}\NormalTok{ pred}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ v}\OperatorTok{)} \OperatorTok{\{}\NormalTok{ PII res }\OperatorTok{=}\NormalTok{ \_pred}\OperatorTok{(}\NormalTok{v}\OperatorTok{);}\NormalTok{ splay}\OperatorTok{(}\NormalTok{res}\OperatorTok{.}\NormalTok{se}\OperatorTok{);} \ControlFlowTok{return}\NormalTok{ res}\OperatorTok{.}\NormalTok{fi}\OperatorTok{;} \OperatorTok{\}}
  
  \NormalTok{    PII \_nxtd}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ v}\OperatorTok{)\{}
  \NormalTok{        PII res }\OperatorTok{=}\NormalTok{ rank}\OperatorTok{(}\NormalTok{rt}\OperatorTok{,}\NormalTok{ v}\OperatorTok{);}
          \ControlFlowTok{return}\NormalTok{ select}\OperatorTok{(}\NormalTok{rt}\OperatorTok{,}\NormalTok{ res}\OperatorTok{.}\NormalTok{fi }\OperatorTok{+}\NormalTok{ cnt}\OperatorTok{[}\NormalTok{res}\OperatorTok{.}\NormalTok{se}\OperatorTok{]);}
      \OperatorTok{\}} \DataTypeTok{int}\NormalTok{ nxtd}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ v}\OperatorTok{)} \OperatorTok{\{}\NormalTok{ PII res }\OperatorTok{=}\NormalTok{ \_nxtd}\OperatorTok{(}\NormalTok{v}\OperatorTok{);}\NormalTok{ splay}\OperatorTok{(}\NormalTok{res}\OperatorTok{.}\NormalTok{se}\OperatorTok{);} \ControlFlowTok{return}\NormalTok{ res}\OperatorTok{.}\NormalTok{fi}\OperatorTok{;} \OperatorTok{\}}
      
      \DataTypeTok{void}\NormalTok{ erase}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ v}\OperatorTok{)\{}
  \NormalTok{        PII pre }\OperatorTok{=}\NormalTok{ \_pred}\OperatorTok{(}\NormalTok{v}\OperatorTok{),}\NormalTok{ nxt }\OperatorTok{=}\NormalTok{ \_nxtd}\OperatorTok{(}\NormalTok{v}\OperatorTok{);}
  \NormalTok{        splay}\OperatorTok{(}\NormalTok{pre}\OperatorTok{.}\NormalTok{se}\OperatorTok{);}\NormalTok{ splay}\OperatorTok{(}\NormalTok{nxt}\OperatorTok{.}\NormalTok{se}\OperatorTok{,}\NormalTok{ rt}\OperatorTok{);}
          \DataTypeTok{int} \OperatorTok{\&}\NormalTok{target }\OperatorTok{=}\NormalTok{ ls}\OperatorTok{(}\NormalTok{rs}\OperatorTok{(}\NormalTok{rt}\OperatorTok{));}\NormalTok{ cnt}\OperatorTok{[}\NormalTok{target}\OperatorTok{]} \OperatorTok{{-}{-};}\NormalTok{ si}\OperatorTok{[}\NormalTok{target}\OperatorTok{]{-}{-};}
          \ControlFlowTok{if}\OperatorTok{(!}\NormalTok{cnt}\OperatorTok{[}\NormalTok{target}\OperatorTok{])}\NormalTok{ target }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
  \NormalTok{        maintain}\OperatorTok{(}\NormalTok{rs}\OperatorTok{(}\NormalTok{rt}\OperatorTok{));}\NormalTok{ maintain}\OperatorTok{(}\NormalTok{ls}\OperatorTok{(}\NormalTok{rt}\OperatorTok{));}\NormalTok{  maintain}\OperatorTok{(}\NormalTok{rt}\OperatorTok{);}
      \OperatorTok{\}}
      \DataTypeTok{Splay\_t}\OperatorTok{()\{}\NormalTok{ tot }\OperatorTok{=}\NormalTok{ rt }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}\NormalTok{ ins}\OperatorTok{(}\NormalTok{INT\_MAX}\OperatorTok{);}\NormalTok{ ins}\OperatorTok{(}\NormalTok{INT\_MIN}\OperatorTok{);} \OperatorTok{\}}
  \OperatorTok{\};}
  \end{Highlighting}
  \end{Shaded}
  
  \paragraph{维护序列}\label{ux7ef4ux62a4ux5e8fux5217}
  
  一种支持增删元素的，线段树替代方案。
  本质上和线段的思想很相似，一样采用信息合并和懒标记优化复杂度，每个结点也和线段树一样存储一个子区间的信息。
  唯一不同的就是线段树是一种
  \texttt{Leafy\ Tree}，即所有信息都只存储在叶子结点上，其结构导致无法删除和新增元素。
  -
  注意懒标记和线段树的定义是一样的，其作用节点的信息首先被修改。类比线段树的懒标记直接写就好了。
  -
  平衡树合并信息和线段树合并信息不同点在于：线段树是合并两边的信息，平衡树是先合并左子结点信息和中间结点信息再与有子结点合并，其实还是因为线段树是一种
  \texttt{Leafy\ Tree} —— 和平衡树有本质区别。 - 因为 \texttt{Splay}
  可以相对较好的控制树的形态，可以让一个子树组成任意区间，所以能够很好的维护序列。
  - 核心操作：
  
  \begin{Shaded}
  \begin{Highlighting}[]
  \DataTypeTok{void}\NormalTok{ Make\_Range}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ L}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ R}\OperatorTok{)\{}
      \DataTypeTok{int}\NormalTok{ pre }\OperatorTok{=}\NormalTok{ find}\OperatorTok{(}\NormalTok{rt}\OperatorTok{,}\NormalTok{ L }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{),}\NormalTok{ suf }\OperatorTok{=}\NormalTok{ find}\OperatorTok{(}\NormalTok{rt}\OperatorTok{,}\NormalTok{ R }\OperatorTok{+} \DecValTok{1}\OperatorTok{);}
  \NormalTok{    splay}\OperatorTok{(}\NormalTok{pre}\OperatorTok{);}\NormalTok{ splay}\OperatorTok{(}\NormalTok{suf}\OperatorTok{,}\NormalTok{ rt}\OperatorTok{);}
  \OperatorTok{\}}
  \end{Highlighting}
  \end{Shaded}
  
  \begin{Shaded}
  \begin{Highlighting}[]
  \AttributeTok{const} \DataTypeTok{int}\NormalTok{ \_ }\OperatorTok{=} \FloatTok{5e5} \OperatorTok{+} \DecValTok{10}\OperatorTok{;}
  \KeywordTok{struct} \DataTypeTok{Splay\_t}\OperatorTok{\{}
  \NormalTok{    stack}\OperatorTok{\textless{}}\DataTypeTok{int}\OperatorTok{\textgreater{}}\NormalTok{ Mem}\OperatorTok{;}
      \PreprocessorTok{\#define none }\OperatorTok{({-}}\DecValTok{30000}\OperatorTok{)}
      \KeywordTok{struct} \DataTypeTok{data\_t}\OperatorTok{\{}
          \DataTypeTok{int}\NormalTok{ sum}\OperatorTok{,}\NormalTok{ per}\OperatorTok{,}\NormalTok{ suf}\OperatorTok{,}\NormalTok{ ans}\OperatorTok{;}
          \DataTypeTok{data\_t}\OperatorTok{()\{}\NormalTok{ per }\OperatorTok{=}\NormalTok{ suf }\OperatorTok{=}\NormalTok{ ans }\OperatorTok{=} \OperatorTok{{-}}\FloatTok{1e9}\OperatorTok{;}\NormalTok{ sum }\OperatorTok{=} \DecValTok{0}\OperatorTok{;} \OperatorTok{\};}
          \DataTypeTok{data\_t}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ V}\OperatorTok{)} \OperatorTok{\{}\NormalTok{ sum }\OperatorTok{=}\NormalTok{ per }\OperatorTok{=}\NormalTok{ suf }\OperatorTok{=}\NormalTok{ ans }\OperatorTok{=}\NormalTok{ V}\OperatorTok{;} \OperatorTok{\}}
          \DataTypeTok{void}\NormalTok{ ret}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ v}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ len}\OperatorTok{)\{}
              \ControlFlowTok{if}\OperatorTok{(}\NormalTok{v }\OperatorTok{\textless{}=} \DecValTok{0}\OperatorTok{)}\NormalTok{ suf }\OperatorTok{=}\NormalTok{ per }\OperatorTok{=}\NormalTok{ ans }\OperatorTok{=}\NormalTok{ v}\OperatorTok{,}\NormalTok{ sum }\OperatorTok{=}\NormalTok{ v }\OperatorTok{*}\NormalTok{ len}\OperatorTok{;} \CommentTok{// changed \textasciigrave{}sum = v\textasciigrave{} to \textasciigrave{}sum = v * len\textasciigrave{}.}
              \ControlFlowTok{else}\NormalTok{       sum }\OperatorTok{=}\NormalTok{ suf }\OperatorTok{=}\NormalTok{ per }\OperatorTok{=}\NormalTok{ ans }\OperatorTok{=}\NormalTok{ v }\OperatorTok{*}\NormalTok{ len}\OperatorTok{;}
          \OperatorTok{\}}
          \DataTypeTok{void}\NormalTok{ rev}\OperatorTok{()} \OperatorTok{\{}\NormalTok{ swap}\OperatorTok{(}\NormalTok{per}\OperatorTok{,}\NormalTok{ suf}\OperatorTok{);} \OperatorTok{\}}
          \DataTypeTok{data\_t} \KeywordTok{operator} \OperatorTok{+} \OperatorTok{(}\AttributeTok{const} \DataTypeTok{data\_t} \OperatorTok{\&}\NormalTok{ B}\OperatorTok{)} \OperatorTok{\{}
              \DataTypeTok{data\_t}\NormalTok{ A }\OperatorTok{=} \OperatorTok{*}\KeywordTok{this}\OperatorTok{,}\NormalTok{ res}\OperatorTok{;}
  \NormalTok{            res}\OperatorTok{.}\NormalTok{sum }\OperatorTok{=}\NormalTok{ A}\OperatorTok{.}\NormalTok{sum }\OperatorTok{+}\NormalTok{ B}\OperatorTok{.}\NormalTok{sum}\OperatorTok{;}
  \NormalTok{            res}\OperatorTok{.}\NormalTok{per }\OperatorTok{=}\NormalTok{ max}\OperatorTok{(}\NormalTok{A}\OperatorTok{.}\NormalTok{per}\OperatorTok{,}\NormalTok{ A}\OperatorTok{.}\NormalTok{sum }\OperatorTok{+}\NormalTok{ B}\OperatorTok{.}\NormalTok{per}\OperatorTok{);}
  \NormalTok{            res}\OperatorTok{.}\NormalTok{suf }\OperatorTok{=}\NormalTok{ max}\OperatorTok{(}\NormalTok{A}\OperatorTok{.}\NormalTok{suf }\OperatorTok{+}\NormalTok{ B}\OperatorTok{.}\NormalTok{sum}\OperatorTok{,}\NormalTok{ B}\OperatorTok{.}\NormalTok{suf}\OperatorTok{);}
  \NormalTok{            res}\OperatorTok{.}\NormalTok{ans }\OperatorTok{=}\NormalTok{ max}\OperatorTok{(}\NormalTok{max}\OperatorTok{(}\NormalTok{A}\OperatorTok{.}\NormalTok{ans}\OperatorTok{,}\NormalTok{ B}\OperatorTok{.}\NormalTok{ans}\OperatorTok{),}\NormalTok{ A}\OperatorTok{.}\NormalTok{suf }\OperatorTok{+}\NormalTok{ B}\OperatorTok{.}\NormalTok{per}\OperatorTok{);}
              \ControlFlowTok{return}\NormalTok{ res}\OperatorTok{;}
          \OperatorTok{\}}
      \OperatorTok{\};}
  
      \DataTypeTok{int}\NormalTok{ ch}\OperatorTok{[}\NormalTok{\_}\OperatorTok{][}\DecValTok{2}\OperatorTok{],}\NormalTok{ fa}\OperatorTok{[}\NormalTok{\_}\OperatorTok{],}\NormalTok{ si}\OperatorTok{[}\NormalTok{\_}\OperatorTok{],}\NormalTok{ rt}\OperatorTok{,}\NormalTok{ tot}\OperatorTok{;} \DataTypeTok{data\_t}\NormalTok{ v}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
      \DataTypeTok{short}\NormalTok{ val}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
      \DataTypeTok{bool}\NormalTok{ tag\_rev}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];} \DataTypeTok{short}\NormalTok{ tag\_ret}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
      \PreprocessorTok{\#define ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{)}\PreprocessorTok{ }\OperatorTok{(}\NormalTok{ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\DecValTok{0}\OperatorTok{])}
      \PreprocessorTok{\#define rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{)}\PreprocessorTok{ }\OperatorTok{(}\NormalTok{ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\DecValTok{1}\OperatorTok{])}
      \PreprocessorTok{\#define maintain}\OperatorTok{(}\NormalTok{o}\OperatorTok{)}\PreprocessorTok{ }\OperatorTok{(}\NormalTok{si}\OperatorTok{[}\NormalTok{o}\OperatorTok{]}\PreprocessorTok{ }\OperatorTok{=}\PreprocessorTok{ }\NormalTok{si}\OperatorTok{[}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{)]}\PreprocessorTok{ }\OperatorTok{+}\PreprocessorTok{ }\NormalTok{si}\OperatorTok{[}\NormalTok{rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{)]}\PreprocessorTok{ }\OperatorTok{+}\PreprocessorTok{ }\DecValTok{1}\OperatorTok{,}\PreprocessorTok{ }\NormalTok{v}\OperatorTok{[}\NormalTok{o}\OperatorTok{]}\PreprocessorTok{ }\OperatorTok{=}\PreprocessorTok{ }\NormalTok{v}\OperatorTok{[}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{)]}\PreprocessorTok{ }\OperatorTok{+}\PreprocessorTok{ }\DataTypeTok{data\_t}\OperatorTok{(}\NormalTok{val}\OperatorTok{[}\NormalTok{o}\OperatorTok{])}\PreprocessorTok{ }\OperatorTok{+}\PreprocessorTok{ }\NormalTok{v}\OperatorTok{[}\NormalTok{rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{)])}
      \PreprocessorTok{\#define get}\OperatorTok{(}\NormalTok{o}\OperatorTok{)}\PreprocessorTok{ }\OperatorTok{(}\NormalTok{ch}\OperatorTok{[}\NormalTok{fa}\OperatorTok{[}\NormalTok{o}\OperatorTok{]][}\DecValTok{1}\OperatorTok{]}\PreprocessorTok{ }\OperatorTok{==}\PreprocessorTok{ }\NormalTok{o}\OperatorTok{)}
      \DataTypeTok{int}\NormalTok{ make}\OperatorTok{()\{}
          \ControlFlowTok{if}\OperatorTok{(!}\NormalTok{Mem}\OperatorTok{.}\NormalTok{empty}\OperatorTok{())\{}
              \DataTypeTok{int}\NormalTok{ o }\OperatorTok{=}\NormalTok{ Mem}\OperatorTok{.}\NormalTok{top}\OperatorTok{();}\NormalTok{ Mem}\OperatorTok{.}\NormalTok{pop}\OperatorTok{();}
  \NormalTok{            tag\_ret}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{=}\NormalTok{ none}\OperatorTok{;}
  \NormalTok{            tag\_rev}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{=} \KeywordTok{false}\OperatorTok{;}
  \NormalTok{            ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\DecValTok{1}\OperatorTok{]} \OperatorTok{=}\NormalTok{ ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\DecValTok{0}\OperatorTok{]} \OperatorTok{=}\NormalTok{ si}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{=}\NormalTok{ val}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{=}\NormalTok{ fa}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{=} \DecValTok{0}\OperatorTok{;}
  \NormalTok{            v}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{=} \DataTypeTok{data\_t}\OperatorTok{();}
              \ControlFlowTok{return}\NormalTok{ o}\OperatorTok{;}
          \OperatorTok{\}} \ControlFlowTok{else} \OperatorTok{\{}
  \NormalTok{            tot}\OperatorTok{++;}
  \NormalTok{            tag\_ret}\OperatorTok{[}\NormalTok{tot}\OperatorTok{]} \OperatorTok{=}\NormalTok{ none}\OperatorTok{;}
  \NormalTok{            tag\_rev}\OperatorTok{[}\NormalTok{tot}\OperatorTok{]} \OperatorTok{=} \KeywordTok{false}\OperatorTok{;}
  \NormalTok{            ch}\OperatorTok{[}\NormalTok{tot}\OperatorTok{][}\DecValTok{1}\OperatorTok{]} \OperatorTok{=}\NormalTok{ ch}\OperatorTok{[}\NormalTok{tot}\OperatorTok{][}\DecValTok{0}\OperatorTok{]} \OperatorTok{=}\NormalTok{ si}\OperatorTok{[}\NormalTok{tot}\OperatorTok{]} \OperatorTok{=}\NormalTok{ val}\OperatorTok{[}\NormalTok{tot}\OperatorTok{]} \OperatorTok{=}\NormalTok{ fa}\OperatorTok{[}\NormalTok{tot}\OperatorTok{]} \OperatorTok{=} \DecValTok{0}\OperatorTok{;}
  \NormalTok{            v}\OperatorTok{[}\NormalTok{tot}\OperatorTok{]} \OperatorTok{=} \DataTypeTok{data\_t}\OperatorTok{();}
              \ControlFlowTok{return}\NormalTok{ tot}\OperatorTok{;}
          \OperatorTok{\}}
          
      \OperatorTok{\}}
      \DataTypeTok{void}\NormalTok{ recycle}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{)\{} \ControlFlowTok{if}\OperatorTok{(!}\NormalTok{o}\OperatorTok{)} \ControlFlowTok{return} \OperatorTok{;}\NormalTok{ Mem}\OperatorTok{.}\NormalTok{push}\OperatorTok{(}\NormalTok{o}\OperatorTok{);}\NormalTok{ recycle}\OperatorTok{(}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{));}\NormalTok{ recycle}\OperatorTok{(}\NormalTok{rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{));} \OperatorTok{\}}
  
      \DataTypeTok{Splay\_t}\OperatorTok{()} \OperatorTok{\{}\NormalTok{ rt }\OperatorTok{=}\NormalTok{ tot }\OperatorTok{=} \DecValTok{0}\OperatorTok{;} \OperatorTok{\}}
      \DataTypeTok{void}\NormalTok{ tar\_rev}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{)\{}
  \NormalTok{        v}\OperatorTok{[}\NormalTok{o}\OperatorTok{].}\NormalTok{rev}\OperatorTok{();}
  \NormalTok{        swap}\OperatorTok{(}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{),}\NormalTok{ rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{));}
  \NormalTok{        tag\_rev}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{\^{}=} \DecValTok{1}\OperatorTok{;}
      \OperatorTok{\}}
      \DataTypeTok{void}\NormalTok{ tar\_ret}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ V}\OperatorTok{)\{}
  \NormalTok{        v}\OperatorTok{[}\NormalTok{o}\OperatorTok{].}\NormalTok{ret}\OperatorTok{(}\NormalTok{V}\OperatorTok{,}\NormalTok{ si}\OperatorTok{[}\NormalTok{o}\OperatorTok{]);}
  \NormalTok{        val}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{=}\NormalTok{ V}\OperatorTok{;}
  \NormalTok{        tag\_ret}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{=}\NormalTok{ V}\OperatorTok{;}
      \OperatorTok{\}}
      \DataTypeTok{void}\NormalTok{ push}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{)\{}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{tag\_ret}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{!=}\NormalTok{ none}\OperatorTok{)\{}
              \ControlFlowTok{if}\OperatorTok{(}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{))}\NormalTok{ tar\_ret}\OperatorTok{(}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{),}\NormalTok{ tag\_ret}\OperatorTok{[}\NormalTok{o}\OperatorTok{]);}
              \ControlFlowTok{if}\OperatorTok{(}\NormalTok{rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{))}\NormalTok{ tar\_ret}\OperatorTok{(}\NormalTok{rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{),}\NormalTok{ tag\_ret}\OperatorTok{[}\NormalTok{o}\OperatorTok{]);}
  \NormalTok{            tag\_ret}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{=}\NormalTok{ none}\OperatorTok{;}
          \OperatorTok{\}}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{tag\_rev}\OperatorTok{[}\NormalTok{o}\OperatorTok{])\{}
              \ControlFlowTok{if}\OperatorTok{(}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{))}\NormalTok{tar\_rev}\OperatorTok{(}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{));}
              \ControlFlowTok{if}\OperatorTok{(}\NormalTok{rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{))}\NormalTok{tar\_rev}\OperatorTok{(}\NormalTok{rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{));}
  \NormalTok{            tag\_rev}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{=} \DecValTok{0}\OperatorTok{;}
          \OperatorTok{\}}
      \OperatorTok{\}}
      \DataTypeTok{void}\NormalTok{ rotate}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{)\{}
          \DataTypeTok{int}\NormalTok{ p }\OperatorTok{=}\NormalTok{ fa}\OperatorTok{[}\NormalTok{o}\OperatorTok{],}\NormalTok{ gp }\OperatorTok{=}\NormalTok{ fa}\OperatorTok{[}\NormalTok{fa}\OperatorTok{[}\NormalTok{o}\OperatorTok{]],}\NormalTok{ chk }\OperatorTok{=}\NormalTok{ get}\OperatorTok{(}\NormalTok{o}\OperatorTok{);}
  \NormalTok{        ch}\OperatorTok{[}\NormalTok{p}\OperatorTok{][}\NormalTok{chk}\OperatorTok{]} \OperatorTok{=}\NormalTok{ ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\NormalTok{chk }\OperatorTok{\^{}} \DecValTok{1}\OperatorTok{];}\NormalTok{ fa}\OperatorTok{[}\NormalTok{ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\NormalTok{chk }\OperatorTok{\^{}} \DecValTok{1}\OperatorTok{]]} \OperatorTok{=}\NormalTok{ p}\OperatorTok{;}
  \NormalTok{        ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\NormalTok{chk }\OperatorTok{\^{}} \DecValTok{1}\OperatorTok{]} \OperatorTok{=}\NormalTok{ p}\OperatorTok{;}\NormalTok{ fa}\OperatorTok{[}\NormalTok{p}\OperatorTok{]} \OperatorTok{=}\NormalTok{ o}\OperatorTok{;}
  \NormalTok{        fa}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{=}\NormalTok{ gp}\OperatorTok{;} \ControlFlowTok{if}\OperatorTok{(}\NormalTok{gp}\OperatorTok{)}\NormalTok{ ch}\OperatorTok{[}\NormalTok{gp}\OperatorTok{][}\NormalTok{ch}\OperatorTok{[}\NormalTok{gp}\OperatorTok{][}\DecValTok{1}\OperatorTok{]} \OperatorTok{==}\NormalTok{ p}\OperatorTok{]} \OperatorTok{=}\NormalTok{ o}\OperatorTok{;}
  \NormalTok{        maintain}\OperatorTok{(}\NormalTok{p}\OperatorTok{);}\NormalTok{ maintain}\OperatorTok{(}\NormalTok{o}\OperatorTok{);}
      \OperatorTok{\}}
      \DataTypeTok{void}\NormalTok{ splay}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ tgp }\OperatorTok{=} \DecValTok{0}\OperatorTok{)\{}
          \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ f }\OperatorTok{=}\NormalTok{ fa}\OperatorTok{[}\NormalTok{o}\OperatorTok{];}\NormalTok{ f }\OperatorTok{=}\NormalTok{ fa}\OperatorTok{[}\NormalTok{o}\OperatorTok{],}\NormalTok{ f }\OperatorTok{!=}\NormalTok{ tgp}\OperatorTok{;}\NormalTok{ rotate}\OperatorTok{(}\NormalTok{o}\OperatorTok{))\{}
  \NormalTok{            push}\OperatorTok{(}\NormalTok{f}\OperatorTok{);}\NormalTok{ push}\OperatorTok{(}\NormalTok{o}\OperatorTok{);}
              \ControlFlowTok{if}\OperatorTok{(}\NormalTok{fa}\OperatorTok{[}\NormalTok{f}\OperatorTok{]} \OperatorTok{!=}\NormalTok{ tgp}\OperatorTok{)}\NormalTok{ rotate}\OperatorTok{(}\NormalTok{get}\OperatorTok{(}\NormalTok{o}\OperatorTok{)} \OperatorTok{==}\NormalTok{ get}\OperatorTok{(}\NormalTok{f}\OperatorTok{)} \OperatorTok{?}\NormalTok{ f }\OperatorTok{:}\NormalTok{ o}\OperatorTok{);}
          \OperatorTok{\}}
          \ControlFlowTok{if}\OperatorTok{(!}\NormalTok{tgp}\OperatorTok{)}\NormalTok{ rt }\OperatorTok{=}\NormalTok{ o}\OperatorTok{;} \CommentTok{// changed \textasciigrave{}rt = tgp\textasciigrave{}  to \textasciigrave{}rt = o\textasciigrave{}.}
      \OperatorTok{\}}
      \DataTypeTok{void}\NormalTok{ build\_sub}\OperatorTok{(}\DataTypeTok{int} \OperatorTok{\&}\NormalTok{o}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ f}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ L}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ R}\OperatorTok{,} \DataTypeTok{int} \OperatorTok{*}\NormalTok{A}\OperatorTok{)\{}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{L }\OperatorTok{\textgreater{}}\NormalTok{ R}\OperatorTok{)} \ControlFlowTok{return} \OperatorTok{;}
          \DataTypeTok{int}\NormalTok{ mid }\OperatorTok{=} \OperatorTok{(}\NormalTok{L }\OperatorTok{+}\NormalTok{ R}\OperatorTok{)} \OperatorTok{\textgreater{}\textgreater{}} \DecValTok{1}\OperatorTok{;}
  \NormalTok{        o }\OperatorTok{=}\NormalTok{ make}\OperatorTok{();}\NormalTok{ fa}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{=}\NormalTok{ f}\OperatorTok{;}\NormalTok{ val}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{=}\NormalTok{ A}\OperatorTok{[}\NormalTok{mid}\OperatorTok{];}\NormalTok{ v}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{=} \DataTypeTok{data\_t}\OperatorTok{(}\NormalTok{A}\OperatorTok{[}\NormalTok{mid}\OperatorTok{]);}\NormalTok{ si}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{=} \DecValTok{1}\OperatorTok{;}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{L }\OperatorTok{==}\NormalTok{ R}\OperatorTok{)} \ControlFlowTok{return} \OperatorTok{;}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{L }\OperatorTok{\textless{}=}\NormalTok{ mid }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{)}\NormalTok{ build\_sub}\OperatorTok{(}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{),}\NormalTok{ o}\OperatorTok{,}\NormalTok{ L}\OperatorTok{,}\NormalTok{ mid }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{,}\NormalTok{ A}\OperatorTok{);}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{mid }\OperatorTok{+} \DecValTok{1} \OperatorTok{\textless{}=}\NormalTok{ R}\OperatorTok{)}\NormalTok{ build\_sub}\OperatorTok{(}\NormalTok{rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{),}\NormalTok{ o}\OperatorTok{,}\NormalTok{ mid }\OperatorTok{+} \DecValTok{1}\OperatorTok{,}\NormalTok{ R}\OperatorTok{,}\NormalTok{ A}\OperatorTok{);}
  \NormalTok{        maintain}\OperatorTok{(}\NormalTok{o}\OperatorTok{);}
      \OperatorTok{\}} 
      \DataTypeTok{void}\NormalTok{ build}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ L}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ R}\OperatorTok{,} \DataTypeTok{int} \OperatorTok{*}\NormalTok{A}\OperatorTok{)\{} 
  \NormalTok{        build\_sub}\OperatorTok{(}\NormalTok{rt}\OperatorTok{,} \DecValTok{0}\OperatorTok{,}\NormalTok{ L}\OperatorTok{,}\NormalTok{ R}\OperatorTok{,}\NormalTok{ A}\OperatorTok{);} 
      \OperatorTok{\}}
      
      \DataTypeTok{int}\NormalTok{ insert}\OperatorTok{(}\DataTypeTok{int} \OperatorTok{\&}\NormalTok{o}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ f}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ target}\OperatorTok{,} \DataTypeTok{int} \OperatorTok{*}\NormalTok{A}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ len}\OperatorTok{)\{}
          \ControlFlowTok{if}\OperatorTok{(!}\NormalTok{o}\OperatorTok{)} \ControlFlowTok{return}\NormalTok{ build\_sub}\OperatorTok{(}\NormalTok{o}\OperatorTok{,}\NormalTok{ f}\OperatorTok{,} \DecValTok{1}\OperatorTok{,}\NormalTok{ len}\OperatorTok{,}\NormalTok{ A}\OperatorTok{),}\NormalTok{ o}\OperatorTok{;}
          \DataTypeTok{int}\NormalTok{ r }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}\NormalTok{ push}\OperatorTok{(}\NormalTok{o}\OperatorTok{);}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{target }\OperatorTok{\textless{}=}\NormalTok{ si}\OperatorTok{[}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{)])}\NormalTok{ r }\OperatorTok{=}\NormalTok{ insert}\OperatorTok{(}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{),}\NormalTok{ o}\OperatorTok{,}\NormalTok{ target}\OperatorTok{,}\NormalTok{ A}\OperatorTok{,}\NormalTok{ len}\OperatorTok{);}
          \ControlFlowTok{else}\NormalTok{ r }\OperatorTok{=}\NormalTok{ insert}\OperatorTok{(}\NormalTok{rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{),}\NormalTok{ o}\OperatorTok{,}\NormalTok{ target }\OperatorTok{{-}}\NormalTok{ si}\OperatorTok{[}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{)]} \OperatorTok{{-}} \DecValTok{1}\OperatorTok{,}\NormalTok{ A}\OperatorTok{,}\NormalTok{ len}\OperatorTok{);}
  \NormalTok{        maintain}\OperatorTok{(}\NormalTok{o}\OperatorTok{);} \ControlFlowTok{return}\NormalTok{ r}\OperatorTok{;}
      \OperatorTok{\}} \DataTypeTok{void}\NormalTok{ insert}\OperatorTok{(}\DataTypeTok{int} \OperatorTok{*}\NormalTok{A}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ pos}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ len}\OperatorTok{)} \OperatorTok{\{} \DataTypeTok{int}\NormalTok{ r }\OperatorTok{=}\NormalTok{ insert}\OperatorTok{(}\NormalTok{rt}\OperatorTok{,} \DecValTok{0}\OperatorTok{,}\NormalTok{ pos}\OperatorTok{,}\NormalTok{ A}\OperatorTok{,}\NormalTok{ len}\OperatorTok{);}\NormalTok{ splay}\OperatorTok{(}\NormalTok{r}\OperatorTok{);} \OperatorTok{\}}
  
      \DataTypeTok{int}\NormalTok{ find}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ k}\OperatorTok{)\{}
  \NormalTok{        push}\OperatorTok{(}\NormalTok{o}\OperatorTok{);}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{k }\OperatorTok{\textless{}=}\NormalTok{ si}\OperatorTok{[}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{)])} \ControlFlowTok{return}\NormalTok{ find}\OperatorTok{(}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{),}\NormalTok{ k}\OperatorTok{);}
          \ControlFlowTok{else} \OperatorTok{\{}
              \ControlFlowTok{if}\OperatorTok{(}\NormalTok{k }\OperatorTok{\textless{}=}\NormalTok{ si}\OperatorTok{[}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{)]} \OperatorTok{+} \DecValTok{1}\OperatorTok{)} \ControlFlowTok{return}\NormalTok{ o}\OperatorTok{;}
              \ControlFlowTok{else} \ControlFlowTok{return}\NormalTok{ find}\OperatorTok{(}\NormalTok{rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{),}\NormalTok{ k }\OperatorTok{{-}} \DecValTok{1} \OperatorTok{{-}}\NormalTok{ si}\OperatorTok{[}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{)]);}
          \OperatorTok{\}}
      \OperatorTok{\}}
      \DataTypeTok{void}\NormalTok{ Make\_Range}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ L}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ R}\OperatorTok{)\{}
          \DataTypeTok{int}\NormalTok{ per }\OperatorTok{=}\NormalTok{ find}\OperatorTok{(}\NormalTok{rt}\OperatorTok{,}\NormalTok{ L }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{),}\NormalTok{ suf }\OperatorTok{=}\NormalTok{ find}\OperatorTok{(}\NormalTok{rt}\OperatorTok{,}\NormalTok{ R }\OperatorTok{+} \DecValTok{1}\OperatorTok{);}
  \NormalTok{        splay}\OperatorTok{(}\NormalTok{per}\OperatorTok{);}\NormalTok{ splay}\OperatorTok{(}\NormalTok{suf}\OperatorTok{,}\NormalTok{ rt}\OperatorTok{);}
      \OperatorTok{\}}
      \DataTypeTok{void}\NormalTok{ erase}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ L}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ R}\OperatorTok{)\{}
  \NormalTok{        Make\_Range}\OperatorTok{(}\NormalTok{L}\OperatorTok{,}\NormalTok{ R}\OperatorTok{);}
          \DataTypeTok{int} \OperatorTok{\&}\NormalTok{ target }\OperatorTok{=}\NormalTok{ ls}\OperatorTok{(}\NormalTok{rs}\OperatorTok{(}\NormalTok{rt}\OperatorTok{));}
  \NormalTok{        recycle}\OperatorTok{(}\NormalTok{target}\OperatorTok{);}\NormalTok{ target }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}\NormalTok{ maintain}\OperatorTok{(}\NormalTok{rs}\OperatorTok{(}\NormalTok{rt}\OperatorTok{));}\NormalTok{ maintain}\OperatorTok{(}\NormalTok{rt}\OperatorTok{);}
      \OperatorTok{\}}
      \DataTypeTok{void}\NormalTok{ rev}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ L}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ R}\OperatorTok{)\{}
  \NormalTok{        Make\_Range}\OperatorTok{(}\NormalTok{L}\OperatorTok{,}\NormalTok{ R}\OperatorTok{);}
          \DataTypeTok{int} \OperatorTok{\&}\NormalTok{ target }\OperatorTok{=}\NormalTok{ ls}\OperatorTok{(}\NormalTok{rs}\OperatorTok{(}\NormalTok{rt}\OperatorTok{));}
  \NormalTok{        tar\_rev}\OperatorTok{(}\NormalTok{target}\OperatorTok{);}\NormalTok{ maintain}\OperatorTok{(}\NormalTok{rs}\OperatorTok{(}\NormalTok{rt}\OperatorTok{));}\NormalTok{ maintain}\OperatorTok{(}\NormalTok{rt}\OperatorTok{);}
      \OperatorTok{\}}
      \DataTypeTok{void}\NormalTok{ ret}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ L}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ R}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ V}\OperatorTok{)\{}
  \NormalTok{        Make\_Range}\OperatorTok{(}\NormalTok{L}\OperatorTok{,}\NormalTok{ R}\OperatorTok{);}
          \DataTypeTok{int} \OperatorTok{\&}\NormalTok{ target }\OperatorTok{=}\NormalTok{ ls}\OperatorTok{(}\NormalTok{rs}\OperatorTok{(}\NormalTok{rt}\OperatorTok{));}
  \NormalTok{        tar\_ret}\OperatorTok{(}\NormalTok{target}\OperatorTok{,}\NormalTok{ V}\OperatorTok{);}\NormalTok{ maintain}\OperatorTok{(}\NormalTok{rs}\OperatorTok{(}\NormalTok{rt}\OperatorTok{));}\NormalTok{ maintain}\OperatorTok{(}\NormalTok{rt}\OperatorTok{);}
      \OperatorTok{\}}
      \DataTypeTok{int}\NormalTok{ query\_sum}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ L}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ R}\OperatorTok{)\{}
  \NormalTok{        Make\_Range}\OperatorTok{(}\NormalTok{L}\OperatorTok{,}\NormalTok{ R}\OperatorTok{);}
          \DataTypeTok{int} \OperatorTok{\&}\NormalTok{ target }\OperatorTok{=}\NormalTok{ ls}\OperatorTok{(}\NormalTok{rs}\OperatorTok{(}\NormalTok{rt}\OperatorTok{));}
          \ControlFlowTok{return}\NormalTok{ v}\OperatorTok{[}\NormalTok{target}\OperatorTok{].}\NormalTok{sum}\OperatorTok{;}
      \OperatorTok{\}}
      \DataTypeTok{int}\NormalTok{ query\_ans}\OperatorTok{()\{}
          \ControlFlowTok{return}\NormalTok{ v}\OperatorTok{[}\NormalTok{rt}\OperatorTok{].}\NormalTok{ans}\OperatorTok{;}
      \OperatorTok{\}}
     \DataTypeTok{void}\NormalTok{ dfs}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o }\OperatorTok{=} \OperatorTok{{-}}\DecValTok{1}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ indent }\OperatorTok{=} \DecValTok{0}\OperatorTok{)\{}
      \ControlFlowTok{if}\OperatorTok{(}\NormalTok{o }\OperatorTok{==} \OperatorTok{{-}}\DecValTok{1}\OperatorTok{)}\NormalTok{ o }\OperatorTok{=}\NormalTok{ rt}\OperatorTok{;}
      \ControlFlowTok{if}\OperatorTok{(!}\NormalTok{o}\OperatorTok{)}  \OperatorTok{\{}\NormalTok{ cerr }\OperatorTok{\textless{}\textless{}}\NormalTok{ string}\OperatorTok{(}\NormalTok{indent}\OperatorTok{,} \CharTok{\textquotesingle{} \textquotesingle{}}\OperatorTok{)} \OperatorTok{\textless{}\textless{}} \StringTok{"\# null"} \OperatorTok{\textless{}\textless{}}\NormalTok{ endl}\OperatorTok{;} \ControlFlowTok{return} \OperatorTok{;} \OperatorTok{\}}
  \NormalTok{    push}\OperatorTok{(}\NormalTok{o}\OperatorTok{);}
      \ControlFlowTok{if}\OperatorTok{(}\NormalTok{rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{))} \OtherTok{assert}\OperatorTok{(}\NormalTok{fa}\OperatorTok{[}\NormalTok{rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{)]} \OperatorTok{==}\NormalTok{ o}\OperatorTok{);}\NormalTok{ dfs}\OperatorTok{(}\NormalTok{rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{),}\NormalTok{ indent }\OperatorTok{+} \DecValTok{10}\OperatorTok{);}
  \NormalTok{    cerr }\OperatorTok{\textless{}\textless{}}\NormalTok{ string}\OperatorTok{(}\NormalTok{indent}\OperatorTok{,} \CharTok{\textquotesingle{} \textquotesingle{}}\OperatorTok{)} \OperatorTok{\textless{}\textless{}} \StringTok{"\# v="} \OperatorTok{\textless{}\textless{}}\NormalTok{ val}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{\textless{}\textless{}} \StringTok{" ans="} \OperatorTok{\textless{}\textless{}}\NormalTok{ v}\OperatorTok{[}\NormalTok{o}\OperatorTok{].}\NormalTok{ans }\OperatorTok{\textless{}\textless{}}\NormalTok{ endl}\OperatorTok{;}
      \ControlFlowTok{if}\OperatorTok{(}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{))} \OtherTok{assert}\OperatorTok{(}\NormalTok{fa}\OperatorTok{[}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{)]} \OperatorTok{==}\NormalTok{ o}\OperatorTok{);}\NormalTok{ dfs}\OperatorTok{(}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{),}\NormalTok{ indent }\OperatorTok{+} \DecValTok{10}\OperatorTok{);}
      \OperatorTok{\}}
  \OperatorTok{\};}
  \DataTypeTok{Splay\_t}\NormalTok{ t}\OperatorTok{;}
  \DataTypeTok{int}\NormalTok{ A}\OperatorTok{[}\NormalTok{\_}\OperatorTok{],}\NormalTok{ n}\OperatorTok{,}\NormalTok{ m}\OperatorTok{;}
  \DataTypeTok{char}\NormalTok{ opt}\OperatorTok{[}\DecValTok{100}\OperatorTok{];}
  \DataTypeTok{int}\NormalTok{ main}\OperatorTok{()\{} \CommentTok{//freopen(".in", "r", stdin); freopen(".out", "w", stdout);}
  \NormalTok{    Read}\OperatorTok{(}\NormalTok{n}\OperatorTok{)(}\NormalTok{m}\OperatorTok{);}\NormalTok{ n }\OperatorTok{+=} \DecValTok{2}\OperatorTok{;}\NormalTok{ rep}\OperatorTok{(}\NormalTok{i}\OperatorTok{,} \DecValTok{2}\OperatorTok{,}\NormalTok{ n }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{)}\NormalTok{ Read}\OperatorTok{(}\NormalTok{A}\OperatorTok{[}\NormalTok{i}\OperatorTok{]);} 
  \NormalTok{    A}\OperatorTok{[}\DecValTok{1}\OperatorTok{]} \OperatorTok{=}\NormalTok{ A}\OperatorTok{[}\NormalTok{n}\OperatorTok{]} \OperatorTok{=}\NormalTok{ none}\OperatorTok{;} \CommentTok{// added line \textasciigrave{}A[1] = A[n] = {-}inf\textasciigrave{}. }
  \NormalTok{    t}\OperatorTok{.}\NormalTok{build}\OperatorTok{(}\DecValTok{1}\OperatorTok{,}\NormalTok{ n}\OperatorTok{,}\NormalTok{ A}\OperatorTok{);}
  \NormalTok{    rep}\OperatorTok{(}\NormalTok{tt}\OperatorTok{,} \DecValTok{1}\OperatorTok{,}\NormalTok{ m}\OperatorTok{)\{}
  \NormalTok{        scanf}\OperatorTok{(}\StringTok{"}\SpecialCharTok{\%s}\StringTok{"}\OperatorTok{,}\NormalTok{ opt}\OperatorTok{);} \DataTypeTok{char}\NormalTok{ sign0 }\OperatorTok{=}\NormalTok{ opt}\OperatorTok{[}\DecValTok{0}\OperatorTok{],}\NormalTok{ sign1 }\OperatorTok{=}\NormalTok{ opt}\OperatorTok{[}\DecValTok{3}\OperatorTok{];}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{sign0 }\OperatorTok{==} \CharTok{\textquotesingle{}I\textquotesingle{}}\OperatorTok{)} \OperatorTok{\{} \CommentTok{// Insert a sequence.}
              \DataTypeTok{int}\NormalTok{ pos}\OperatorTok{,}\NormalTok{ tot}\OperatorTok{;}\NormalTok{ Read}\OperatorTok{(}\NormalTok{pos}\OperatorTok{)(}\NormalTok{tot}\OperatorTok{);}\NormalTok{ rep}\OperatorTok{(}\NormalTok{i}\OperatorTok{,} \DecValTok{1}\OperatorTok{,}\NormalTok{ tot}\OperatorTok{)}\NormalTok{ Read}\OperatorTok{(}\NormalTok{A}\OperatorTok{[}\NormalTok{i}\OperatorTok{]);}\NormalTok{ pos}\OperatorTok{++;}
  \NormalTok{            t}\OperatorTok{.}\NormalTok{insert}\OperatorTok{(}\NormalTok{A}\OperatorTok{,}\NormalTok{ pos}\OperatorTok{,}\NormalTok{ tot}\OperatorTok{);}
          \OperatorTok{\}} \ControlFlowTok{else} \ControlFlowTok{if}\OperatorTok{(}\NormalTok{sign0 }\OperatorTok{==} \CharTok{\textquotesingle{}D\textquotesingle{}}\OperatorTok{)\{} \CommentTok{// Delete a sequence.}
              \DataTypeTok{int}\NormalTok{ pos}\OperatorTok{,}\NormalTok{ tot}\OperatorTok{;}\NormalTok{ Read}\OperatorTok{(}\NormalTok{pos}\OperatorTok{)(}\NormalTok{tot}\OperatorTok{);}\NormalTok{ pos}\OperatorTok{++;}
  \NormalTok{            t}\OperatorTok{.}\NormalTok{erase}\OperatorTok{(}\NormalTok{pos}\OperatorTok{,}\NormalTok{ pos }\OperatorTok{+}\NormalTok{ tot }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{);}
          \OperatorTok{\}} \ControlFlowTok{else} \ControlFlowTok{if}\OperatorTok{(}\NormalTok{sign0 }\OperatorTok{==} \CharTok{\textquotesingle{}R\textquotesingle{}}\OperatorTok{)\{} \CommentTok{// Reverse a sequence.}
              \DataTypeTok{int}\NormalTok{ pos}\OperatorTok{,}\NormalTok{ tot}\OperatorTok{;}\NormalTok{ Read}\OperatorTok{(}\NormalTok{pos}\OperatorTok{)(}\NormalTok{tot}\OperatorTok{);}\NormalTok{ pos}\OperatorTok{++;}
  \NormalTok{            t}\OperatorTok{.}\NormalTok{rev}\OperatorTok{(}\NormalTok{pos}\OperatorTok{,}\NormalTok{ tot }\OperatorTok{+}\NormalTok{ pos }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{);}
          \OperatorTok{\}} \ControlFlowTok{else} \ControlFlowTok{if}\OperatorTok{(}\NormalTok{sign0 }\OperatorTok{==} \CharTok{\textquotesingle{}G\textquotesingle{}}\OperatorTok{)\{} \CommentTok{// calc the sum of sequence.}
              \DataTypeTok{int}\NormalTok{ pos}\OperatorTok{,}\NormalTok{ tot}\OperatorTok{;}\NormalTok{ Read}\OperatorTok{(}\NormalTok{pos}\OperatorTok{)(}\NormalTok{tot}\OperatorTok{);}\NormalTok{ pos}\OperatorTok{++;}
  \NormalTok{            printf}\OperatorTok{(}\StringTok{"}\SpecialCharTok{\%d\textbackslash{}n}\StringTok{"}\OperatorTok{,}\NormalTok{ t}\OperatorTok{.}\NormalTok{query\_sum}\OperatorTok{(}\NormalTok{pos}\OperatorTok{,}\NormalTok{ pos }\OperatorTok{+}\NormalTok{ tot }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{));}
          \OperatorTok{\}} \ControlFlowTok{else} \ControlFlowTok{if}\OperatorTok{(}\NormalTok{sign1 }\OperatorTok{==} \CharTok{\textquotesingle{}{-}\textquotesingle{}}\OperatorTok{)\{} \CommentTok{// calc the max sum sub sequence.}
  \NormalTok{            printf}\OperatorTok{(}\StringTok{"}\SpecialCharTok{\%d\textbackslash{}n}\StringTok{"}\OperatorTok{,}\NormalTok{ t}\OperatorTok{.}\NormalTok{query\_ans}\OperatorTok{());}
          \OperatorTok{\}} \ControlFlowTok{else} \OperatorTok{\{} \CommentTok{// make same on the sequence.}
              \DataTypeTok{int}\NormalTok{ pos}\OperatorTok{,}\NormalTok{ tot}\OperatorTok{,}\NormalTok{ c}\OperatorTok{;}\NormalTok{ Read}\OperatorTok{(}\NormalTok{pos}\OperatorTok{)(}\NormalTok{tot}\OperatorTok{)(}\NormalTok{c}\OperatorTok{);}\NormalTok{ pos}\OperatorTok{++;}
  \NormalTok{            t}\OperatorTok{.}\NormalTok{ret}\OperatorTok{(}\NormalTok{pos}\OperatorTok{,}\NormalTok{ pos }\OperatorTok{+}\NormalTok{ tot }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{,}\NormalTok{ c}\OperatorTok{);}
          \OperatorTok{\}}
      \OperatorTok{\}}
      \ControlFlowTok{return} \DecValTok{0}\OperatorTok{;}
  \OperatorTok{\}}
  \end{Highlighting}
  \end{Shaded}
  
  \subsubsection{非旋 Treap}\label{ux975eux65cb-treap}
  
  udp：2021/01/02. u1s1，这东西又短 又小 又快。\texttt{splay} 可能真的只有
  \texttt{LCT} 里面才出场了。
  
  \begin{Shaded}
  \begin{Highlighting}[]
  \DataTypeTok{int}\NormalTok{ rand}\OperatorTok{()\{}
      \AttributeTok{static} \DataTypeTok{int}\NormalTok{ seed }\OperatorTok{=} \DecValTok{1020031005}\OperatorTok{;}
      \ControlFlowTok{return}\NormalTok{ seed }\OperatorTok{=} \OperatorTok{((}\NormalTok{seed }\OperatorTok{+}\DecValTok{0}\BuiltInTok{ll}\OperatorTok{+} \DecValTok{20031006}\OperatorTok{)} \OperatorTok{\%} \DecValTok{998244353}\OperatorTok{);}
  \OperatorTok{\}}
  \KeywordTok{namespace}\NormalTok{ FHQ}\OperatorTok{\{}
      \AttributeTok{const} \DataTypeTok{int}\NormalTok{ \_ }\OperatorTok{=} \FloatTok{1e5} \OperatorTok{+} \DecValTok{100}\OperatorTok{;}
      \DataTypeTok{int}\NormalTok{ ch}\OperatorTok{[}\NormalTok{\_}\OperatorTok{][}\DecValTok{2}\OperatorTok{],}\NormalTok{ si}\OperatorTok{[}\NormalTok{\_}\OperatorTok{],}\NormalTok{ v}\OperatorTok{[}\NormalTok{\_}\OperatorTok{],}\NormalTok{ tot }\OperatorTok{=} \DecValTok{0}\OperatorTok{,}\NormalTok{ rt }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
      \PreprocessorTok{\#define ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{)}\PreprocessorTok{ }\OperatorTok{(}\NormalTok{ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\DecValTok{0}\OperatorTok{])}
      \PreprocessorTok{\#define rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{)}\PreprocessorTok{ }\OperatorTok{(}\NormalTok{ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\DecValTok{1}\OperatorTok{])}
      \PreprocessorTok{\#define maintain}\OperatorTok{(}\NormalTok{o}\OperatorTok{)}\PreprocessorTok{ }\OperatorTok{(}\DataTypeTok{void}\OperatorTok{)(}\NormalTok{si}\OperatorTok{[}\NormalTok{o}\OperatorTok{]}\PreprocessorTok{ }\OperatorTok{=}\PreprocessorTok{ }\NormalTok{si}\OperatorTok{[}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{)]}\PreprocessorTok{ }\OperatorTok{+}\PreprocessorTok{ }\NormalTok{si}\OperatorTok{[}\NormalTok{rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{)]}\PreprocessorTok{ }\OperatorTok{+}\PreprocessorTok{ }\DecValTok{1}\OperatorTok{)}
      \PreprocessorTok{\#define make}\OperatorTok{(}\NormalTok{vs}\OperatorTok{)}\PreprocessorTok{ }\OperatorTok{(++}\NormalTok{tot}\OperatorTok{,}\PreprocessorTok{ }\NormalTok{v}\OperatorTok{[}\NormalTok{tot}\OperatorTok{]}\PreprocessorTok{ }\OperatorTok{=}\PreprocessorTok{ }\NormalTok{vs}\OperatorTok{,}\PreprocessorTok{ }\NormalTok{si}\OperatorTok{[}\NormalTok{tot}\OperatorTok{]}\PreprocessorTok{ }\OperatorTok{=}\PreprocessorTok{ }\DecValTok{1}\OperatorTok{,}\PreprocessorTok{ }\NormalTok{ch}\OperatorTok{[}\NormalTok{tot}\OperatorTok{][}\DecValTok{0}\OperatorTok{]}\PreprocessorTok{ }\OperatorTok{=}\PreprocessorTok{ }\NormalTok{ch}\OperatorTok{[}\NormalTok{tot}\OperatorTok{][}\DecValTok{1}\OperatorTok{]}\PreprocessorTok{ }\OperatorTok{=}\PreprocessorTok{ }\DecValTok{0}\OperatorTok{,}\PreprocessorTok{ }\NormalTok{tot}\OperatorTok{)}
      \PreprocessorTok{\#define mg}\OperatorTok{(}\NormalTok{a}\OperatorTok{,}\PreprocessorTok{ }\NormalTok{b}\OperatorTok{,}\PreprocessorTok{ }\NormalTok{c}\OperatorTok{)}\PreprocessorTok{ }\OperatorTok{(}\NormalTok{merge}\OperatorTok{(}\NormalTok{merge}\OperatorTok{(}\NormalTok{a}\OperatorTok{,}\PreprocessorTok{ }\NormalTok{b}\OperatorTok{),}\PreprocessorTok{ }\NormalTok{c}\OperatorTok{))}
      \DataTypeTok{void}\NormalTok{ split}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ V}\OperatorTok{,} \DataTypeTok{int} \OperatorTok{\&}\NormalTok{x}\OperatorTok{,} \DataTypeTok{int} \OperatorTok{\&}\NormalTok{y}\OperatorTok{)\{}
          \ControlFlowTok{if}\OperatorTok{(!}\NormalTok{o}\OperatorTok{)} \ControlFlowTok{return} \OperatorTok{(}\DataTypeTok{void}\OperatorTok{)(}\NormalTok{x }\OperatorTok{=}\NormalTok{ y }\OperatorTok{=} \DecValTok{0}\OperatorTok{);}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{v}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{\textless{}=}\NormalTok{ V}\OperatorTok{)} \ControlFlowTok{return}\NormalTok{ x }\OperatorTok{=}\NormalTok{ o}\OperatorTok{,}\NormalTok{ split}\OperatorTok{(}\NormalTok{rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{),}\NormalTok{ V}\OperatorTok{,}\NormalTok{ rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{),}\NormalTok{ y}\OperatorTok{),}\NormalTok{ maintain}\OperatorTok{(}\NormalTok{o}\OperatorTok{);}
          \ControlFlowTok{return}\NormalTok{ y }\OperatorTok{=}\NormalTok{ o}\OperatorTok{,}\NormalTok{ split}\OperatorTok{(}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{),}\NormalTok{ V}\OperatorTok{,}\NormalTok{ x}\OperatorTok{,}\NormalTok{ ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{)),}\NormalTok{ maintain}\OperatorTok{(}\NormalTok{o}\OperatorTok{);}
      \OperatorTok{\}}
      \DataTypeTok{int}\NormalTok{ merge}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ x}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ y}\OperatorTok{)\{}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{x }\OperatorTok{==} \DecValTok{0} \OperatorTok{||}\NormalTok{ y }\OperatorTok{==} \DecValTok{0}\OperatorTok{)} \ControlFlowTok{return}\NormalTok{ x }\OperatorTok{+}\NormalTok{ y}\OperatorTok{;}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{rand}\OperatorTok{()} \OperatorTok{\%} \OperatorTok{(}\NormalTok{si}\OperatorTok{[}\NormalTok{x}\OperatorTok{]} \OperatorTok{+}\NormalTok{ si}\OperatorTok{[}\NormalTok{y}\OperatorTok{])} \OperatorTok{+} \DecValTok{1} \OperatorTok{\textless{}=}\NormalTok{ si}\OperatorTok{[}\NormalTok{x}\OperatorTok{])} \ControlFlowTok{return}\NormalTok{ rs}\OperatorTok{(}\NormalTok{x}\OperatorTok{)} \OperatorTok{=}\NormalTok{ merge}\OperatorTok{(}\NormalTok{rs}\OperatorTok{(}\NormalTok{x}\OperatorTok{),}\NormalTok{ y}\OperatorTok{),}\NormalTok{ maintain}\OperatorTok{(}\NormalTok{x}\OperatorTok{),}\NormalTok{ x}\OperatorTok{;}
          \ControlFlowTok{else} \ControlFlowTok{return}\NormalTok{ ls}\OperatorTok{(}\NormalTok{y}\OperatorTok{)} \OperatorTok{=}\NormalTok{ merge}\OperatorTok{(}\NormalTok{x}\OperatorTok{,}\NormalTok{ ls}\OperatorTok{(}\NormalTok{y}\OperatorTok{)),}\NormalTok{ maintain}\OperatorTok{(}\NormalTok{y}\OperatorTok{),}\NormalTok{ y}\OperatorTok{;}
      \OperatorTok{\}}
      \DataTypeTok{void}\NormalTok{ ins}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ x}\OperatorTok{)\{} \DataTypeTok{int}\NormalTok{ t0}\OperatorTok{,}\NormalTok{ t1 }\OperatorTok{=}\NormalTok{ make}\OperatorTok{(}\NormalTok{x}\OperatorTok{),}\NormalTok{ t2}\OperatorTok{;}\NormalTok{ split}\OperatorTok{(}\NormalTok{rt}\OperatorTok{,}\NormalTok{ x}\OperatorTok{,}\NormalTok{ t0}\OperatorTok{,}\NormalTok{ t2}\OperatorTok{);}\NormalTok{ rt }\OperatorTok{=}\NormalTok{ mg}\OperatorTok{(}\NormalTok{t0}\OperatorTok{,}\NormalTok{ t1}\OperatorTok{,}\NormalTok{ t2}\OperatorTok{);} \OperatorTok{\}}
      \DataTypeTok{void}\NormalTok{ erase}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ V}\OperatorTok{)\{} \DataTypeTok{int}\NormalTok{ x}\OperatorTok{,}\NormalTok{ y}\OperatorTok{,}\NormalTok{ z}\OperatorTok{;}\NormalTok{ split}\OperatorTok{(}\NormalTok{rt}\OperatorTok{,}\NormalTok{ V}\OperatorTok{,}\NormalTok{ y}\OperatorTok{,}\NormalTok{ z}\OperatorTok{);}\NormalTok{ split}\OperatorTok{(}\NormalTok{y}\OperatorTok{,}\NormalTok{ V }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{,}\NormalTok{ x}\OperatorTok{,}\NormalTok{ y}\OperatorTok{);}\NormalTok{ y }\OperatorTok{=}\NormalTok{ merge}\OperatorTok{(}\NormalTok{ls}\OperatorTok{(}\NormalTok{y}\OperatorTok{),}\NormalTok{ rs}\OperatorTok{(}\NormalTok{y}\OperatorTok{));}\NormalTok{ rt }\OperatorTok{=}\NormalTok{ mg}\OperatorTok{(}\NormalTok{x}\OperatorTok{,}\NormalTok{ y}\OperatorTok{,}\NormalTok{ z}\OperatorTok{);} \OperatorTok{\}}
      \DataTypeTok{int}\NormalTok{ rank}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ V}\OperatorTok{)} \OperatorTok{\{} \DataTypeTok{int}\NormalTok{ x}\OperatorTok{,}\NormalTok{ y}\OperatorTok{;}\NormalTok{ split}\OperatorTok{(}\NormalTok{rt}\OperatorTok{,}\NormalTok{ V }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{,}\NormalTok{ x}\OperatorTok{,}\NormalTok{ y}\OperatorTok{);} \DataTypeTok{int}\NormalTok{ res }\OperatorTok{=}\NormalTok{ si}\OperatorTok{[}\NormalTok{x}\OperatorTok{];}\NormalTok{ rt }\OperatorTok{=}\NormalTok{ merge}\OperatorTok{(}\NormalTok{x}\OperatorTok{,}\NormalTok{ y}\OperatorTok{);} \ControlFlowTok{return}\NormalTok{ res }\OperatorTok{+} \DecValTok{1}\OperatorTok{;} \OperatorTok{\}}
      \DataTypeTok{int}\NormalTok{ select}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ V}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ o }\OperatorTok{=} \OperatorTok{{-}}\DecValTok{1}\OperatorTok{)\{} \ControlFlowTok{if}\OperatorTok{(}\NormalTok{o }\OperatorTok{==} \OperatorTok{{-}}\DecValTok{1}\OperatorTok{)}\NormalTok{ o }\OperatorTok{=}\NormalTok{ rt}\OperatorTok{;} \ControlFlowTok{if}\OperatorTok{(}\NormalTok{V }\OperatorTok{\textless{}=}\NormalTok{ si}\OperatorTok{[}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{)])} \ControlFlowTok{return}\NormalTok{ select}\OperatorTok{(}\NormalTok{V}\OperatorTok{,}\NormalTok{ ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{));} \ControlFlowTok{else} \OperatorTok{\{} \ControlFlowTok{if}\OperatorTok{(}\NormalTok{V }\OperatorTok{\textless{}=}\NormalTok{ si}\OperatorTok{[}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{)]} \OperatorTok{+} \DecValTok{1}\OperatorTok{)} \ControlFlowTok{return}\NormalTok{ v}\OperatorTok{[}\NormalTok{o}\OperatorTok{];} \ControlFlowTok{else} \ControlFlowTok{return}\NormalTok{ select}\OperatorTok{(}\NormalTok{V }\OperatorTok{{-}}\NormalTok{ si}\OperatorTok{[}\NormalTok{ls}\OperatorTok{(}\NormalTok{o}\OperatorTok{)]} \OperatorTok{{-}} \DecValTok{1}\OperatorTok{,}\NormalTok{ rs}\OperatorTok{(}\NormalTok{o}\OperatorTok{));} \OperatorTok{\}} \OperatorTok{\}}
      \DataTypeTok{int}\NormalTok{ pred}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ V}\OperatorTok{)\{} \DataTypeTok{int}\NormalTok{ x}\OperatorTok{,}\NormalTok{ y}\OperatorTok{;}\NormalTok{ split}\OperatorTok{(}\NormalTok{rt}\OperatorTok{,}\NormalTok{ V }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{,}\NormalTok{ x}\OperatorTok{,}\NormalTok{ y}\OperatorTok{);} \DataTypeTok{int}\NormalTok{ res }\OperatorTok{=}\NormalTok{ select}\OperatorTok{(}\NormalTok{si}\OperatorTok{[}\NormalTok{x}\OperatorTok{],}\NormalTok{ x}\OperatorTok{);}\NormalTok{ rt }\OperatorTok{=}\NormalTok{ merge}\OperatorTok{(}\NormalTok{x}\OperatorTok{,}\NormalTok{ y}\OperatorTok{);} \ControlFlowTok{return}\NormalTok{ res}\OperatorTok{;} \OperatorTok{\}}
      \DataTypeTok{int}\NormalTok{ succ}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ V}\OperatorTok{)\{} \DataTypeTok{int}\NormalTok{ x}\OperatorTok{,}\NormalTok{ y}\OperatorTok{;}\NormalTok{ split}\OperatorTok{(}\NormalTok{rt}\OperatorTok{,}\NormalTok{ V}\OperatorTok{,}\NormalTok{ x}\OperatorTok{,}\NormalTok{ y}\OperatorTok{);} \DataTypeTok{int}\NormalTok{ res }\OperatorTok{=}\NormalTok{ select}\OperatorTok{(}\DecValTok{1}\OperatorTok{,}\NormalTok{ y}\OperatorTok{);}\NormalTok{ rt }\OperatorTok{=}\NormalTok{ merge}\OperatorTok{(}\NormalTok{x}\OperatorTok{,}\NormalTok{ y}\OperatorTok{);} \ControlFlowTok{return}\NormalTok{ res}\OperatorTok{;} \OperatorTok{\}}
  \OperatorTok{\}} \KeywordTok{using}\NormalTok{ FHQ}\OperatorTok{::}\NormalTok{ ins }\OperatorTok{;}\KeywordTok{using}\NormalTok{ FHQ}\OperatorTok{::}\NormalTok{ erase }\OperatorTok{;}\KeywordTok{using}\NormalTok{ FHQ}\OperatorTok{::}\NormalTok{ select }\OperatorTok{;}\KeywordTok{using}\NormalTok{ FHQ}\OperatorTok{::}\NormalTok{ rank }\OperatorTok{;}\KeywordTok{using}\NormalTok{ FHQ}\OperatorTok{::}\NormalTok{ pred }\OperatorTok{;}\KeywordTok{using}\NormalTok{ FHQ}\OperatorTok{::}\NormalTok{ succ }\OperatorTok{;}
  \end{Highlighting}
  \end{Shaded}
  
  
  \end{document}
[INFO] [makePDF] LaTeX run number 1
[INFO] [makePDF] LaTeX output
  This is XeTeX, Version 3.141592653-2.6-0.999995 (TeX Live 2023/Debian) (preloaded format=xelatex)
   restricted \write18 enabled.
  entering extended mode
  (.../input.tex
  LaTeX2e <2023-11-01> patch level 1
  L3 programming layer <2024-01-22>
  (.../article.cls
  Document Class: article 2023/05/17 v1.4n Standard LaTeX document class
  (.../[system]
  (.../xcolor.sty
  (.../color.cfg)
  (.../xetex.def)
  (.../[system]
  (.../geometry.sty
  (.../keyval.sty)
  (.../ifvtex.sty
  (.../iftex.sty)))
  (.../amsmath.sty
  For additional information on amsmath, use the `?' option.
  (.../amstext.sty
  (.../amsgen.sty))
  (.../amsbsy.sty)
  (.../amsopn.sty))
  (.../amssymb.sty
  (.../amsfonts.sty))
  (.../unicode-math.sty
  (.../expl3.sty
  (.../l3backend-xetex.def))
  (.../unicode-math-xetex.sty
  (.../xparse.sty)
  (.../l3keys2e.sty)
  (.../fontspec.sty
  (.../fontspec-xetex.sty
  (.../fontenc.sty)
  (.../fontspec.cfg)))
  (.../fix-cm.sty
  (.../ts1enc.def))
  (.../unicode-math-table.tex)))
  (.../lmodern.sty)
  (.../xeCJK.sty
  (.../ctexhook.sty)
  (.../xtemplate.sty)
  (.../xeCJK.cfg))
  (.../upquote.sty
  (.../textcomp.sty))
  (.../microtype.sty
  (.../etoolbox.sty)
  (.../microtype-xetex.def)
  (.../microtype.cfg))
  (.../setspace.sty)
  (.../parskip.sty
  (.../kvoptions.sty
  (.../ltxcmds.sty)
  (.../kvsetkeys.sty)))
  (.../fancyvrb.sty)
  (.../soul.sty
  (.../soul-ori.sty)
  (.../infwarerr.sty)
  (.../etexcmds.sty))
  (.../xeCJKfntef.sty
  (.../ulem.sty))
  (.../bookmark.sty
  (.../hyperref.sty
  (.../kvdefinekeys.sty)
  (.../pdfescape.sty
  (.../pdftexcmds.sty))
  (.../hycolor.sty)
  (.../auxhook.sty)
  (.../nameref.sty
  (.../refcount.sty)
  (.../gettitlestring.sty))
  (.../pd1enc.def)
  (.../intcalc.sty)
  (.../puenc.def)
  (.../url.sty)
  (.../bitset.sty
  (.../bigintcalc.sty))
  (.../atbegshi-ltx.sty))
  (.../hxetex.def
  (.../stringenc.sty)
  (.../rerunfilecheck.sty
  (.../atveryend-ltx.sty)
  (.../uniquecounter.sty)))
  (.../bkm-dvipdfm.def))
  (.../xurl.sty)
  No file input.aux.
  *geometry* driver: auto-detecting
  *geometry* detected driver: xetex
  (.../mt-LatinModernRoman.cfg)
  
  Package hyperref Warning: Rerun to get /PageLabels entry.
  
  (.../omllmm.fd)
  (.../umsa.fd)
  (.../mt-msa.cfg)
  (.../umsb.fd)
  (.../mt-msb.cfg)
  
  Package xeCJK Warning: Unknown CJK family `\CJKttdefault' is being ignored.
  (xeCJK)                
  (xeCJK)                Try to use `\setCJKmonofont[<...>]{<...>}' to define
  (xeCJK)                it.
  
  
  LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/b/n' undefined
  (Font)              using `TU/ARPLUKaiCN(0)/m/n' instead on input line 130.
  
  [1] [2] [3] [4] [5] [6] [7] [8] (.../input.aux)
  
  LaTeX Font Warning: Some font shapes were not available, defaults substituted.
  
  
  LaTeX Warning: Label(s) may have changed. Rerun to get cross-references right.
  
   )
  Output written on .../input.pdf (8 pages).
  Transcript written on .../input.log.
[INFO] [makePDF] Rerun needed
  Package hyperref Warning: Rerun to get /PageLabels entry.
  LaTeX Warning: Label(s) may have changed. Rerun to get cross-references right.
[INFO] [makePDF] LaTeX run number 2
[INFO] [makePDF] LaTeX output
  This is XeTeX, Version 3.141592653-2.6-0.999995 (TeX Live 2023/Debian) (preloaded format=xelatex)
   restricted \write18 enabled.
  entering extended mode
  (.../input.tex
  LaTeX2e <2023-11-01> patch level 1
  L3 programming layer <2024-01-22>
  (.../article.cls
  Document Class: article 2023/05/17 v1.4n Standard LaTeX document class
  (.../[system]
  (.../xcolor.sty
  (.../color.cfg)
  (.../xetex.def)
  (.../[system]
  (.../geometry.sty
  (.../keyval.sty)
  (.../ifvtex.sty
  (.../iftex.sty)))
  (.../amsmath.sty
  For additional information on amsmath, use the `?' option.
  (.../amstext.sty
  (.../amsgen.sty))
  (.../amsbsy.sty)
  (.../amsopn.sty))
  (.../amssymb.sty
  (.../amsfonts.sty))
  (.../unicode-math.sty
  (.../expl3.sty
  (.../l3backend-xetex.def))
  (.../unicode-math-xetex.sty
  (.../xparse.sty)
  (.../l3keys2e.sty)
  (.../fontspec.sty
  (.../fontspec-xetex.sty
  (.../fontenc.sty)
  (.../fontspec.cfg)))
  (.../fix-cm.sty
  (.../ts1enc.def))
  (.../unicode-math-table.tex)))
  (.../lmodern.sty)
  (.../xeCJK.sty
  (.../ctexhook.sty)
  (.../xtemplate.sty)
  (.../xeCJK.cfg))
  (.../upquote.sty
  (.../textcomp.sty))
  (.../microtype.sty
  (.../etoolbox.sty)
  (.../microtype-xetex.def)
  (.../microtype.cfg))
  (.../setspace.sty)
  (.../parskip.sty
  (.../kvoptions.sty
  (.../ltxcmds.sty)
  (.../kvsetkeys.sty)))
  (.../fancyvrb.sty)
  (.../soul.sty
  (.../soul-ori.sty)
  (.../infwarerr.sty)
  (.../etexcmds.sty))
  (.../xeCJKfntef.sty
  (.../ulem.sty))
  (.../bookmark.sty
  (.../hyperref.sty
  (.../kvdefinekeys.sty)
  (.../pdfescape.sty
  (.../pdftexcmds.sty))
  (.../hycolor.sty)
  (.../auxhook.sty)
  (.../nameref.sty
  (.../refcount.sty)
  (.../gettitlestring.sty))
  (.../pd1enc.def)
  (.../intcalc.sty)
  (.../puenc.def)
  (.../url.sty)
  (.../bitset.sty
  (.../bigintcalc.sty))
  (.../atbegshi-ltx.sty))
  (.../hxetex.def
  (.../stringenc.sty)
  (.../rerunfilecheck.sty
  (.../atveryend-ltx.sty)
  (.../uniquecounter.sty)))
  (.../bkm-dvipdfm.def))
  (.../xurl.sty)
  (.../input.aux)
  *geometry* driver: auto-detecting
  *geometry* detected driver: xetex
  (.../mt-LatinModernRoman.cfg)
  (.../omllmm.fd)
  (.../umsa.fd)
  (.../mt-msa.cfg)
  (.../umsb.fd)
  (.../mt-msb.cfg)
  
  Package xeCJK Warning: Unknown CJK family `\CJKttdefault' is being ignored.
  (xeCJK)                
  (xeCJK)                Try to use `\setCJKmonofont[<...>]{<...>}' to define
  (xeCJK)                it.
  
  
  LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/b/n' undefined
  (Font)              using `TU/ARPLUKaiCN(0)/m/n' instead on input line 130.
  
  [1] [2] [3] [4] [5] [6] [7] [8] (.../input.aux)
  
  LaTeX Font Warning: Some font shapes were not available, defaults substituted.
  
   )
  Output written on .../input.pdf (8 pages).
  Transcript written on .../input.log.