CVBB ACM Team

用户工具

站点工具

您在这里: front_page » 2020-2021 » teams » legal_string » jxm2001 » 无旋treap
2020-2021:teams:legal_string:jxm2001:无旋treap

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
后一修订版 		前一修订版
2020-2021:teams:legal_string:jxm2001:无旋treap [2020/07/08 19:55]
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>
-#include <​iostream>​ +const int MAXN=1e5+5; 
-#include <​cstdio>​ +namespace ​fhq_treap{
-#include <​cstdlib>​ +
-#include <​algorithm>​ +
-#include <​string>​ +
-#include <​sstream>​ +
-#include <​cstring>​ +
-#include <​cctype>​ +
-#include <​cmath>​ +
-#include <​vector>​ +
-#include <​set>​ +
-#include <​map>​ +
-#include <​stack>​ +
-#include <​queue>​ +
-#include <​ctime>​ +
-#include <​cassert>​ +
-#define _for(i,a,b) for(int i=(a);​i<​(b);​++i) +
-#define _rep(i,a,b) for(int i=(a);​i<​=(b);​++i) +
-#define mem(a,b) memset(a,​b,​sizeof(a)) +
-using namespace std; +
-typedef long long LL; +
-inline int read_int(){ +
-    int t=0;bool sign=false;​char c=getchar();​ +
-    while(!isdigit(c)){sign|=c=='​-';​c=getchar();​} +
-    while(isdigit(c)){t=(t<<​1)+(t<<​3)+(c&​15);​c=getchar();​} +
-    return sign?​-t:​t;​ +
-} +
-inline LL read_LL(){ +
-    LL t=0;bool sign=false;​char c=getchar();​ +
-    while(!isdigit(c)){sign|=c=='​-';​c=getchar();​} +
-    while(isdigit(c)){t=(t<<​1)+(t<<​3)+(c&​15);​c=getchar();​} +
-    return sign?​-t:​t;​ +
-} +
-inline char get_char(){ +
-    char c=getchar();​ +
-    while(c=='​ '​||c=='​\n'​||c=='​\r'​)c=getchar();​ +
-    return c; +
-} +
-inline void write(LL x){ +
-    register char c[21],​len=0;​ +
-    if(!x)return putchar('​0'​),​void();​ +
-    if(x<​0)x=-x,​putchar('​-'​);​ +
-    while(x)c[++len]=x%10,​x/​=10;​ +
-    while(len)putchar(c[len--]+48);​ +
-} +
-inline void space(LL x){write(x),​putchar('​ ');} +
-inline void enter(LL x){write(x),​putchar('​\n'​);​} +
-const int MAXN=2e6+5; +
-struct ​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);
  }  }
  }  }
行 139: 行 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);
  }  }
  }  }
行 154: 行 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);​
行 188: 行 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;
 } }
行 231: 行 192:
 <hidden 查看代码>​ <hidden 查看代码>​
 <code cpp> <code cpp>
