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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

【数据结构】【BZOJ1500】维修数列 + 有关垃圾回收的测试  

2014-05-07 11:19:45|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
@BZOJ1500: [NOI2005]维修数列
splay维护序列裸题
我调了一天多……
感觉该回家养猪了Orz

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<queue>
using namespace std;
const int _MAX = 1000000000;
int dede;
struct Node{
int d,s,size;
int lmax,rmax,Max;
short rota,add;
bool fadd;
Node *fa,*ch[2];
Node(){s=size=0;}
Node(Node *l){fa=ch[0]=ch[1]=l;d=s=size=0;lmax=Max=rmax=fadd=add=rota=0;}
int pl(){return fa->ch[1]==this;}
inline void count(){
s=ch[0]->s+d+ch[1]->s;
size=ch[0]->size+1+ch[1]->size;
lmax=rmax=Max=-_MAX;
//lmax
if(ch[0]->size > 0){
if(ch[0]->s+d>lmax){lmax=ch[0]->s+d;}
if(ch[1]->lmax > 0){lmax+=ch[1]->lmax;}
if(ch[0]->lmax > lmax){lmax=ch[0]->lmax;}
}else{
lmax=d;
if(ch[1]->lmax > 0){lmax+=ch[1]->lmax;}
}
//rmax
if(ch[1]->size > 0){
if(ch[1]->s+d>rmax){rmax=ch[1]->s+d; }
if(ch[0]->rmax > 0){rmax+=ch[0]->rmax;}
if(ch[1]->rmax > rmax){rmax=ch[1]->rmax;}
}else{
rmax=d;
if(ch[0]->rmax > 0){rmax+=ch[0]->rmax;}
}
//max all
if(rmax<lmax){Max=lmax;}
else{Max=rmax;}
if(ch[0]->rmax+d+ch[1]->lmax>Max)
{Max=ch[0]->rmax+d+ch[1]->lmax;}
//*
if(d > Max)Max=d;
if(ch[1]->size > 0){
if(ch[1]->lmax + d > Max) Max=ch[1]->lmax + d;
if(ch[1]->lmax > Max) Max=ch[1]->lmax;
if(ch[1]->Max > Max)Max=ch[1]->Max;
}
if(ch[0]->size > 0){
if(ch[0]->rmax + d > Max) Max=ch[0]->rmax + d;
if(ch[0]->rmax > Max) Max=ch[0]->rmax;
if(ch[0]->Max > Max)Max=ch[0]->Max;
}

}
inline void set(int a){
add=d=a;
fadd=1;
s=size*a;
if(a>0)
Max=lmax=rmax=s;
else
Max=lmax=rmax=a;
}
inline void Swap(){
rota^=1;
swap(ch[0],ch[1]);
swap(lmax,rmax);
}
inline void pushdown(){
if(rota){//rotate
ch[0]->Swap();
ch[1]->Swap();
rota=0;
}
if(fadd){//*
ch[0]->set(add);
ch[1]->set(add);
add=0;
fadd=0;
}
}
}*null,house[500000];
int top=0;
const int N = 300000+1;
queue<Node *>pupa;
int data[N];
inline Node *newNode(){
if(pupa.empty()){
if(top<500000){
house[top]=Node(null);
return &house[top++];
}else return new Node(null);
}
Node *re=pupa.front();
pupa.pop();
*re = Node(null);
return re;
}
inline void del(Node *&r){pupa.push(r);r=null;}
inline int scan(){
char cc=' ';int re=0,fh=1;
while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='-'){fh=-1;cc=getchar();}
if(cc=='+'){fh=1;cc=getchar();}
while('0'<=cc&&cc<='9'){
re=re*10+cc-'0';
cc=getchar();
}
return re*fh;
}
class Splay{
public:
Node *ROOT;
int lenth;
inline void Build(int n){
ROOT=newNode();
ROOT->ch[1]=newNode();
ROOT->ch[1]->fa=ROOT;
ROOT->ch[1]->ch[0]=build(1,n,ROOT->ch[1]);
ROOT->ch[1]->count();
ROOT->count();
lenth=n+2;
}
inline void work(int t){
int pos,n,i,j;Node *r;
if(t==1){//insert
pos=scan()+1;n=scan();
for(i=1;i<=n;i++)
data[i]=scan();
pack(pos,pos+1);
ROOT->ch[1]->ch[0]=build(1,n,ROOT->ch[1]);
ROOT->ch[1]->count();
ROOT->count();
lenth+=n;
}else if(t==2){//delete
pos=scan()+1;n=scan();
pack(pos-1,pos+n);
Delete(ROOT->ch[1]->ch[0]);
ROOT->ch[1]->count();
ROOT->count();
lenth-=n;
}else if(t==3){//make-sum
pos=scan()+1;n=scan();
pack(pos-1,pos+n);
r=ROOT->ch[1]->ch[0];
r->pushdown();
r->set(scan());
}else if(t==4){//reverse
pos=scan()+1;n=scan();
pack(pos-1,pos+n);
r=ROOT->ch[1]->ch[0];
r->Swap();
}else if(t==5){//get-sum
pos=scan()+1;n=scan();
pack(pos-1,pos+n);
dede++;
printf("%d\n",ROOT->ch[1]->ch[0]->s);
}else if(t==6){//max-sum
pack(1,lenth);
dede++;
printf("%d\n",ROOT->ch[1]->ch[0]->Max);
}else if(t==7){
pos=scan()+1;n=scan();
Print(pos-1,pos+n-1-1);
}
}
private:
inline void Print(int l,int r){
pack(l,r+2);
print(ROOT->ch[1]->ch[0]);
printf("\n");
}
inline void print(Node *r){
if(r==null)return;
r->pushdown();
print(r->ch[0]);
printf("%d ",r->d);
print(r->ch[1]);
}
inline Node *build(int l,int r,Node *fa){
if(r<l) return null;
Node *ro=newNode();
int mid=(l+r)/2;
ro->d=data[mid];
ro->fa=fa;
if(l<r){
ro->fa=fa;
ro->ch[0]=build(l,mid-1,ro);
ro->ch[1]=build(mid+1,r,ro);
}
ro->count();
return ro;
}
inline void Delete(Node *&r){
if(r->ch[0]!=null) Delete(r->ch[0]);
if(r->ch[1]!=null) Delete(r->ch[1]);
del(r);
}
inline void rotate(Node *k){
Node *r=k->fa;int x=k->pl()^1;
if(r==null||k==null) return;
k->pushdown();
r->ch[x^1]=k->ch[x];
r->ch[x^1]->fa=r;
if(r->fa!=null){r->fa->ch[r->pl()] = k;}
else ROOT=k;
k->ch[x]=r;
k->fa=r->fa;r->fa=k;
r->count();k->count();
}
void splay(Node *r,Node *tar=null){
if(r==null) return;
for(;r->fa!=tar;rotate(r))
if(r->fa->fa!=tar)
rotate(r->pl()!=r->fa->pl()?r:r->fa);
}
inline Node *kth(Node *r,int k){
while(r!=null){
r->pushdown();
if(k<=r->ch[0]->size) r=r->ch[0];
else if(k<=r->ch[0]->size+1) return r;
else {k-=r->ch[0]->size+1;r=r->ch[1];}
}
printf("%c",7);
}
inline void pack(int l,int r){
Node *ro;
ro=kth(ROOT,l);
splay(ro);
ro=kth(ROOT,r);
splay(ro,ROOT);
}
}Stree;
int main(){
int i,j,n,m;
char ops[20];
n=scan();m=scan();
null=newNode(); *null=Node(null);
Stree.ROOT=null;
for(i=1;i<=n;i++)
data[i]=scan();
Stree.Build(n);
for(i=1;i<=m;i++){
scanf("%s",ops);
if(ops[0]=='I') j=1;
if(ops[0]=='D') j=2;
if(ops[2]=='K') j=3;
if(ops[0]=='R') j=4;
if(ops[0]=='G') j=5;
if(ops[2]=='X') j=6;
if(ops[0]=='P') j=7;
Stree.work(j);
if(dede==-1)
printf("%s\n",ops);
}
return 0;
}

