[关闭]
@yang12138 2018-10-27T00:58:42.000000Z 字数 12156 阅读 1178

板子

KD树

  2. //二维kd树，询问给定点到已知点集的最短距离，k维同理
  3. //基于欧几里得距离，基于曼哈顿距离同理
  5. const int N=2e5+10;
  7. struct Point{
  8.     ll x[2];
  9.     Point(){
  10.         memset(x,0,sizeof(x));
  11.     }
  12. };
  14. ll dis(const Point& a,const Point& b){
  15.     ll ans=0;
  16.     for(int i=0;i<2;i++) ans+=1LL*(a.x[i]-b.x[i])*(a.x[i]-b.x[i]);
  17.     return ans;
  18. }
  20. int DIM;
  21. bool cmp(const Point& a,const Point& b){
  22.     return a.x[DIM]<b.x[DIM];
  23. }
  25. ll pw(ll a){return a*a;}
  27. struct Node{
  28.     Point p;
  29.     int dim;
  30.     Node *lson,*rson;
  31.     Node(){
  32.         lson = rson = NULL;
  33.     }
  34. };
  36. Node* newNode(){
  37.     return new Node;
  38. }
  40. void build(Node* &root,vector<Point>vec,int dep){
  42.     if(!vec.size()){
  43.         root=NULL;
  44.         return ;
  45.     }
  47.     root = newNode();
  48.     DIM=root->dim=dep;
  50.     sort(vec.begin(),vec.end(),cmp);
  52.     int sz = (int)vec.size();
  53.     root->p = vec[sz/2];
  55.     vector<Point>lvec,rvec;
  56.     for(int i=0;i<=sz/2-1;i++) lvec.push_back(vec[i]);
  57.     for(int i=sz/2+1;i<sz;i++) rvec.push_back(vec[i]);
  59.     build(root->lson,lvec,dep^1);
  60.     build(root->rson,rvec,dep^1);
  61. }
  64. void add(Node* &root,const Point& tar,int dep){
  65.     if(root==NULL){
  66.     root=newNode();
  67.         root->p=tar,root->dim=dep;
  68.         return ;
  69.     }
  70.     if(tar.x[dep]<=root->p.x[dep])
  71.         add(root->lson,tar,dep^1);
  72.     else add(root->rson,tar,dep^1);
  73. }
  75. void search(const Node* root,const Point& tar,ll& min_dis){
  76.     if(root==NULL) return ;
  78.     if(dis(tar,root->p)<min_dis) min_dis=dis(tar,root->p);
  80.     Node* left;
  81.     if(tar.x[root->dim]<=root->p.x[root->dim]){
  82.         search(root->lson,tar,min_dis);
  83.         left=root->rson;
  84.     }
  85.     else{
  86.         search(root->rson,tar,min_dis);
  87.         left=root->lson;
  88.     }
  90.     if(pw(abs(tar.x[root->dim] - root->p.x[root->dim]))<=min_dis){
  91.         search(left,tar,min_dis);
  92.     }
  93. }
  1. //求曼哈顿距离最近和最远
  2. //维护四个最值
  4. struct Point{
  5.     int x,y;
  6.     Point(){}
  7.     Point(int x,int y):x(x),y(y){}
  8.     int dis(const Point& tmp)const{
  9.         return abs(x-tmp.x)+abs(y-tmp.y);
  10.     }
  11. };
  13. int DIM;
  14. bool cmp(const Point& a,const Point& b){
  15.     return DIM?a.y<b.y:a.x<b.x;
  16. }
  18. struct Node{
  19.     Point p;
  20.     Node *lson,*rson;
  21.     int mi[2],ma[2];
  22.     Node(){
  23.         lson = rson = NULL;
  24.     }
  25.     void setp(const Point& tp){
  26.         this->p = tp;
  27.         mi[0]=ma[0]=tp.x;
  28.         mi[1]=ma[1]=tp.y;
  29.     }
  30.     void pushup(const Node& tp){
  31.         mi[0]=min(mi[0],tp.mi[0]);
  32.         ma[0]=max(ma[0],tp.ma[0]);
  33.         mi[1]=min(mi[1],tp.mi[1]);
  34.         ma[1]=max(ma[1],tp.ma[1]);
  35.     }
  36.     //求理论上可能的最小值
  37.     int min_dis(const Point& tp){
  38.         int ans=0;
  39.         if(tp.x<mi[0] || tp.x>ma[0]){
  40.             ans+= (tp.x<mi[0])?mi[0]-tp.x:tp.x-ma[0];
  41.         }
  42.         if(tp.y<mi[1] || tp.y>ma[1]){
  43.             ans+= (tp.y<mi[1])?mi[1]-tp.y:tp.y-ma[1];
  44.         }
  45.         return ans;
  46.     }
  47.     //求理论上可能的最大值
  48.     int max_dis(const Point& tp){
  49.         return max(abs(tp.x-mi[0]),abs(tp.x-ma[0]))+max(abs(tp.y-mi[1]),abs(tp.y-ma[1]));
  50.     }
  51. };
  53. //[l,r)
  54. void build(Node* &root,Point* p,int l,int r,int dep){
  55.     if(l>=r){
  56.         root=NULL;
  57.         return ;
  58.     }
  59.     root = new Node;
  60.     int sz=r-l;
  61.     DIM = dep;
  62.     nth_element(p+l,p+l+sz/2,p+r,cmp);
  64.     root->setp(p[l+sz/2]);
  66.     build(root->lson,p,l,l+sz/2,dep^1);
  67.     build(root->rson,p,l+sz/2+1,r,dep^1);
  68.     if(root->lson!=NULL) root->pushup(*(root->lson));
  69.     if(root->rson!=NULL) root->pushup(*(root->rson));
  70. }
  72. void search_min(Node* &root,const Point& tar,int dep,int& ans){
  73.     if(root==NULL) return ;
  74.     if(root->p.dis(tar)!=0) ans=min(ans,root->p.dis(tar));
  76.     if(root->lson==NULL && root->rson==NULL) return ;
  77.     if(root->lson==NULL){
  78.         search_min(root->rson,tar,dep+1,ans);
  79.     }
  80.     else if(root->rson==NULL){
  81.         search_min(root->lson,tar,dep+1,ans);
  82.     }
  83.     else{
  84.         if(root->lson->min_dis(tar) < root->rson->min_dis(tar)){
  85.             if(root->lson->min_dis(tar)>=ans) return ;
  86.             search_min(root->lson,tar,dep+1,ans);
  87.             if(root->rson->min_dis(tar)<ans) search_min(root->rson,tar,dep+1,ans);
  88.         }
  89.         else{
  90.             if(root->rson->min_dis(tar)>=ans) return ;
  91.             search_min(root->rson,tar,dep+1,ans);
  92.             if(root->lson->min_dis(tar)<ans) search_min(root->lson,tar,dep+1,ans);
  93.         }
  94.     }
  95. }
  97. void search_max(Node* &root,const Point& tar,int dep,int& ans){
  98.     if(root==NULL) return ;
  99.     ans=max(ans,root->p.dis(tar));
  101.     if(root->lson==NULL && root->rson==NULL) return ;
  102.     if(root->lson==NULL){
  103.         search_max(root->rson,tar,dep+1,ans);
  104.     }
  105.     else if(root->rson==NULL){
  106.         search_max(root->lson,tar,dep+1,ans);
  107.     }
  108.     else{
  109.         if(root->lson->max_dis(tar) > root->rson->max_dis(tar)){
  110.             if(root->lson->max_dis(tar)<=ans) return ;
  111.             search_max(root->lson,tar,dep+1,ans);
  112.             if(root->rson->max_dis(tar)>ans) search_max(root->rson,tar,dep+1,ans);
  113.         }
  114.         else{
  115.             if(root->rson->max_dis(tar)<=ans) return ;
  116.             search_max(root->rson,tar,dep+1,ans);
  117.             if(root->lson->max_dis(tar)>ans) search_max(root->lson,tar,dep+1,ans);
  118.         }
  119.     }
  120. }

