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

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

主席树初学  

2014-07-05 20:51:52|  分类: 算法杂类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
主席树,在GT的讲解下我收益很大,于是就A了两题,一题是裸的主席树:poj2104,,无修改。
先贴下自己写的模板:求区间第k大无修改。
每颗线段树i,其实代表的是1-i权值的前缀和,线段树记得是权值,维护size。然后由于i+1颗线段树与i颗线段树唯一的区别就是多了一个新的元素,即某条链上更新size,其余直接继承,指向;
有注释
#include<cstdio>
#include<algorithm>
#define ls tree[t].l
#define rs tree[t].r
#define mid ((l+r)>>1)
#define nn 100005
using namespace std;
struct node{int l,r,size;}tree[nn*30];
int a[nn],b[nn],root[nn];
int n,N,i,tot,ans,m,k,p,x,y; 

void build(int l,int r,int t)
 {if (l==r)return;
  ls=++tot;rs=++tot;
  build(l,mid,ls);
  build(mid+1,r,rs);
 }//初始树
 
int find(int w)
 {return lower_bound(b+1,b+N+1,w)-b;}找到其真正排名
 
void insert(int ll,int l,int r,int t,int tt)
 {tree[t].size++;
  if (l==r)return;
  if (ll<=mid){tree[++tot]=tree[tree[tt].l]; 
               ls=tot;
               insert(ll,l,mid,ls,tree[tt].l);
              }else
              {tree[++tot]=tree[tree[tt].r];
               rs=tot;
               insert(ll,mid+1,r,rs,tree[tt].r);
              }
 }//沿途更新新的一个线段树,其余直接继承(指向);故其实才开了nlogn个结点;
void ask(int l,int r,int t,int tt)
 {if (l==r){ans=l;return;}
  if (tree[ls].size-tree[tree[tt].l].size>=k)ask(l,mid,ls,tree[tt].l);
  else {k-=(tree[ls].size-tree[tree[tt].l].size);
        ask(mid+1,r,rs,tree[tt].r);
       }
 }//类似splay中找排名
inline int read()
{
  int x=0;char ch=getchar();bool positive=1;
  for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') positive=0;
  for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
  return positive?x:-x;
}
int main()
{
 n=read();m=read();
 for (i=1;i<=n;i++)a[i]=read(),b[i]=a[i];
 sort(b+1,b+n+1);N=0;
 b[0]=1000000001;
 for (i=1;i<=n;i++)if (b[i]!=b[i-1])b[++N]=b[i];
 
 root[0]=++tot;
 build(1,N,tot);
 for (i=1;i<=n;i++){
      root[i]=++tot; 
      tree[tot]=tree[root[i-1]];
      p=find(a[i]);
      insert(p,1,N,root[i],root[i-1]);
                   }
 
 for (i=1;i<=m;i++)
           {x=read();y=read();k=read();
            ask(1,N,root[y],root[x-1]);
            printf("%d\n",b[ans]);
           }
return 0;
}
另一道便是bzoj1901在上题的基础上带修改,那么就像前缀和若要修改就得写树状数组了。。
于是第一道树套数诞生,代码:
#include<cstdio>
#include<algorithm>
#define ls tree[t].l
#define rs tree[t].r
#define mid ((l+r)>>1)
#define nn 10010
using namespace std;
struct node{int l,r,si;}tree[nn*400];
struct node2{int l,r,id,si;}q[nn];
int tot,ans,k,s4,p,N,j,s5,i,n,m,NN;
int b[nn*3],a[nn],qq[nn],pp[nn],root[nn];
char c[3];

void build(int l,int r,int t)
 {if (l==r)return;
  ls=++tot;rs=++tot;
  build(l,mid,ls);
  build(mid+1,r,rs);
 }
int find(int w)
 {return lower_bound(b+1,b+NN+1,w)-b;
 }
void insert(int ll,int l,int r,int t,int s)
 {tree[t].si+=s;
 if (l==r)return;
 if (ll<=mid){tree[++tot]=tree[ls];
              ls=tot;
              insert(ll,l,mid,ls,s);
             }else
             {tree[++tot]=tree[rs];
              rs=tot;
              insert(ll,mid+1,r,rs,s);
             }
 }
void findans(int l,int r)
 {int i;
  if (l==r) {ans=l;return;}
    int lsum=0,rsum=0;
    for (i=1;i<=s4;i++)
      lsum+=tree[tree[qq[i]].l].si;
     for (i=1;i<=s5;i++)
      rsum+=tree[tree[pp[i]].l].si;
     if (rsum-lsum>=k) 
     { for (i=1;i<=s4;i++)
         qq[i]=tree[qq[i]].l;
       for (i=1;i<=s5;i++)
         pp[i]=tree[pp[i]].l;
       findans(l,(l+r)>>1);
     }
     else { for (i=1;i<=s4;i++)
         qq[i]=tree[qq[i]].r;
       for (i=1;i<=s5;i++)
         pp[i]=tree[pp[i]].r;
         k-=(rsum-lsum);
       findans(((l+r)>>1)+1,r);
       }
}
void ask(int l,int r)
 {s4=s5=0;int i;
  for (i=l-1;i;i-=i&(-i))qq[++s4]=root[i];
  for (i=r;i;i-=i&(-i))pp[++s5]=root[i];
  findans(1,NN);
  printf("%d\n",b[ans]);
 }
int main()
{
 scanf("%d%d",&n,&m);
 for(i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];
 N=n;
 for(i=1;i<=m;i++)
  {scanf("%s",c);
   if (c[0]=='Q'){scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].si);q[i].id=1;}
   else {scanf("%d%d",&q[i].l,&q[i].r);b[++N]=q[i].r;}
  }
b[0]=-1;
 sort(b+1,b+N+1);NN=0;
 for (i=1;i<=N;i++)if (b[i]!=b[i-1])
                    b[++NN]=b[i];
 root[0]=++tot;
 build(1,NN,tot);
 for (i=1;i<=n;i++){
     root[i]=++tot;
     tree[tot]=tree[1];
                   }
 for (i=1;i<=n;i++){p=find(a[i]);
  for (j=i;j<=n;j+=j&(-j))insert(p,1,NN,root[j],1);
                   }
 for (i=1;i<=m;i++)
  if (!q[i].id){
   for (j=q[i].l;j<=n;j+=j&(-j))insert(find(a[q[i].l]),1,NN,root[j],-1);
   for (j=q[i].l;j<=n;j+=j&(-j))insert(find(q[i].r),1,NN,root[j],1);
   a[q[i].l]=q[i].r;
               }else
               {k=q[i].si;
                ask(q[i].l,q[i].r);
                }
 return 0;
}
  评论这张
 
阅读(8427)| 评论(19)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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