有关垃圾回收效率的测试:
1:我一开始的写法,一开始全部用New,删除时指针放到‘内存池’里,之后再拿来用
2:全部用New,并且删除子树的时候用O(n)把每个赋成null
3:全部用New,并且删除子树的时候O(1)把子树甩掉
4:Wangxz神犇的写法,事先开一个数组,申请的时候优先取数组里的,如果数组满了或者’内存池‘空再用New
0:乱搞写法,事先开一个数组,把数组的所有元素指针放到‘内存池‘
正常
【数据结构】【BZOJ1500】维修数列 + 有关垃圾回收的测试 - 时光机 - 时光机TimeMachine
O2优化
【数据结构】【BZOJ1500】维修数列 + 有关垃圾回收的测试 - 时光机 - 时光机TimeMachine
2,3写法不仅慢(部分点会T,这里我时限开得比较大)而且会MLE
2号写法为了防MLE我把所有点赋null都改成了delete,结果……跑了15秒,50%的测试点时间超过2s
可见当题目有大量删除的时候一定要加垃圾回收
虽然要O(n)删除子树,但是这个浪费的时间几乎就是九牛一毛
最后再看一下事先申请数组的写法
在总时间这里整整少了1s
(之前有一次写Dinic,new出来的邻接表跑了10s,而Next数组跑了5s)
不过有了这个写法,就算是用指针也可以达到和数组一样的申请速度了
妈妈再也不用担心我被new卡常数了
感谢Wangxz神犇 OrzOrz
  评论这张
 
阅读(38)| 评论(5)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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