Min_25筛

可求素数之和
时间,空间大概

  1. struct HashTable{
  2.     const static int N = 6.6e5+10;
  3.     const static int mod = (1<<22)+1;
  5.     int head[mod];
  6.     int v[N],nex[N],cnt;
  7.     ll u[N];
  9.     HashTable(){
  10.         memset(head,0,sizeof(head));
  11.         cnt=1;
  12.     }
  14.     void insert(ll x,int id){
  15.         int left=x%mod;
  16.         v[cnt]=id,u[cnt]=x,nex[cnt]=head[left],head[left]=cnt++;
  17.     }
  19.     int query(ll x){
  20.         int left=x%mod;
  21.         for(int i=head[left];i;i=nex[i]){
  22.             if(u[i]==x) return v[i];
  23.         }
  24.         return -1;
  25.     }
  27.     void clear(){
  28.         memset(head,0,sizeof(head));
  29.         cnt=1;
  30.     }
  32. }ht;
  34. const int N=6.6e5+10;
  36. int pri[N],t;
  37. ll pris[N];
  38. bool vis[N];
  40. void init(){
  41.     for(int i=2;i<N;i++){
  42.         if(!vis[i]) pri[++t]=i;
  43.         for(int j=1;j<=t;j++){
  44.             int u=pri[j]*i;
  45.             if(u>=N) break;
  46.             vis[u]=1;
  47.             if(i%pri[j]==0) break;
  48.         }
  49.     }
  50.     for(int i=1;i<=t;i++) pris[i]=pris[i-1]+pri[i];
  51. }
  53. int Hash(int x){
  54.     return upper_bound(pri+1,pri+t+1,x)-pri-1;
  55. }
  57. int sqr(ll x){
  58.     int k=(int)sqrt(x+0.5);
  59.     while(1LL*(k+1)*(k+1)<=x) k++;
  60.     while(1LL*k*k>x) k--;
  61.     return k;
  62. }
  64. int cou[N];
  65. ll v[N];
  66. double *dp[N];
  67. int len[N];
  69. double g(ll n,int j){
  70.     if(j==0) return 1.0*n*(n+1)/2-1;
  71.     int id=ht.query(n);
  72.     if(j>len[id]) return g(n,len[id]);
  74.     if(dp[id]==NULL){
  75.         dp[id]=new double[len[id]+1];
  76.         for(int i=0;i<len[id]+1;i++) dp[id][i]=-1.0;
  77.     }
  79.     if(dp[id][j]>=0) return dp[id][j];
  80.     return dp[id][j]=g(n,j-1)-1.0*pri[j]*(g(n/pri[j],j-1)-pris[j-1]);
  81. }
  83. double cal(ll n){
  84.     if(n<=1) return 0;
  86.     ht.clear();
  87.     int cnt=0;
  88.     for(ll l=1,r;l<=n;l=r+1){
  89.         r=n/(n/l);
  90.         v[++cnt]=n/l;
  91.         len[cnt]=Hash(sqr(n/l));
  92.         ht.insert(n/l,cnt);
  93.     }
  94.     double ans=g(n,t);
  96.     for(int i=1;i<=cnt;i++){
  97.         if(dp[i]!=NULL) delete(dp[i]),dp[i]=NULL;
  98.     }
  100.     return ans;
  101. }

