首页 > 代码库 > 【POJ】2892 Tunnel Warfare

【POJ】2892 Tunnel Warfare

2024-09-03 11:27:51   215人阅读

【算法】平衡树(treap)

【题解】

treap：http://dongxicheng.org/structure/treap/（似乎文中理解的旋转方向不太一样，我一般认为左旋即把右节点旋上去）

因为第一次理解旋转，详细写一下树的旋转过程，下面以右旋为例。

技术分享

void rturn(int &t)

{
     int k=tree[t].l;
     tree[t].l=tree[k].r;//让旋转后的右节点t承接原左节点k的右子树作为新左子树，同时解除k作为左节点对于t的隶属关系。
     tree[k].r=t;//将k的右节点置为t(原k的右节点已送出)。
     t=k;//赋新根便于返回。
}
右旋就是将左节点旋上去作为新根。
原根t，新根k(原根t的左节点)
本质就是原根t的左节点解放出k并更新为k的右节点。
解放出来的k的右节点更新为原根t，k本身不再隶属其它节点而是作为新根。
真正动到的节点：t的左节点(解放出k)，k的右节点(存放t)，而原k的右节点变成了t的左节点(替换过去)。
---
由于插入是从根进入的，应该可以保证左子树所有值均小于根节点，右子树所有值均大于根节点。
其它的上面给的博客链接已经说得很清楚了，可以结合代码去看。
技术分享 
#include<cstdio>
#include<algorithm>
#include<ctime>
using namespace std;
const int maxn=50010;
struct cyc{int num,w,rnd,l,r;}t[maxn*3];
int n,m,root,sz,s,tt,d[maxn];
void rr(int &tt)//右旋 
{
    int k=t[tt].l;
    t[tt].l=t[k].r;
    t[k].r=tt;
    tt=k;
}
void lr(int &tt)
{
    int k=t[tt].r;
    t[tt].r=t[k].l;
    t[k].l=tt;
    tt=k;
}
void insert(int &w,int x)
{
    if(w==0)
     {
         w=++sz;
         t[w].num=x;
         t[w].w=1;
         t[w].rnd=rand();
         return;
     }
    if(t[w].num==x){t[w].w++;return;};
    if(x<t[w].num)
     {
         insert(t[w].l,x);
         if(t[t[w].l].rnd<t[w].rnd)rr(w);
     }
    if(x>t[w].num)
     {
         insert(t[w].r,x);
         if(t[t[w].r].rnd<t[w].rnd)lr(w);
     }
}
void del(int &w,int x)
{
    if(t[w].num==x)
     {
         if(t[w].w>1)
          {
              t[w].w--;
              return;
          }
         if(t[w].l*t[w].r==0)w=t[w].l+t[w].r;//如果只有一颗子树，用这颗子树代替这个节点就可以删除了(没有子树则是用0代替之)。
          else
         if(t[t[w].l].rnd<t[t[w].r].rnd)
          {
              rr(w);
//              del(t[w].r,x);
            del(w,x);
          }
         else
          {
              lr(w);
//              del(t[w].l,x);
            del(w,x);
          }
     }
    else if(t[w].num<x)del(t[w].r,x);
     else del(t[w].l,x);
}
void find(int w,int x)
{
    if(w==0)return;
    if(t[w].num>=x&&t[w].num<tt)tt=t[w].num;
    if(t[w].num<=x&&t[w].num>s)s=t[w].num;
    if(t[w].num>x)find(t[w].l,x);
    if(t[w].num<x)find(t[w].r,x);
}
int main()
{
    srand(time(0));
    scanf("%d%d",&n,&m);
    for(int i=1,j=0;i<=m;i++)
     {
//         printf("[]");
         char c=getchar();int x;
         c=getchar();//printf("[c=%c]",c);
//         while(c<‘A‘&&c>‘Z‘)c=getchar();
         if(c==‘D‘)
          {
              scanf("%d",&x);
              insert(root,x);
              d[++j]=x;
          }
         if(c==‘R‘)del(root,d[j--]);
         if(c==‘Q‘)
          {
              s=0,tt=n+1;
              scanf("%d",&x);
              find(root,x);
              if(s==tt)printf("0\n");
              else printf("%d\n",tt-s-1);
          }
     }
    return 0;
}
View Code

在POJ把语言换成C++就过了……？？？

【POJ】2892 Tunnel Warfare


联系
我们