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

ydc的博客

 
 
 

日志

 
 

bzoj 1901 & bzoj 1500 (dynamic rankings & 维修序列)  

2013-04-06 22:21:43|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
今天上午听翱犇虐人,然后把与上午东西毫不相关的东西搞了……
1901我不知道我是用的函数式线段树还是主席树啊囧……以后对于函数式线段树有必要小小的做个总结,至少现在我还不是特别清晰,因为只做了两道题(还有一个是Poj那个划分树的题,无修改的区间K大值)
1500是很久以前就听说过了的。本着连括号修复都写过应该不会怕维修序列的心情来写
先是一些小的编译错误or细节错误
然后由于新建了最左最右两个节点,而这道题又不是我常见的输入[l,r],结果对于区间+1,-1的纠结导致我调了一阵子(以前都是直接XX(l,r+2),XX是函数名)
再稍微和暴力对拍了一下就没有WA了
不过超时……
猛然发现傻×到了连读入优化都没加的程度
赶快加了
还是超时
加inline
用处不大……
最后还是决定把insert函数重写一下算了

众所周知,splay中,在某个数后面加若干个数需要递归建一棵完全平衡的splay,然后再接起来。我偷懒想暴力建看卡不卡的过。
事实上是卡不过的
老老实实地建树就能过了
不过还是写的好丑的
慢的要死

接下来就是贴代码,1901我不打算贴了。
犹豫了一下,要不要把调试函数去掉
不过方便大家对拍+更加自然一些,就不去了吧