定义是积性函数
求

  2. struct HashTable{
  3.     const static int N = 2.1e5+10;
  4.     const static int mod = (1<<20)+1;
  6.     int head[mod];
  7.     int v[N],nex[N],cnt;
  8.     ll u[N];
  10.     HashTable(){
  11.         memset(head,0,sizeof(head));
  12.         cnt=1;
  13.     }
  15.     void insert(ll x,int id){
  16.         int left=x%mod;
  17.         v[cnt]=id,u[cnt]=x,nex[cnt]=head[left],head[left]=cnt++;
  18.     }
  20.     int query(ll x){
  21.         int left=x%mod;
  22.         for(int i=head[left];i;i=nex[i]){
  23.             if(u[i]==x) return v[i];
  24.         }
  25.         return -1;
  26.     }
  28.     void clear(){
  29.         memset(head,0,sizeof(head));
  30.         cnt=1;
  31.     }
  33. }ht;
  35. const int N=2.1e5+10;
  36. const int mod=1e9+7;
  38. struct PLL{
  39.     int a;
  40.     ll b;
  41.     PLL(){
  42.         a=b=-1;
  43.     }
  44.     PLL(ll a,ll b):a(a),b(b){}
  45.     PLL operator - (const PLL& tmp)const{
  46.         return PLL((0LL+a-tmp.a+mod)%mod,b-tmp.b);
  47.     }
  48.     PLL operator + (const PLL& tmp)const{
  49.         return PLL((0LL+a+tmp.a)%mod,b+tmp.b);
  50.     }
  51.     PLL operator * (const PLL& tmp)const{
  52.         return PLL((1LL*a*tmp.a)%mod,b*tmp.b);
  53.     }
  54. }pris[N];
  56. int pri[N],t;
  57. bool vis[N];
  58. ll ps[N];
  60. void init(){
  61.     for(int i=2;i<N;i++){
  62.         if(!vis[i]) pri[++t]=i;
  63.         for(int j=1;j<=t;j++){
  64.             int u=pri[j]*i;
  65.             if(u>=N) break;
  66.             vis[u]=1;
  67.             if(i%pri[j]==0) break;
  68.         }
  69.     }
  70.     pris[0]=PLL(0,0);
  71.     for(int i=1;i<=t;i++){
  72.         pris[i]=pris[i-1]+PLL(pri[i],1);
  73.         ps[i]=(ps[i-1]+(pri[i]^1))%mod;
  74.     }
  75. }
  77. int Hash(int x){
  78.     return upper_bound(pri+1,pri+t+1,x)-pri-1;
  79. }
  81. int sqr(ll x){
  82.     int k=(int)sqrt(x+0.5);
  83.     while(1LL*(k+1)*(k+1)<=x) k++;
  84.     while(1LL*k*k>x) k--;
  85.     return k;
  86. }
  88. int len[N];
  89. ll v[N];
  90. int *dpa[N];
  91. ll *dpb[N];
  93. PLL h(ll n,int j){
  94.     if(j==0) return PLL((1LL*(n%mod)*(n%mod+1)/2-1)%mod,n-1);
  95.     int id=ht.query(n);
  96.     if(j>len[id]) return h(n,len[id]);
  98.     if(dpa[id]==NULL){
  99.         dpa[id] = new int[len[id]+1];
  100.         dpb[id] = new ll[len[id]+1];
  101.         for(int i=0;i<len[id]+1;i++) dpa[id][i]=-1,dpb[id][i]=-1;
  102.     }
  104.     if(dpa[id][j]>=0) return PLL(dpa[id][j],dpb[id][j]);
  105.     PLL ans=h(n,j-1)-PLL(pri[j],1)*(h(n/pri[j],j-1)-pris[j-1]);
  106.     dpa[id][j]=ans.a,dpb[id][j]=ans.b;
  107.     return ans;
  108. }
  110. void initn(ll n){
  112.     ht.clear();
  113.     int cnt=0;
  114.     for(ll l=1,r;l<=n;l=r+1){
  115.         r=n/(n/l);
  116.         v[++cnt]=n/l;
  117.         len[cnt]=Hash(sqr(n/l));
  118.         ht.insert(n/l,cnt);
  119.     }
  120. }
  122. //[1,n] \sigma_{p is prime}f(p)
  123. ll cal(ll n){
  124.     if(n<=1) return 0;
  125.     PLL ans=h(n,t);
  126.     return (0LL+ans.a+1-(ans.b-1))%mod;
  127. }
  129. int *G[N];
  131. ll g(ll n,int m){
  132.     if(m>=1 && pri[m]>=n) return 0;
  133.     if(m>=1 && n/pri[m]<=pri[m]){
  134.         return (cal(n)-ps[m]+mod)%mod;
  135.     }
  137.     int id=ht.query(n);
  138.     if(G[id]==NULL){
  139.         G[id] = new int[len[id]+1];
  140.         for(int i=0;i<len[id]+1;i++) G[id][i]=-1;
  141.     }
  143.     if(G[id][m]>=0) return G[id][m];
  145.     ll ans=0;
  146.     for(int i=m+1;1LL*pri[i]*pri[i]<=n;i++){
  147.         ll cur=pri[i];
  148.         for(int j=1;cur<=n;j++){
  149.             ll tmp=g(n/cur,i)+((j>1)?1:0);
  150.             (ans+=(pri[i]^j)*tmp)%=mod;
  151.             cur*=pri[i];
  152.         }
  153.     }
  154.     (ans+=cal(n)-ps[m])%=mod;
  155.     return G[id][m]=ans;
  156. }
  158. void solve(ll n){
  159.     initn(n);
  160.     ll ans=g(n,0);
  161.     cout<<(ans+1+mod)%mod<<endl;
  162. }