-#include <​iostream>​ +const int MAXN=1e5+5; 
-#include <​cstdio>​ +namespace Treap{ 
-#include <​cstdlib>​ + int root;
-#include <​algorithm>​ +
-#include <​string>​ +
-#include <​sstream>​ +
-#include <​cstring>​ +
-#include <​cctype>​ +
-#include <​cmath>​ +
-#include <​vector>​ +
-#include <​set>​ +
-#include <​map>​ +
-#include <​stack>​ +
-#include <​queue>​ +
-#include <​ctime>​ +
-#include <​cassert>​ +
-#define _for(i,a,b) for(int i=(a);​i<​(b);​++i) +
-#define _rep(i,a,b) for(int i=(a);​i<​=(b);​++i) +
-#define mem(a,b) memset(a,​b,​sizeof(a)) +
-using namespace std; +
-typedef long long LL; +
-inline int read_int(){ +
-    int t=0;bool sign=false;​char c=getchar();​ +
-    while(!isdigit(c)){sign|=c=='​-';​c=getchar();​} +
-    while(isdigit(c)){t=(t<<​1)+(t<<​3)+(c&​15);​c=getchar();​} +
-    return sign?​-t:​t;​ +
-} +
-inline LL read_LL(){ +
-    LL t=0;bool sign=false;​char c=getchar();​ +
-    while(!isdigit(c)){sign|=c=='​-';​c=getchar();​} +
-    while(isdigit(c)){t=(t<<​1)+(t<<​3)+(c&​15);​c=getchar();​} +
-    return sign?​-t:​t;​ +
-} +
-inline char get_char(){ +
-    char c=getchar();​ +
-    while(c=='​ '​||c=='​\n'​||c=='​\r'​)c=getchar();​ +
-    return c; +
-} +
-inline void write(LL x){ +
-    register char c[21],​len=0;​ +
-    if(!x)return putchar('​0'​),​void();​ +
-    if(x<​0)x=-x,​putchar('​-'​);​ +
-    while(x)c[++len]=x%10,​x/​=10;​ +
-    while(len)putchar(c[len--]+48);​ +
-} +
-inline void space(LL x){write(x),​putchar('​ ');} +
-inline void enter(LL x){write(x),​putchar('​\n'​);​} +
-const int MAXN=2e6+5; +
-struct fhq_treap{ +
- int root,tot; +
- vector<​int>​ sequence;+
  struct Node{  struct Node{
- int r,val,sz,flip,ch[2];+ int val; 
 + int r,sz,ch[2]; 
 + int flip;
  }node[MAXN];​  }node[MAXN];​
- int New(int v){ + int node_cnt; 
- int x=++tot; + int new_node(int v){ 
- node[x].val=v,node[x].r=rand(),​node[x].sz=1; + int k=++node_cnt; 
- return ​x;+ node[k].val=v; 
 + node[k].r=rand(),​node[k].sz=1,​node[k].ch[0]=node[k].ch[1]=0;​ 
 + node[k].flip=0; 
 + return ​k;
  }  }
- void pushup(int k){node[k].sz=node[node[k].ch[0]].sz+node[node[k].ch[1]].sz+1;} + #define lch(k) node[node[k].ch[0]] 
- void pushdown(int k){+ #define rch(k) ​node[node[k].ch[1]] 
 + void push_up(int k){ 
 + node[k].sz=lch(k).sz+rch(k).sz+1;​ 
 + } 
 + void push_flip(int k){ 
 + swap(node[k].ch[0],node[k].ch[1]); 
 + node[k].flip^=1; 
 + } 
 + void push_down(int k){
  if(node[k].flip){  if(node[k].flip){
- swap(node[k].ch[0],​node[k].ch[1]); + push_flip(node[k].ch[0]);​ 
- node[node[k].ch[0]].flip^=1; + push_flip(node[k].ch[1]);
- node[node[k].ch[1]].flip^=1;+
  node[k].flip=0;​  node[k].flip=0;​
  }  }
  }  }
  void split(int k,int &k1,int &k2,int rk){  void split(int k,int &k1,int &k2,int rk){
- if(!k) return k1=k2=0,​void();​ + if(!k)return k1=k2=0,​void();​ 
- pushdown(k); + push_down(k); 
- if(node[node[k].ch[0]].sz+1<​=rk){ + if(lch(k).sz+1<​=rk){ 
- k1=k;​split(node[k].ch[1],​node[k1].ch[1],​k2,​rk-node[node[k].ch[0]].sz-1);pushup(k1); + k1=k; 
- }else{ + split(node[k].ch[1],​node[k1].ch[1],​k2,​rk-lch(k).sz-1); 
- k2=k;​split(node[k].ch[0],​k1,​node[k2].ch[0],​rk);​pushup(k2);+ push_up(k1); 
 + } 
 + else{ 
 + k2=k; 
 + split(node[k].ch[0],​k1,​node[k2].ch[0],​rk);​ 
 + push_up(k2);
  }  }
  }  }
行 311: 行 241:
  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){
- pushdown(k1);​k=k1;​merge(node[k].ch[1],​node[k1].ch[1],​k2);​pushup(k); + push_down(k1); 
- }else{ + k=k1; 
- pushdown(k2);​k=k2;​merge(node[k].ch[0],​k1,​node[k2].ch[0]);​pushup(k);+ merge(node[k].ch[1],​node[k1].ch[1],​k2);​ 
 + push_up(k); 
 + } 
 + else{ 
 + push_down(k2); 
 + k=k2; 
 + merge(node[k].ch[0],​k1,​node[k2].ch[0]);​ 
 + push_up(k);
  }  }
  }  }
