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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

ZJOI2012 小蓝的好友  

2013-03-27 11:30:09|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
其实很早就写过这道题了,至于为何现在又来写呢?因为有个学弟一直在纠结这道题,好心好意的我就决定重新研究一下这题(忘了丽洁的算法了,结果以前的代码就看不懂。。。),qzc大神讲题时我又临时yy了一个,一直怀疑其正确性,正好刚刚才研究完treap的另一种写法,用来做这道题是再合适不过了。于是花了点时间顺手又写了一遍(其实发现这题和treap的关系之后真的就是随手切了)。
讲讲算法吧,首先补集转化,将其变成统计没有空格的个数。
然后扫描线,统计以每一层为底边的空白矩形个数。那么影响答案的就只有该列的高度
比如说高度为(1,1,1),那么答案就是6.
ZJOI2012 小蓝的好友 - hzaskywalker - Yavin(某沙茶的代码库)
 
 
请将上面这图脑补成笛卡尔树吧(我好不容易画的图忘了保存!!!好气愤,于是找了张别的图代替)
差不多就是这样。如果我们对于高度建立权值小的在上的笛卡尔树,那么考虑这个东西有什么意义。对于点i,它的高度为3,它左儿子的高度为5,右儿子的高度为7,那么说明了什么问题呢?其左儿子对应的高度为4,5的矩形的右边界是在i以左的。也就是说(5-3)*在左儿子这棵子树中选择任意两个点作为边界的方案数,就是左儿子对应的矩形的方案数。
也可以这么想,我们从底部将整个图贪心划分,每次选择没有被染色的最低的一个点,往左和往右延伸,然后染色,而延伸的区间的边界就是笛卡尔树的最近的两个祖先。
我们发现数据是随机的,而笛卡尔树在随机情况下是logn的(其实就是treap而已),操作就是将某个点的高度修改为0,或将所有区间的高度+1,顺手统计答案。这个问题是很简单很简单的,用平衡树轻松维护。
于是问题就解决了。
代码如下:

#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;

const int MAX=120000+10;
const int NUM=4;

int ran()
{
static int seed=222313214;
seed+=(seed<<2)+1;
return seed;
}

struct node
{
node *lc,*rc;
int size;//记录子树大小
int add;
int height;
LL ans;

node(){}
friend void downit(node* ,int rev,int add);

void down()
{
if(add)
{
if(lc)lc->doAdd(add);
if(rc)rc->doAdd(add);
add=0;
}
}

void update()
{
size=1;
ans=0;
down();
if(lc)
{
size+=lc->size;
ans+=(LL)lc->size*(lc->size+1)/2*(lc->height-height);
ans+=lc->ans;
}
if(rc)
{
size+=rc->size;
ans+=(LL)rc->size*(rc->size+1)/2*(rc->height-height);
ans+=rc->ans;
}
}

void doAdd(int p)
{
add+=p;
height+=p;
}
}tree[MAX*NUM];
int cnt;

node* mynew()
{
return tree+(cnt++);
}

node* newnode(int _height,node* _lc,node* _rc)
{
node* p=mynew();
p->height=_height;
p->lc=_lc;
p->rc=_rc;
p->size=1;
p->ans=0;
p->add=0;
return p;
}

node* merge(node* a,node* b)
{
if(!b)return a;
if(!a)return b;
a->down();
b->down();
if( a->height < b->height )
{
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_l(node* a,int left)
{
if(!a)
return mp((node*)0,(node*)0);
a->down();
int size_l=(a->lc?a->lc->size:0)+1;
pair<node* ,node* > tmp;
if(size_l<=left)
{
tmp=spilt_l(a->rc,left-size_l);
a->rc=tmp.x;
a->update();
return mp(a,tmp.y);
}
else
{
tmp=spilt_l(a->lc,left);
a->lc=tmp.y;
a->update();
return mp(tmp.x,a);
}
}

node* insert(node* a,int left,node* p)
{
if(!a)return p;
a->down();
int size_l=(a->lc?a->lc->size:0)+1;
if(p->height<a->height)
{
if(size_l<=left)
{
a->rc=insert(a->rc,left-size_l,p);
a->update();
}
else
{
a->lc=insert(a->lc,left,p);
a->update();
}
return a;
}
else
{
pair<node* ,node* > tmp=spilt_l(a,left);
p->lc=tmp.x;
p->rc=tmp.y;
p->update();
return p;
}
}

node* root;

int r,c,n;
pair<int,int> cut[MAX];

LL getAns()
{
root->down();
return root->ans+(LL)root->height*c*(c+1)/2;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#endif
int i;
scanf("%d%d",&r,&c);
scanf("%d",&n);
REP(i,1,n)
scanf("%d%d",&cut[i].x,&cut[i].y);
sort(cut+1,cut+n+1);
REP(i,1,c)
root=insert(root,i-1,newnode( 0,0,0) );
LL ans=(LL)r*(r+1)/2*c*(c+1)/2;
int t=1;
REP(i,1,r)
{
root->doAdd(1);
while(t<=n && cut[t].x==i)
{
pair<node*,node*> tmp=spilt_l(root,cut[t].y-1);
root=merge ( merge(tmp.x,newnode(0,0,0)) ,spilt_l(tmp.y,1).y);
++t;
}
ans-=getAns();
}
cout<<ans<<endl;
return 0;
}



  评论这张
 
阅读(647)| 评论(8)
推荐 转载

历史上的今天

评论

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

页脚

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