splay

平衡树，可以实现区间翻转

  1. struct Node{
  2.     ll x,mi,tag;
  3.     int sz;
  4.     bool rev;
  5.     Node *ch[2],*fa;
  6.     Node(){}
  7.     Node(ll x,Node* fa):x(x),fa(fa){
  8.         ch[0] = ch[1] = NULL; 
  9.         mi = x,tag = 0,rev = 0,sz = 1;
  10.     }
  11.     void pushup(){
  12.         mi = x,sz = 1;
  13.         if(ch[0]!=NULL) mi = min(mi, ch[0]->mi),sz+=ch[0]->sz;
  14.         if(ch[1]!=NULL) mi = min(mi, ch[1]->mi),sz+=ch[1]->sz;
  15.     }
  16. };
  18. //如果u是它父亲的左儿子return 0，否则return 1
  19. int son(Node* u){
  20.     return (u->fa->ch[1] == u);
  21. }
  23. //d=0 表示左旋
  24. void rotate(Node* root,int d){
  25.     Node *f = root->fa;
  26.     f->ch[d^1] = root->ch[d];
  27.     if(root->ch[d]!=NULL) root->ch[d]->fa=f;
  28.     root->fa = f->fa;
  29.     if(f->fa!=NULL) f->fa->ch[son(f)]=root;
  30.     f->fa = root;
  31.     root->ch[d] = f;
  32.     f->pushup(),root->pushup();
  33. }
  35. //把root旋转到s的儿子,rt是根节点
  36. void splay(Node *root,Node *s,Node* &rt){
  38.     while(root->fa != s){
  39.         Node *f = root->fa;
  40.         /*
  41.         rotate(root,son(root)^1);
  42.         continue;
  43.         */
  44.         if(f->fa == s){
  45.             rotate(root,son(root)^1);
  46.             break;
  47.         }
  48.         else if(son(root) == son(root->fa)){
  49.             int d = son(root);
  50.             rotate(root->fa,d^1);
  51.             rotate(root,d^1);
  52.         }
  53.         else{
  54.             int d = son(root);
  55.             rotate(root,d^1);
  56.             rotate(root,d);
  57.         }
  58.     }
  59.     if(s==NULL) rt = root;
  60. }
  62. void pushdown(Node* &root){
  64.     if(root->rev){
  65.         swap(root->ch[0],root->ch[1]);
  66.     }
  68.     if(root->ch[0]!=NULL){
  69.         root->ch[0]->rev ^= root->rev;
  70.         root->ch[0]->x += root->tag;
  71.         root->ch[0]->mi += root->tag;
  72.         root->ch[0]->tag += root->tag;
  73.     }
  74.     if(root->ch[1]!=NULL){
  75.         root->ch[1]->rev ^= root->rev;
  76.         root->ch[1]->x += root->tag;
  77.         root->ch[1]->mi += root->tag;
  78.         root->ch[1]->tag += root->tag;
  79.     }
  80.     root->rev = 0;
  81.     root->tag = 0;
  82. }
  84. const int N=2e5+10;
  86. Node node[N];
  87. int cnt;
  89. Node* newNode(ll x,Node* f){
  90.     node[cnt]=Node(x,f);
  91.     return &node[cnt++];
  92. }
  94. ll a[N];
  95. void build(Node* &root,int l,int r,Node* f){
  96.     if(l>r) return ;
  97.     int m=(l+r)>>1;
  98.     root = newNode(a[m],f);
  99.     build(root->ch[0],l,m-1,root);
  100.     build(root->ch[1],m+1,r,root);
  101.     root->pushup();
  102. }
  104. //找到序列中第x个数并将它伸展到s的儿子
  105. void search(Node* &cur,int x,Node* s,Node* &rt){
  106.     pushdown(cur);
  108.     int lsz = (cur->ch[0]==NULL)?0:cur->ch[0]->sz;
  109.     if(lsz >= x) search(cur->ch[0],x,s,rt);
  110.     else if(x == lsz+1){
  111.         splay(cur,s,rt);
  112.         return ;
  113.     }
  114.     else search(cur->ch[1],x-1-lsz,s,rt);
  115. }
  117. //处理[l,r]区间，使第l-1个数在根节点，第r+1个数在根节点的右儿子
  118. void process(Node* &root,int l,int r){
  119.     search(root,l,NULL,root);
  120.     search(root,r+2,root,root);
  121. }
  123. //[l,r]区间加d
  124. void add(Node* &root,int l,int r,int d){
  125.     process(root,l,r);
  126.     Node* k = root->ch[1]->ch[0];
  127.     k->x += d;
  128.     k->mi += d;
  129.     k->tag += d;
  130. }
  132. //翻转[l,r]区间
  133. void reverse(Node* &root,int l,int r){
  134.     process(root,l,r);
  135.     root->ch[1]->ch[0]->rev ^= 1;
  136. }
  138. //[l,r]区间左移cnt次
  139. void revolve(Node* &root,int l,int r,int cnt){
  140.     cnt %= (r-l+1);
  141.     if(!cnt) return ;
  142.     reverse(root,l,r);
  143.     reverse(root,l,l+cnt-1);
  144.     reverse(root,l+cnt,r);
  145. }
  147. //第x个数后面添加一个数p
  148. void insert(Node* &root,int x,ll p){
  149.     search(root,x+1,NULL,root);
  150.     pushdown(root);
  151.     if(root->ch[1]==NULL){
  152.         root->ch[1] = newNode(p,root);
  153.         root->pushup();
  154.         return ;
  155.     }
  157.     Node* k = root->ch[1];
  158.     while(1){
  159.         pushdown(k);
  160.         if(k->ch[0]==NULL) break;
  161.         k=k->ch[0];
  162.     }
  163.     splay(k,root,root);
  164.     k->ch[0] = newNode(p,k);
  165.     k->pushup(),root->pushup();
  166. }
  168. //删掉第x个数
  169. void del(Node* &root,int x){
  170.     search(root,x+1,NULL,root);
  171.     pushdown(root);
  172.     if(root->ch[1]==NULL){
  173.         root = root->ch[0];
  174.         root->fa = NULL;
  175.         return ;
  176.     }
  177.     Node* k = root->ch[1];
  178.     while(1){
  179.         pushdown(k);
  180.         if(k->ch[0]==NULL) break;
  181.         k=k->ch[0];
  182.     }
  183.     splay(k,root,root);
  184.     k->ch[0] = root->ch[0];
  185.     if(k->ch[0]!=NULL) k->ch[0]->fa = k;
  186.     root->ch[0] = NULL;
  187.     root = k;
  188.     if(root!=NULL) root->fa=NULL;
  189. }
  191. //[l,r]区间最小值
  192. ll min(Node* &root,int l,int r){
  193.     process(root,l,r);
  194.     pushdown(root);
  195.     pushdown(root->ch[1]);
  196.     pushdown(root->ch[1]->ch[0]);
  197.     return root->ch[1]->ch[0]->mi;
  198. }
  200. //中序遍历splay
  201. void dfs(Node* root,vector<int>& ans){
  202.     if(root==NULL) return ;
  203.     pushdown(root);
  204.     dfs(root->ch[0],ans);
  205.     ans.push_back(root->x);
  206.     dfs(root->ch[1],ans);
  207. }

