注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

 
 
 

日志

 
 

Treap模板( 对区间处理更方便的 fhq式的treap )  

2014-03-03 18:04:36|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
-------------------------------------------------------------------------------------------
大家可以先看看 神犇dwj的讲解
http://hi.baidu.com/wdxertqdtscnwze/item/7b6a9419be7c68cd756a8498
(请手动复制 直接超链接会出问题)
然后的话 似乎学一下左偏树对这个的理解会更好
-------------------------------------------------------------------------------------------
以下是我写的 tyvj 文艺平衡树(区间翻转) 那题的代码
又长又慢 希望有神犇来提些建议
-------------------------------------------------------------------------------------------
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define rep(i,n) for(int i=1;i<=n;++i)
#define imax(x,y) (x>y?x:y)
#define imin(x,y) (x<y?x:y)
using namespace std;
const int N=500010,BIG=2147483647;
struct treap
{
    int aux,child[2],sum,turn;
}a[N];
int n,m,root=0,t1,t2,t3,t4,k;
void update_treap(int x)
{
    a[x].sum=a[a[x].child[0]].sum+a[a[x].child[1]].sum+1;
}
void pushdown(int x)
{
    int tmp=a[x].child[0];
    a[x].child[0]=a[x].child[1];
    a[x].child[1]=tmp;
a[x].turn=0;
if(a[x].child[0])a[a[x].child[0]].turn^=1;
if(a[x].child[1])a[a[x].child[1]].turn^=1;
}
int merge_treap(int x,int y)///把以x为根的与以y为根的合并 且x内元素均不大于y内元素
{
    if(a[x].turn)pushdown(x);
    if(a[y].turn)pushdown(y);
    if(!x)return y;
    if(!y)return x;
    if(a[x].aux<=a[y].aux)
    {
        a[x].child[1]=merge_treap(a[x].child[1],y);
        update_treap(x);
        return x;
    }
    else
    {
        a[y].child[0]=merge_treap(x,a[y].child[0]);
        update_treap(y);
        return y;
    }
}
void split_treap(int &tl,int &tr,int x)
{
    if(a[x].turn)pushdown(x);
    if(a[a[x].child[0]].sum<=k)
    {
        k-=a[a[x].child[0]].sum;
        tl=merge_treap(tl,a[x].child[0]);
        a[x].child[0]=0;
        update_treap(x);
        if(k>0)
        {
            --k;
            int tx=a[x].child[1];
            a[x].child[1]=0;
            update_treap(x);
            tl=merge_treap(tl,x);
            if(tx)split_treap(tl,tr,tx);
        }
        else tr=merge_treap(tr,x);
    }
    else if(a[x].child[0])
    {
        split_treap(tl,tr,a[x].child[0]);
        a[x].child[0]=0;
        update_treap(x);
        tr=merge_treap(tr,x);
    }
}
void insert_treap(int x)
{
    if(a[x].turn)pushdown(x);
    if(a[x].child[0])
    insert_treap(a[x].child[0]);
    printf("%d ",x);
    if(a[x].child[1])
    insert_treap(a[x].child[1]);
}
int main()
{
    srand(0);
    scanf("%d%d",&n,&m);
    rep(i,n)
    {
        a[i].aux=rand();
        a[i].sum=1;
        root=merge_treap(root,i);
        update_treap(root);
    }
    int l,r,tmp;
    rep(i,m)
    {
        scanf("%d%d",&l,&r);
        if(l==r)continue;
        t1=t2=t3=t4=0;
        k=l-1;
        split_treap(t1,t2,root);
        k=r-l+1;
        split_treap(t3,t4,t2);
        root=0;
        a[t3].turn^=1;
        root=merge_treap(t1,t3);
        root=merge_treap(root,t4);
    }
    insert_treap(root);
    return 0;
}
  评论这张
 
阅读(201)| 评论(3)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017