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

 
 
 

日志

 
 

bzoj 1091 ( zju2112 ) & vijos 1665 树套树模板题  

2014-03-18 15:20:09|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
第二道碰到的树套树 这次就没直接抄别人的了 自己写了个 顺便又把treap复习了遍
由于这种题还没多大感受 大家可以看看z55250825
以下是代码额:
#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)
#define id(l,r) (l+r|l!=r)
using namespace std;
const int N=10010,M=N*30;
struct treap
{
    int child[2],num,sum,aux;
}a[M];
int root[N<<1],b[N];
int n,m,len=0,tmpaux,ql,qr;
void update_treap(int x)
{
    a[x].sum=a[a[x].child[0]].sum+a[a[x].child[1]].sum+1;
}
void rotate_treap(int &x,int t)
{
    int y=a[x].child[t];
    a[x].child[t]=a[y].child[t^1];
    a[y].child[t^1]=x;
    update_treap(x);
    update_treap(y);
    x=y;
}
void insert_treap(int &x,int y)
{
    if(x)
    {
        int t=y>a[x].num;
        insert_treap(a[x].child[t],y);
        if(a[a[x].child[t]].aux<a[x].aux)
        rotate_treap(x,t);
    }
    else
    {
        x=++len;
        a[x].num=y;
        a[x].aux=tmpaux;
        a[x].sum=1;
    }
    update_treap(x);
}
void delete_treap(int &x,int y)
{
    if(a[x].num==y)
    {
        if(!a[x].child[0]&&!a[x].child[1])
        {x=0;return;}
        if(a[x].child[0]&&!a[x].child[1])
        {
            rotate_treap(x,0);
            delete_treap(a[x].child[1],y);
        }
        else if(!a[x].child[0]&&a[x].child[1])
        {
            rotate_treap(x,1);
            delete_treap(a[x].child[0],y);
        }
        else
        {
            int t=a[a[x].child[0]].aux>a[a[x].child[1]].aux;
            rotate_treap(x,t);
            delete_treap(a[x].child[t^1],y);
        }
    }
    else
    delete_treap(a[x].child[a[x].num<y],y);
    update_treap(x);
}
int findsum_treap(int x,int y)
{
    if(!x)return 0;
    if(a[x].num<=y)
    return findsum_treap(a[x].child[1],y)+a[a[x].child[0]].sum+1;
    else
    return findsum_treap(a[x].child[0],y);
}
int trydo(int x,int L,int R)
{
    int mid,gain=0;
    mid=(L+R)>>1;
    if(ql<=L&&qr>=R)
    {
        gain=findsum_treap(root[id(L,R)],x);
        return gain;
    }
    if(ql<=mid)gain+=trydo(x,L,mid);
    if(qr>mid)gain+=trydo(x,mid+1,R);
    return gain;
}
int main()
{
    int L,R,mid,k;
    char ch[5];
    scanf("%d%d",&n,&m);
    srand(0);
    rep(i,n)
    {
        scanf("%d",&b[i]);
        L=1,R=n;
        tmpaux=rand();
        while(insert_treap(root[id(L,R)],b[i]),L<R)
        {
            mid=(L+R)>>1;
            if(i<=mid)R=mid;
            else L=mid+1;
        }
    }
    rep(i,m)
    {
        scanf("%s",ch);
        if(ch[0]=='Q')
        {
            scanf("%d%d%d",&ql,&qr,&k);
            L=0,R=1000000000;
            while(L<R)
            {
                mid=(L+R)>>1;
                if(trydo(mid,1,n)>=k)R=mid;
                else L=mid+1;
            }
            printf("%d\n",R);
        }
        else
        {
            scanf("%d%d",&ql,&qr);
            L=1,R=n;
            tmpaux=rand();
            while(L<=R)
            {
                delete_treap(root[id(L,R)],b[ql]);
                insert_treap(root[id(L,R)],qr);
                if(L==R)break;
                mid=(L+R)>>1;
                if(ql<=mid)R=mid;
                else L=mid+1;
            }
            b[ql]=qr;
        }
    }
    return 0;
}

  评论这张
 
阅读(61)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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