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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

BZOJ 2827 千山鸟飞绝  

2013-03-28 11:49:58|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
vfleaking的神题,wyx神向我推荐的
结果就是卡了我一上午的常数,用尽各种方法,
最后想wyx要到数据之后,发现真得跑得好慢好慢,根本就不是treap的正常速度。。。整个人都无语了。。。就算是Splay也不会这么慢吧!!!
愤怒的我怒而换了个随机方式,采用系统的随机函数(而不是范爷的那种),结果就AC了。。。而且跑得还不算很慢囧。
到底是怎么回事呢?难道是构造的数据么,能够构造出卡掉我那个rand方式的数据,vfleaking实在是太强了。

我的算法,用的是treap+标记。。。从昨天开始就一直在写待标记的平衡树,感觉人都写傻了。
对于每个坐标,都建立平衡树,那么操作就是加点,删点,询问最大值和次大值,询问大小,将一棵树内的所有域与某个数取最大值。
这些操作都是可以很容易地用标记实现。据说函数式线段树也可做?不明觉历,离线算法也碉堡了。
主要就是卡常数啊。。。
还有为什么最近常在BZOJ上做题呢?

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<fstream>
#include<map>
#include<ctime>
#include<set>
#include<queue>
#include<cmath>
#include<vector>
#include<bitset>
#include<functional>
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
#define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
using namespace std;

typedef long long LL;
typedef double ld;

inline int ran()
{
return rand();
}

inline void up(pair<int,int>& a,pair<int,int>& b)
{
if(b.x>a.x)
{
if(a.x>b.y)
a.y=a.x;
else a.y=b.y;
a.x=b.x;
}
else //b.x<=a.x
{
if(b.x!=a.x)
{
if(b.x>a.y)
a.y=b.x;
}
else
{
if(b.y>a.y)
a.y=b.y;
}
}
}

struct node
{
int weight;
int key,size;
node *lc,*rc;

pair< pair<int,int> ,int> flag;
pair<int,int> ans;
int now;

void clear()
{
flag=mp( mp(0,0),0);
size=1;
lc=rc=0;
}

void myset(pair< pair<int,int> ,int> c)
{
up(flag.x,c.x);
if(c.y>flag.y)
{
flag.y=c.y;
if(c.y>ans.y)
ans.y=c.y;
}
if(c.x.x!=key)
{
if(c.x.x>ans.x)
ans.x=c.x.x;
}
else
{
if(c.x.y>ans.x)
ans.x=c.x.y;
}
}

void down()
{
if(!flag.x.x)
return;
if(lc)lc->myset(flag);
if(rc)rc->myset(flag);
flag=mp(mp(0,0),0);
}

void update()
{
size=1;
if(lc)
size+=lc->size;
if(rc)
size+=rc->size;
}
};

node* merge(node* a,node* b)
{
if(!a)return b;
if(!b)return a;
a->down();
b->down();
if(a->weight>b->weight)
{
a->rc=merge(a->rc,b);
a->update();
return a;
}
else
{
b->lc=merge(a,b->lc);
b->update();
return b;
}
}

pair<node*,node* > spilt(node* a,int key)
{
if(!a)return mp((node*)0,(node*)0);
pair<node*,node*> tmp;
a->down();
if(a->key<key)
{
tmp=spilt(a->rc,key);
a->rc=tmp.x;
a->update();
return mp(a,tmp.y);
}
else
{
tmp=spilt(a->lc,key);
a->lc=tmp.y;
a->update();
return mp(tmp.x,a);
}
}

node* insert(node* a,node* p)
{
if(!a)
return p;
a->down();
if(p->weight<a->weight)
{
if(a->key<p->key)
a->rc=insert(a->rc,p);
else
a->lc=insert(a->lc,p);
a->update();
return a;
}
else
{
pair<node*,node*> tmp=spilt(a,p->key);
p->lc=tmp.x;
p->rc=tmp.y;
p->update();
return p;
}
}

node* delit(node* r,node* u)
{
r->down();
if(r==u)
return merge(u->lc,u->rc);
else
{
if(r->key<u->key)
r->rc=delit(r->rc,u);
else r->lc=delit(r->lc,u);
r->update();
return r;
}
}

pair<int,int> mx;

void get(node* r)
{
if(!r)return;
get(r->rc);
if(mx.y)return;
if(mx.x)
{
mx.y=r->key;
return;
}
else mx.x=r->key;
get(r->lc);
}

typedef pair<int,int> point;
vector<point> cc;

const int NUM=30000+10;
const int MAX=650000+10;

struct Event
{
int t,v;
int flag;
point aim;
Event(int a,int b,int c,point d)
{
t=a;
v=b;
flag=c;
aim=d;
}
Event(){}
}t[MAX];
int top;

int operator < (const Event& a,const Event& b)
{
if(a.t!=b.t)return a.t<b.t;
else return a.flag<b.flag;
}

int n,T;
node tree[NUM],*root[MAX];

int find(point a)
{
return lower_bound(cc.begin(),cc.end(),a)-cc.begin();
}

void del(node* u)
{
int tmp=u->now;
node* r=root[tmp];
root[tmp]=delit(r,u);
}

pair<int,int> num[NUM];

int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#endif
int i,x,y;
scanf("%d",&n);
REP(i,1,n)
{
scanf("%d%d%d",&tree[i].key,&x,&y);
num[i]=mp(tree[i].key,i);
t[++top]=Event(0,i,1,mp(x,y));
cc.pb(mp(x,y));
}
sort(num+1,num+n+1);
REP(i,1,n)
{
int c=num[i].y;
tree[c].key=i;
tree[c].weight=ran();
tree[c].clear();
tree[c].ans=mp(0,0);
}
scanf("%d",&T);
REP(i,1,T)
{
int a;
scanf("%d%d%d",&a,&x,&y);
t[++top]=Event(i,a,-1,mp(0,0));
t[++top]=Event(i,a,1,mp(x,y));
cc.pb(mp(x,y));
}
sort(cc.begin(),cc.end());
cc.erase(unique(cc.begin(),cc.end()),cc.end());
sort(t+1,t+top+1);
REP(i,1,top)
{
int tmp;
node* u=t[i].v+tree;
if(t[i].flag==1)
{
node* r=root[tmp=find(t[i].aim)];
u->now=tmp;
u->clear();
u->weight=ran();
root[tmp]=r=insert(r,u);
if(r->size>1)
{
mx=mp(0,0);
get(r);
pair< pair<int,int> ,int> p=mp(mx,r->size-1);
r->down();
r->myset(p);
}
}
else if(t[i].flag==-1)
del(u);
}
REP(i,1,n)
{
del(tree+i);
printf("%lld\n",(LL)num[tree[i].ans.x].x*tree[i].ans.y);
}
return 0;
}



  评论这张
 
阅读(822)| 评论(4)
推荐 转载

历史上的今天

评论

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

页脚

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