老師的代碼有點(diǎn)瑕疵，這里我補(bǔ)充一下，但是這里的瑕疵是學(xué)算法才能感知到的，如果是新人的話就是需要一一對(duì)比，即用老師的代碼做洛谷 P3369 【模板】普通平衡樹 這題是AC的，但是做洛谷 P6136 【模板】普通平衡樹（數(shù)據(jù)加強(qiáng)版）就不一定了，該題有點(diǎn)裸但是也不是太裸，他輸入數(shù)據(jù)異或加密了。你用老師的板子做就不一定能過，因?yàn)?get_rank(這是我寫的函數(shù)名) 老師的代碼如果這個(gè)數(shù)不存在，就有點(diǎn)問題了。這是問題1，問題2就是.查前驅(qū)/后繼 ，最后也要splay一次，不然復(fù)雜度保證不了，即就兩個(gè)數(shù)據(jù)測(cè)試點(diǎn)TLE。記住注釋也要看看

```C++

//P6136?【模板】普通平衡樹（數(shù)據(jù)加強(qiáng)版）

#include?<iostream>

using?namespace?std;

#define?ls(x)?tr[x].son[0]

#define?rs(x)?tr[x].son[1]

const?int?MAX_N?=?1e5?+?5,?MAX_M?=?1e6?+?5;

const?int?MAX_SIZE?=?MAX_N?+?MAX_M;

const?int??INF?=?(1?<<?30)?+?1;

struct?Node?{

????int?son[2];?//左右兒子

????int?parent;?//父親

????int?val;?//節(jié)點(diǎn)權(quán)值

????int?cnt;?//權(quán)值出現(xiàn)次數(shù)

????int?siz;?//子樹大小

????void?init(int?parent_,?int?val_)?{

????????parent?=?parent_,?val?=?val_;

????????cnt?=?siz?=?1;

????}

}?tr[MAX_SIZE];

int?root,?idx;?//根節(jié)點(diǎn)編號(hào),節(jié)點(diǎn)個(gè)數(shù)

void?pushup(int?x)?{//x?下標(biāo)

????tr[x].siz?=?tr[ls(x)].siz?+?tr[rs(x)].siz?+?tr[x].cnt;

}

void?rotate(int?x)?{//x?下標(biāo)

????int?y?=?tr[x].parent,?z?=?tr[y].parent;

????int?k?=?tr[y].son[1]?==?x;

????tr[z].son[tr[z].son[1]?==?y]?=?x;

????tr[x].parent?=?z;

????tr[y].son[k]?=?tr[x].son[k?^?1];

????tr[tr[x].son[k?^?1]].parent?=?y;

????tr[x].son[k?^?1]?=?y;

????tr[y].parent?=?x;

????pushup(y),?pushup(x);

}

void?splay(int?x,?int?k)?{

????while?(tr[x].parent?!=?k)?{

????????int?y?=?tr[x].parent,?z?=?tr[y].parent;

????????if?(z?!=?k)?//?折轉(zhuǎn)底，直轉(zhuǎn)中

????????????(ls(y)?==?x)^(ls(z)?==?y)???rotate(x)?:?rotate(y);

????????rotate(x);

????}

????if?(!k)?root?=?x;

}

void?insert(int?v)?{?//插入數(shù)值v

????int?x?=?root,?p?=?0;

????while?(x?&&?tr[x].val?!=?v)

????????p?=?x,?x?=?tr[x].son[v?>?tr[x].val];

????if?(x)?tr[x].cnt++;

????else?{

????????x?=?++idx;

????????tr[p].son[v?>?tr[p].val]?=?x;

????????tr[x].init(p,?v);

????}

????splay(x,?0);

}

void?find(int?v)?{?//找到數(shù)值v并轉(zhuǎn)到根

????int?x?=?root;

????while?(tr[x].son[v?>?tr[x].val]?&&?v?!=?tr[x].val)

????????x?=?tr[x].son[v?>?tr[x].val];

????splay(x,?0);

}

int?get_pre(int?v)?{?//數(shù)值v前驅(qū)的編號(hào)

????find(v);

????int?x?=?root;

????if?(tr[x].val?<?v)?return?x;

????x?=?ls(x);

????while?(rs(x))?x?=?rs(x);

????splay(x,?0);//?艸,少一句代碼都TLE,#5樣例TLE#6樣例PASS

????return?x;

}

int?get_suc(int?v)?{?//數(shù)值v后繼的編號(hào)

????find(v);

????int?x?=?root;

????if?(tr[x].val?>?v)?return?x;

????x?=?rs(x);

????while?(ls(x))?x?=?ls(x);

????splay(x,?0);//?#5樣例PASS#6樣例TLE

????return?x;

}

void?del(int?v)?{?//數(shù)值v刪除

????int?pre?=?get_pre(v);

????int?suc?=?get_suc(v);

????splay(pre,?0),?splay(suc,?pre);

????int?del?=?tr[suc].son[0];

????if?(tr[del].cnt?>?1)

????????tr[del].cnt--,?splay(del,?0);

????else

????????tr[suc].son[0]?=?0,?splay(suc,?0);

}

int?get_rank(int?v)?{?//數(shù)值v排名

//????這里老師的代碼有問題

//????find(v);

//????return?tr[tr[root].son[0]].siz;

????insert(v);

????int?res?=?tr[tr[root].son[0]].siz;

????del(v);

????return?res;

}

int?get_val_by_rank(int?k)?{?//數(shù)值

????int?x?=?root;

????while?(1)?{

????????int?y?=?ls(x);

????????if?(tr[y].siz?+?tr[x].cnt?<?k)

????????????k?-=?tr[y].siz?+?tr[x].cnt,

?????????????????x?=?rs(x);

????????else?if?(tr[y].siz?>=?k)?x?=?y;

????????else?break;

????}

????splay(x,?0);

????return?tr[x].val;

}

int?main()?{

????ios::sync_with_stdio(false);

????cin.tie(nullptr);

????insert(-INF);

????insert(INF);?//哨兵

????int?n,?m;

????scanf("%d%d",?&n,?&m);

????int?x;

????while?(n--)?{

????????scanf("%d",?&x);

????????insert(x);

????}

????int?op,?res?=?0,?last?=?0;

????while?(m--)?{

????????scanf("%d%d",?&op,?&x);

????????x?^=?last;

????????if?(op?==?1)?insert(x);

????????if?(op?==?2)?del(x);

????????if?(op?==?3)?res?^=?(last?=?get_rank(x))/*,cout?<<?"加密后:3??"?<<?x?<<?endl*/;

????????if?(op?==?4)?res?^=?(last?=?get_val_by_rank(x?+?1))/*,?cout?<<?"加密后:4??"?<<?x?<<?endl*/;

????????if?(op?==?5)?res?^=?(last?=?tr[get_pre(x)].val)/*,?cout?<<?"加密后:5??"?<<?x?<<?endl*/;

????????if?(op?==?6)?res?^=?(last?=?tr[get_suc(x)].val)/*,?cout?<<?"加密后:6??"?<<?x?<<?endl*/;

????}

????cout?<<?res?<<?'\n';

????return?0;

}

```