treap

平衡树，比多一个求名次功能

  2. //通过赋予每个插入平衡树中的节点一个随机权值，在插入后根据权值进行旋转操作（类似堆的更新），树高O(logn)
  4. struct Node{
  5.     int x,rk,sz;
  6.     Node *ch[2];
  7.     Node(int x):x(x){
  8.         ch[0] = ch[1] = NULL;
  9.         rk = rand();sz = 1;
  10.     }
  11.     int cmp(const int& y){
  12.         if(x==y) return -1;
  13.         return x<y?0:1;
  14.     }
  15.     void pushup(){
  16.         sz=1;
  17.         if(ch[0]!=NULL) sz+=ch[0]->sz;
  18.         if(ch[1]!=NULL) sz+=ch[1]->sz;
  19.     }
  20. };
  22. void rotate(Node* &root,int d){
  23.     Node* k=root->ch[d^1];
  24.     root->ch[d^1]=k->ch[d];
  25.     k->ch[d]=root;
  26.     root->pushup();k->pushup();
  27.     root=k;
  28. }
  30. //在树上插入x，可重复
  31. void add(Node* &root,int x){
  32.     if(root == NULL){
  33.         root = new Node(x);
  34.         return ;
  35.     }
  36.     int d=root->cmp(x);
  37.     if(d==-1) d=0;
  38.     add(root->ch[d^1],x);
  39.     if(root->rk < root->ch[d^1]->rk) rotate(root,d);
  40.     root->pushup();
  41. }
  43. //在树上删除x，重复的只删除一个
  44. void remove(Node* &root,int x){
  45.     if(root==NULL) return ;
  46.     int d=root->cmp(x);
  47.     if(d==-1){
  48.         Node* k = root;
  49.         if(root->ch[0] == NULL){
  50.             root = root->ch[1];
  51.             delete(k);
  52.         }
  53.         else if(root->ch[1] == NULL){
  54.             root = root->ch[0];
  55.             delete(k);
  56.         }
  57.         else{
  58.             int d = (root->ch[0]->rk < root->ch[1]->rk) ? 0 : 1;
  59.             rotate(root,d);
  60.             remove(root->ch[d],x);
  61.         }
  62.     }
  63.     else remove(root->ch[d^1],x);
  64.     if(root!=NULL) root->pushup();
  65. }
  67. //判断树上有没有x
  68. bool has(Node* &root,int x){
  69.     if(root==NULL) return 0;
  70.     int d = root->cmp(x);
  71.     if(d==-1) return 1;
  72.     return has(root->ch[d^1],x);
  73. }
  75. //集合第k大
  76. int kth(Node* &root,int k){
  77.     if(k<=0) return 0;
  78.     // not exist
  79.     if(root == NULL) return 0;
  80.     if(root->sz < k) return 0;
  82.     int rsz = (root->ch[1]==NULL)?0:root->ch[1]->sz;
  84.     if(rsz >= k) return kth(root->ch[1],k);
  85.     else if(rsz+1 == k) return root->x;
  86.     else return kth(root->ch[0],k-1-rsz);
  87. }
  90. void removetree(Node* &root){
  91.     if(root==NULL) return ;
  92.     removetree(root->ch[0]);
  93.     removetree(root->ch[1]);
  94.     delete(root);
  95.     root=NULL;
  96. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注