2020-2021:teams:legal_string:jxm2001:无旋treap
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:legal_string:jxm2001:无旋treap [2021/07/03 11:18] jxm2001 |
2020-2021:teams:legal_string:jxm2001:无旋treap [2021/08/11 10:37] (当前版本) jxm2001 [集合维护版本] |
||
|---|---|---|---|
| 行 63: | 行 63: | ||
| ==== 集合维护版本 ==== | ==== 集合维护版本 ==== | ||
| - | [[https://www.luogu.com.cn/problem/P6136|洛谷p6136]] | + | [[https://www.luogu.com.cn/problem/P3369|洛谷p3369]] |
| <hidden 查看代码> | <hidden 查看代码> | ||
| <code cpp> | <code cpp> | ||
| - | const int MAXN=2e6+5; | + | const int MAXN=1e5+5; |
| - | struct fhq_treap{ | + | namespace fhq_treap{ |
| int root; | int root; | ||
| struct Node{ | struct Node{ | ||
| int val,r,sz,ch[2]; | int val,r,sz,ch[2]; | ||
| }node[MAXN]; | }node[MAXN]; | ||
| - | int pool[MAXN],top,tot; | + | int node_cnt; |
| int New(int v){ | int New(int v){ | ||
| - | int x=top?pool[top--]:++tot; | + | int k=++node_cnt; |
| - | node[x].val=v,node[x].r=rand(),node[x].sz=1,node[x].ch[0]=node[x].ch[1]=0; | + | node[k].val=v; |
| - | return x; | + | node[k].r=rand(),node[k].sz=1,node[k].ch[0]=node[k].ch[1]=0; |
| + | return k; | ||
| + | } | ||
| + | #define lch(k) node[node[k].ch[0]] | ||
| + | #define rch(k) node[node[k].ch[1]] | ||
| + | void push_up(int k){ | ||
| + | node[k].sz=lch(k).sz+rch(k).sz+1; | ||
| } | } | ||
| - | void Del(int x){if(x)pool[++top]=x;} | ||
| - | void pushup(int k){node[k].sz=node[node[k].ch[0]].sz+node[node[k].ch[1]].sz+1;} | ||
| void split(int k,int &k1,int &k2,int v){ | void split(int k,int &k1,int &k2,int v){ | ||
| if(!k) return k1=k2=0,void(); | if(!k) return k1=k2=0,void(); | ||
| if(node[k].val<=v){ | if(node[k].val<=v){ | ||
| - | k1=k;split(node[k].ch[1],node[k1].ch[1],k2,v);pushup(k1); | + | k1=k; |
| + | split(node[k].ch[1],node[k1].ch[1],k2,v); | ||
| + | push_up(k1); | ||
| }else{ | }else{ | ||
| - | k2=k;split(node[k].ch[0],k1,node[k2].ch[0],v);pushup(k2); | + | k2=k; |
| + | split(node[k].ch[0],k1,node[k2].ch[0],v); | ||
| + | push_up(k2); | ||
| } | } | ||
| } | } | ||
| 行 92: | 行 100: | ||
| if(!k1||!k2)return k=k1|k2,void(); | if(!k1||!k2)return k=k1|k2,void(); | ||
| if(node[k1].r>node[k2].r){ | if(node[k1].r>node[k2].r){ | ||
| - | k=k1;merge(node[k].ch[1],node[k1].ch[1],k2);pushup(k); | + | k=k1; |
| + | merge(node[k].ch[1],node[k1].ch[1],k2); | ||
| + | push_up(k); | ||
| }else{ | }else{ | ||
| - | k=k2;merge(node[k].ch[0],k1,node[k2].ch[0]);pushup(k); | + | k=k2; |
| + | merge(node[k].ch[0],k1,node[k2].ch[0]); | ||
| + | push_up(k); | ||
| } | } | ||
| } | } | ||
| 行 107: | 行 119: | ||
| split(root,lef,rig,v); | split(root,lef,rig,v); | ||
| split(lef,lef,mid,v-1); | split(lef,lef,mid,v-1); | ||
| - | Del(mid); | ||
| merge(mid,node[mid].ch[0],node[mid].ch[1]); | merge(mid,node[mid].ch[0],node[mid].ch[1]); | ||
| merge(lef,lef,mid); | merge(lef,lef,mid); | ||
| 行 141: | 行 152: | ||
| return kth(rk); | return kth(rk); | ||
| } | } | ||
| - | }tree; | + | #undef lch |
| + | #undef rch | ||
| + | }; | ||
| int main() | int main() | ||
| { | { | ||
| - | int n=read_int(),m=read_int(),opt,x,last=0,ans=0; | + | int n=read_int(),opt,x; |
| while(n--){ | while(n--){ | ||
| - | x=read_int(); | + | opt=read_int(),x=read_int(); |
| - | tree.insert(x); | + | |
| - | } | + | |
| - | while(m--){ | + | |
| - | opt=read_int(),x=read_int()^last; | + | |
| switch(opt){ | switch(opt){ | ||
| case 1: | case 1: | ||
| - | tree.insert(x); | + | fhq_treap::insert(x); |
| break; | break; | ||
| case 2: | case 2: | ||
| - | tree.erase(x); | + | fhq_treap::erase(x); |
| break; | break; | ||
| case 3: | case 3: | ||
| - | ans^=(last=tree.rank(x)); | + | enter(fhq_treap::rank(x)); |
| break; | break; | ||
| case 4: | case 4: | ||
| - | ans^=(last=tree.kth(x)); | + | enter(fhq_treap::kth(x)); |
| break; | break; | ||
| case 5: | case 5: | ||
| - | ans^=(last=tree.pre(x)); | + | enter(fhq_treap::pre(x)); |
| break; | break; | ||
| case 6: | case 6: | ||
| - | ans^=(last=tree.suf(x)); | + | enter(fhq_treap::suf(x)); |
| break; | break; | ||
| } | } | ||
| } | } | ||
| - | enter(ans); | ||
| return 0; | return 0; | ||
| } | } | ||
2020-2021/teams/legal_string/jxm2001/无旋treap.1625282324.txt.gz · 最后更改: 2021/07/03 11:18 由 jxm2001