调用函数tree.print(tree.root),可以将序列打出,便于调试

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 500010
#define INF 100000000
using namespace std;
int n,m,digit[MAXN],stack[MAXN],top;
struct node
{
int root,v[MAXN],son[MAXN][2],father[MAXN],size[MAXN],maxpre[MAXN],maxsub[MAXN],maxsum[MAXN],sum[MAXN],set[MAXN];
bool reverse[MAXN],same[MAXN];
void update(int p)
{
size[p]=size[son[p][0]]+size[son[p][1]]+1;
sum[p]=sum[son[p][0]]+sum[son[p][1]]+v[p];
maxpre[p]=max(max(maxpre[son[p][0]],sum[son[p][0]]+v[p]),sum[son[p][0]]+v[p]+maxpre[son[p][1]]);
maxsub[p]=max(max(maxsub[son[p][1]],sum[son[p][1]]+v[p]),sum[son[p][1]]+v[p]+maxsub[son[p][0]]);
maxsum[p]=max(max(maxsum[son[p][0]],maxsum[son[p][1]]),max(maxsub[son[p][0]]+v[p],maxpre[son[p][1]]+v[p]));
maxsum[p]=max(max(maxsum[p],maxsub[son[p][0]]+v[p]+maxpre[son[p][1]]),v[p]);
}
void update_rev(int p)
{
reverse[p]^=1;
swap(son[p][0],son[p][1]),swap(maxpre[p],maxsub[p]);
}
void update_set(int p,int k)
{
same[p]=true,set[p]=k,v[p]=k,sum[p]=k*size[p];
maxpre[p]=maxsub[p]=maxsum[p]=max(sum[p],k);
}
void push_down(int p)
{
if(reverse[p])
{
if(son[p][0]) update_rev(son[p][0]);
if(son[p][1]) update_rev(son[p][1]);
reverse[p]=false;
}
if(same[p])
{
if(son[p][0]) update_set(son[p][0],set[p]);
if(son[p][1]) update_set(son[p][1],set[p]);
same[p]=false;
}
}
int Build(int l,int r)
{
int p=stack[top--],mid=(l+r)>>1;
v[p]=digit[mid];
if(l<mid)
{
int q=Build(l,mid-1);
father[q]=p,son[p][0]=q;
}
if(mid<r)
{
int q=Build(mid+1,r);
father[q]=p,son[p][1]=q;
}
update(p);
return p;
}
void Rotate(int p,int x)
{
int set=p==son[x][1],y=son[p][set^1],z=father[x];
if(y!=0) father[y]=x;
if(x==son[z][0]) son[z][0]=p;
if(x==son[z][1]) son[z][1]=p;
son[p][set^1]=x,father[p]=z,son[x][set]=y,father[x]=p,update(x);
}
void Splay(int p,int k)
{
push_down(p);
while(father[p]!=k)
{
int x=father[p],y=father[x];
push_down(y),push_down(x),push_down(p);
if(y==k) Rotate(p,x);
else if((p==son[x][0])^(x==son[y][0])) Rotate(p,x),Rotate(p,y);
else Rotate(x,y),Rotate(p,x);
}
if(k==0) root=p;
update(p);
}
int Select(int rank,int k)
{
int p=root;
push_down(p);
while(size[son[p][0]]+1!=rank)
{
if(size[son[p][0]]+1<rank) rank=rank-size[son[p][0]]-1,p=son[p][1];
else p=son[p][0];
push_down(p);
}
Splay(p,k);
return p;
}
void Insert(int k,int a[],int n)
{
int x=Select(k,0),y=Select(k+1,x),p=Build(1,n);
son[y][0]=p,father[p]=y,Splay(p,0);
}
void Delete(int l,int r)
{
int x=Select(l,0),y=Select(r,x);
static int queue[MAXN];
int front=0,rear=1;
queue[rear]=son[y][0],son[y][0]=0;
while(front<rear)
{
int p=queue[++front];
if(son[p][0]) queue[++rear]=son[p][0];
if(son[p][1]) queue[++rear]=son[p][1];
}
for(int i=1;i<=rear;i++)
{
int p=queue[i];
if(top<=500000) stack[++top]=p;
v[p]=son[p][0]=son[p][1]=father[p]=size[p]=maxpre[p]=maxsub[p]=maxsum[p]=sum[p]=set[p]=0;
reverse[p]=same[p]=false;
}
Splay(y,0);
}
void Set(int l,int r,int v)
{
int x=Select(l,0),y=Select(r,x);
update_set(son[y][0],v),Splay(son[y][0],0);
}
void Reverse(int l,int r)
{
int x=Select(l,0),y=Select(r,x);
update_rev(son[y][0]),Splay(son[y][0],0);
}
int Getsum(int l,int r)
{
int x=Select(l,0),y=Select(r,x);
return sum[son[y][0]];
}
void print(int p)
{
if(p==0) return ;
push_down(p);
print(son[p][0]);
if(p!=1&&p!=n) printf("%d ",v[p]);
print(son[p][1]);
}
}tree;
void Read(int &digit)
{
digit=0;
char c;
for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());
bool type=true;
if(c=='-') c=getchar(),type=false;
for(;c>='0'&&c<='9';digit=digit*10+c-'0',c=getchar());
if(type==false) digit=-digit;
}
void read()
{
Read(n),Read(m);
tree.maxpre[0]=tree.maxsum[0]=tree.maxsub[0]=-INF;
n+=2,digit[1]=digit[n]=-INF;
for(int i=2;i<=n-1;i++)
Read(digit[i]);
for(int i=500000;i>=1;i--)
stack[++top]=i;
tree.root=tree.Build(1,n);
}
void work()
{
char task[15];
int a,b,c;
for(int i=1;i<=m;i++)
{
scanf("%s",task);
if(strcmp(task,"INSERT")==0)
{
Read(a),Read(b);
for(int j=1;j<=b;j++)
Read(digit[j]);
tree.Insert(a+1,digit,b);
}
if(strcmp(task,"DELETE")==0)
{
Read(a),Read(b);
tree.Delete(a,a+b+1);
}
if(strcmp(task,"MAKE-SAME")==0)
{
Read(a),Read(b),Read(c);
tree.Set(a,a+b+1,c);
}
if(strcmp(task,"REVERSE")==0)
{
Read(a),Read(b);
tree.Reverse(a,a+b+1);
}
if(strcmp(task,"GET-SUM")==0)
{
Read(a),Read(b);
printf("%d\n",tree.Getsum(a,a+b+1));
}
if(strcmp(task,"MAX-SUM")==0) printf("%d\n",tree.maxsum[tree.root]);
}
}
int main()
{
read();
work();
return 0;
}


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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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