- void build(){ + int Stack[MAXN];​ 
- _for(i,​0,​sequence.size()) + void build(int k){ 
- merge(root,​root,​New(sequence[i]));+ if(!k)return; 
 + build(node[k].ch[0]); 
 + build(node[k].ch[1]); 
 + push_up(k);
  }  }
- void Flip(int L,int R){+ void build(int *a,int n){ 
 + int top=0; 
 + Stack[top]=0;​ 
 + node[0].r=0x7fffffff;​ 
 + _for(i,​0,​n){ 
 + int k=new_node(a[i]);​ 
 + while(node[k].r>​node[Stack[top]].r)top--;​ 
 + node[k].ch[0]=node[Stack[top]].ch[1];​ 
 + node[Stack[top]].ch[1]=k;​ 
 + Stack[++top]=k;​ 
 + } 
 + node[0].ch[0]=node[0].ch[1]=0;​ 
 + root=Stack[1];​ 
 + build(root);​ 
 + } 
 + void flip(int L,int R){
  int lef,​mid,​rig;​  int lef,​mid,​rig;​
  split(root,​lef,​rig,​R);​  split(root,​lef,​rig,​R);​
  split(lef,​lef,​mid,​L-1);​  split(lef,​lef,​mid,​L-1);​
- node[mid].flip^=1;+ push_flip(mid);
  merge(lef,​lef,​mid);​  merge(lef,​lef,​mid);​
  merge(root,​lef,​rig);​  merge(root,​lef,​rig);​
  }  }
- void output(){ + void dfs(int k,int *a){ 
- sequence.clear(); + if(!k)return;​ 
- dfs(root);+ push_down(k);​ 
 + dfs(node[k].ch[0],a); 
 + a[lch(k).sz]=node[k].val;​ 
 + a+=lch(k).sz+1; 
 + dfs(node[k].ch[1],​a);
  }  }
- void dfs(int k){ +}; 
- if(!k) return; +int a[MAXN];
- pushdown(k);​ +
- dfs(node[k].ch[0]); +
- sequence.push_back(node[k].val);​ +
- dfs(node[k].ch[1]);​ +
- } +
-}tree;+
 int main() int main()
 { {
- int n=read_int(),​m=read_int(),L,R; + int n=read_int(),​m=read_int();​ 
- _rep(i,1,n) + _for(i,0,n)a[i]=i+1; 
- tree.sequence.push_back(i); + Treap::build(a,n);
- tree.build();+
  while(m--){  while(m--){
- L=read_int(),​R=read_int();​ + int lef=read_int(),​rig=read_int();​ 
- tree.Flip(L,R);+ Treap::flip(lef,rig);
  }  }
- tree.output(); + Treap::dfs(Treap::​root,​a); 
- _for(i,​0,​n) + _for(i,​0,​n)space(a[i]); 
- space(tree.sequence[i]); + return 0;
-    return 0;+
 } }
 </​code>​ </​code>​
 </​hidden>​ </​hidden>​
  
2020-2021/teams/legal_string/jxm2001/无旋treap.1594209356.txt.gz · 最后更改: 2020/07/08 19:55 由 jxm2001

页面工具

除额外注明的地方外，本维基上的内容按下列许可协议发布： CC Attribution-Share Alike 4.0 International
CC Attribution-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki
京ICP备20018844号-3