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

ydc的博客

 
 
 

日志

 
 

bzoj 2658(zjoi2012) 小蓝的好友(mrx)  

2013-05-16 09:04:26|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
第一次学treap,拿着道题当入门
首先补集转化
然后用fhq式的treap
一条扫描线不断向上扫,对每一列,维护这条扫描线在这一列上的点能向下走多少步,不妨称之为高度。我们treap有个随机值,在这道题就用这个高度当随机值,至于平衡树的权值自然就是第几列。这样的话,由于数据是随机生成,所以高度也是随机的,所以treap就是期望log n了
每次扫描线向上扫,就把每个点的高度值++。由于有黑点,我们就把黑点处的点的高度值赋为0。
如何统计答案呢?
根据treap每个点的高度,我们可以把矩形给分割成若干个块块。比如这条扫描线向下能走的步数是3,1,4,我们就可以抽象成三个矩形:一个1*3的,一个2*1的,一个3*1的。
而丢到treap里,应该是个这样的结构:根节点是(2,1),左儿子是(1,3),右儿子是(3,4)
左右儿子对应的矩形块能得到多少解呢?以左儿子为例,假设左儿子是x,正好就是(height[x]-height[p])*size[x]*(size[x]+1)/2,因为在左儿子的这棵子树上,左儿子的这个矩形能随意延伸。
然后就可以出解了
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxn 100010
using namespace std;
typedef long long LL;
struct Treap
{
int son[maxn][2],delta[maxn],root;
LL ans[maxn],size[maxn],h[maxn],v[maxn];
void add(int p,int add)
{
h[p]+=add;
delta[p]+=add;
}
void push_down(int p)
{
if(delta[p])
{
if(son[p][0])
add(son[p][0],delta[p]);
if(son[p][1])
add(son[p][1],delta[p]);
delta[p]=0;
}
}
void update(int p)
{
size[p]=1,ans[p]=0;
push_down(p);
int x=son[p][0],y=son[p][1];
if(x)
{
size[p]+=size[x];
ans[p]=ans[p]+ans[x]+size[x]*(size[x]+1)/2*(h[x]-h[p]);
}
if(y)
{
size[p]+=size[y];
ans[p]=ans[p]+ans[y]+size[y]*(size[y]+1)/2*(h[y]-h[p]);
}
}
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);
}
}
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(h[a]<h[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;
}
}
LL getans()
{
push_down(root);
return ans[root]+h[root]*size[root]*(size[root]+1)/2;
}
}tree;
void Read(LL &digit)
{
digit=0;
char c;
for(c=getchar();c<'0'||c>'9';c=getchar());
for(;c>='0'&&c<='9';digit=digit*10+c-'0',c=getchar());
}
void read()
{
LL n,m,p,ans;
static pair<LL,LL> point[maxn];
Read(n),Read(m),Read(p);
for(int i=1;i<=p;i++)
Read(point[i].first),Read(point[i].second);
sort(point+1,point+p+1);
for(int i=1;i<=m;i++)
{
tree.root=tree.merge(tree.root,i);
tree.update(tree.root);
}
ans=n*(n+1)/2*m*(m+1)/2;
for(int i=1,j=1;i<=n;i++)
{
tree.add(tree.root,1);
for(;point[j].first==i;j++)
{
pair<int,int> temp1=tree.Split(tree.root,point[j].second-1);
pair<int,int> temp2=tree.Split(temp1.second,1);
tree.h[temp2.first]=0;
tree.root=tree.merge(temp1.first,temp2.first);
tree.root=tree.merge(tree.root,temp2.second);
}
ans=ans-tree.getans();
}
printf("%lld\n",ans);
}
int main()
{
read();
return 0;
}


  评论这张
 
阅读(1221)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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