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

ydc的博客

 
 
 

日志

 
 

treap 模板(真)  

2013-11-27 20:09:02|  分类: 模板 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
曾经给自己挖了个大坑
http://ydcydcy1.blog.163.com/blog/static/21608904020134162641970/
今天终于找到了一个看上去快一点点的写法

听取翱犇的建议使用指针……不过说真的我得了解一些指针这样的基础知识才行阿T_T
然后刚开始不是直接插入,而是先建好了一个笛卡尔树
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxn 50010
using namespace std;
void Read(int &digit)
{
digit=0;
char c;
for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());
bool type=true;
if(c=='-')
type=false,c=getchar();
for(;c>='0'&&c<='9';digit=digit*10+c-'0',c=getchar());
if(type==false)
digit=-digit;
}
struct Node
{
Node *lc,*rc;
bool rev;
int size,maxv,w,del,v;
}*Root,pool[maxn],*head=pool;
int n,m;
void update(Node *p)
{
p->size=1,p->maxv=p->v;
if(p->lc)
p->size+=p->lc->size,p->maxv=max(p->maxv,p->lc->maxv);
if(p->rc)
p->size+=p->rc->size,p->maxv=max(p->maxv,p->rc->maxv);
}
void add(Node *p,int v)
{
p->maxv+=v,p->del+=v,p->v+=v;
}
void rev(Node *p)
{
swap(p->lc,p->rc),p->rev^=1;
}
void push_down(Node *p)
{
if(p->del)
{
if(p->lc)
add(p->lc,p->del);
if(p->rc)
add(p->rc,p->del);
p->del=0;
}
if(p->rev)
{
if(p->lc)
rev(p->lc);
if(p->rc)
rev(p->rc);
p->rev=false;
}
}
Node* merge(Node* a,Node* b)
{
if(a==0)
return b;
if(b==0)
return a;
if(a->w>b->w)
{
push_down(a);
a->rc=merge(a->rc,b);
update(a);
return a;
}
else
{
push_down(b);
b->lc=merge(a,b->lc);
update(b);
return b;
}
}
pair<Node*,Node*> Split(Node *p,int k)
{
if(p==0)
return make_pair((Node*)0,(Node*)0);
int s=p->lc?p->lc->size:0;
push_down(p);
if(s>=k)
{
pair<Node*,Node*> tmp=Split(p->lc,k);
p->lc=tmp.second,update(p);
return make_pair(tmp.first,p);
}
else
{
pair<Node*,Node*> tmp=Split(p->rc,k-s-1);
p->rc=tmp.first,update(p);
return make_pair(p,tmp.second);
}
}
void DFS(Node *p)
{
if(p==0)
return ;
DFS(p->lc),DFS(p->rc);
update(p);
}
void read()
{
Read(n),Read(m);
for(int i=1;i<=n;++i)
{
Node *q=++head;
q->lc=0,q->rc=0,q->size=1,q->w=rand();
Root=merge(Root,q);
}
}
void Query()
{
for(int i=1,t,l,r,a;i<=m;++i)
{
Read(t);
if(t==1)
{
Read(l),Read(r),Read(a);
pair<Node*,Node*> tmp1=Split(Root,l-1);
pair<Node*,Node*> tmp2=Split(tmp1.second,r-l+1);
add(tmp2.first,a);
Root=merge(tmp1.first,merge(tmp2.first,tmp2.second));
}
if(t==2)
{
Read(l),Read(r);
pair<Node*,Node*> tmp1=Split(Root,l-1);
pair<Node*,Node*> tmp2=Split(tmp1.second,r-l+1);
rev(tmp2.first);
Root=merge(tmp1.first,merge(tmp2.first,tmp2.second));
}
if(t==3)
{
Read(l),Read(r);
pair<Node*,Node*> tmp1=Split(Root,l-1);
pair<Node*,Node*> tmp2=Split(tmp1.second,r-l+1);
printf("%d\n",tmp2.first->maxv);
Root=merge(tmp1.first,merge(tmp2.first,tmp2.second));
}
}
}
int main()
{
read();
Query();
return 0;
}
  评论这张
 
阅读(455)| 评论(3)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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