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

ydc的博客

 
 
 

日志

 
 

bzoj 1251 treap模板题  

2013-05-16 14:06:41|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
大水题
用来练习fhq的treap
结果写丑了
慢的要死
以后都不敢用了
还不明真相
我一定要改进这个模板……

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<ctime>
#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=false;
if(c=='-')
type=true,c=getchar();
for(;c>='0'&&c<='9';digit=digit*10+c-'0',c=getchar());
if(type==true)
digit=-digit;
}
int data()
{
static int seed=978263132;
seed=seed+(seed<<2)+5;
return seed;
}
int n,m;
struct Treap
{
int root,son[maxn][2],key[maxn],size[maxn];
int delta[maxn],maxv[maxn],val[maxn];
bool reverse[maxn];
void update_add(int p,int add)
{
val[p]+=add;
maxv[p]+=add;
delta[p]+=add;
}
void update_rev(int p)
{
reverse[p]^=1;
swap(son[p][0],son[p][1]);
}
void push_down(int p)
{
if(delta[p])
{
if(son[p][0])
update_add(son[p][0],delta[p]);
if(son[p][1])
update_add(son[p][1],delta[p]);
delta[p]=0;
}
if(reverse[p])
{
if(son[p][0])
update_rev(son[p][0]);
if(son[p][1])
update_rev(son[p][1]);
reverse[p]=false;
}
}
void update(int p)
{
size[p]=1,maxv[p]=val[p];
if(son[p][0])
size[p]+=size[son[p][0]],maxv[p]=max(maxv[p],maxv[son[p][0]]);
if(son[p][1])
size[p]+=size[son[p][1]],maxv[p]=max(maxv[p],maxv[son[p][1]]);
}
int merge(int a,int b)
{
if(a==0)
{
update(b);
return b;
}
if(b==0)
{
update(a);
return a;
}
push_down(a),push_down(b);
if(key[a]<key[b])
{
son[a][1]=merge(son[a][1],b);
update(a);
return a;
}
else
{
son[b][0]=merge(a,son[b][0]);
update(b);
return b;
}
}
pair<int,int> Split(int p,int k)
{
if(p==0)
return make_pair(0,0);
push_down(p);
pair<int,int> temp;
if(size[son[p][0]]+1<=k)
{
temp=Split(son[p][1],k-size[son[p][0]]-1);
son[p][1]=temp.first;
update(p);
return make_pair(p,temp.second);
}
else
{
temp=Split(son[p][0],k);
son[p][0]=temp.second;
update(p);
return make_pair(temp.first,p);
}
}
}tree;
void read()
{
Read(n),Read(m);
tree.root=1;
for(int i=1;i<=n;i++)
tree.key[i]=data();
for(int i=2;i<=n;i++)
tree.root=tree.merge(tree.root,i);
}
void ask()
{
for(int i=1,a,b,c,d;i<=m;i++)
{
Read(a);
if(a==1)
{
Read(b),Read(c),Read(d);
pair<int,int> temp1=tree.Split(tree.root,b-1);
pair<int,int> temp2=tree.Split(temp1.second,c-b+1);
tree.update_add(temp2.first,d);
tree.root=tree.merge(temp1.first,temp2.first);
tree.root=tree.merge(tree.root,temp2.second);
}
if(a==2)
{
Read(b),Read(c);
pair<int,int> temp1=tree.Split(tree.root,b-1);
pair<int,int> temp2=tree.Split(temp1.second,c-b+1);
tree.update_rev(temp2.first);
tree.root=tree.merge(temp1.first,temp2.first);
tree.root=tree.merge(tree.root,temp2.second);
}
if(a==3)
{
Read(b),Read(c);
pair<int,int> temp1=tree.Split(tree.root,b-1);
pair<int,int> temp2=tree.Split(temp1.second,c-b+1);
printf("%d\n",tree.maxv[temp2.first]);
tree.root=tree.merge(temp1.first,temp2.first);
tree.root=tree.merge(tree.root,temp2.second);
}
}
}
int main()
{
read();
ask();
return 0;
}

  评论这张
 
阅读(939)| 评论(2)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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