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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ2727][HNOI2012]双十字  

2015-04-02 17:29:14|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2727: [HNOI2012]双十字

傻逼写了好久
顺便提一下有组数据有误……R*C大概是1.1e6左右
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 1E4+100;
const int M = 2E6+100;
const int TN = 2E4+100;
const int MOD = 1E9+9;
int scan(){
char cc=' ';int re=0,fh=1;while(cc==' '||cc=='\r'||cc=='\n')cc=getchar(),fh=1;
if(cc=='+')cc=getchar(),fh=1;if(cc=='-')cc=getchar(),fh=-1;
while('0'<=cc&&cc<='9'){re=re*10+cc-'0';cc=getchar();}return re*fh;
}
int ROOT,T,n,m,up[M],left[M],right[M],down[M],sum[M];
short col[M];
int lson[TN],rson[TN],add[TN],set[TN],tree[TN][2],tr;
short vset[TN];
int Build(int l=1,int r=tr){
int ro=++T;
if(l<r){
int mid = (l+r)/2;
lson[ro] = Build(l,mid);
rson[ro] = Build(mid+1,r);
}
return ro;
}
void make(int val,short t,int ro,int l,int r){
if(t){//set
add[ro] = 0;
set[ro] = val;
vset[ro]= 1;
tree[ro][0] = (ll)val*(r-l+1)%MOD;
tree[ro][1] = (ll)val*(sum[r]-sum[l-1])%MOD;
}else{//add
if(vset[ro])set[ro]=(set[ro]+val)%MOD;
else add[ro] = (add[ro]+val)%MOD;
tree[ro][0] = (tree[ro][0]+(ll)val*(r-l+1))%MOD;
tree[ro][1] = (tree[ro][1]+(ll)val*(sum[r]-sum[l-1]))%MOD;
}
}
void push(int ro,int l,int r){
if(l==r)return;
if(add[ro]){
int mid = (l+r)/2;
make(add[ro],0,lson[ro],l,mid);
make(add[ro],0,rson[ro],mid+1,r);
add[ro]=0;
}
if(vset[ro]){
int mid = (l+r)/2;
make(set[ro],1,lson[ro],l,mid);
make(set[ro],1,rson[ro],mid+1,r);
vset[ro]=0;
set[ro]=0;
}
}
void Add(int la,int ra,int val,int t,int ro=ROOT,int l=1,int r=tr){
push(ro,l,r);
if(la<=l&&r<=ra){make(val,t,ro,l,r);return;}
int mid = (l+r)/2;
if(la<=mid)Add(la,ra,val,t,lson[ro],l,mid);
if(mid+1<=ra)Add(la,ra,val,t,rson[ro],mid+1,r);

tree[ro][0] = (tree[lson[ro]][0] + tree[rson[ro]][0])%MOD;
tree[ro][1] = (tree[lson[ro]][1] + tree[rson[ro]][1])%MOD;
}
void get(int la,int ra,int re[],int ro=ROOT,int l=1,int r=tr){
push(ro,l,r);
if(la<=l&&r<=ra){
re[0] = (re[0]+tree[ro][0])%MOD;
re[1] = (re[1]+tree[ro][1])%MOD;
return;
}
int mid = (l+r)/2;
if(la<=mid)get(la,ra,re,lson[ro],l,mid);
if(mid+1<=ra)get(la,ra,re,rson[ro],mid+1,r);
}
int calc(int x,int y){if(x<=0 || x>n)return 0;return (x-1) * m + y;}
int main(){
// freopen("in.txt","r",stdin);
int i,j,a,b;
n = scan();m = scan();
tr = m / 2;
ROOT = Build(1,tr);
for(i=1;i*2<=m;i++)sum[i] = (sum[i-1]+i)%MOD;
int pn = scan();
for(i=1;i<=pn;i++){
a = scan();b = scan();
col[calc(a,b)] = 1;
}
up[0]=left[0]=right[0]=down[0]=-1;
for(i=1;i<=n;i++){
int t;
t = calc(i,1);
for(j=1;j<=m;j++,t++){
//printf("%d %d\n",i,j);
printf("%d %d\n",t,calc(i-1,j));
if(col[t]) right[t]=left[t]=up[t]=-1;
else up[t] = up[calc(i-1,j)]+1;
}

t = calc(i,m-1);
for(j=m-1;j>=1;j--,t--)
if(!col[t])
right[t] = right[t+1]+1;

t = calc(i,2);
for(j=2;j<=m;j++,t++)
if(!col[t])
left[t] = left[t-1]+1;
}
for(i=n;i;i--)
for(j=1;j<=m;j++)
if(!col[(a=calc(i,j))])
down[a] = down[calc(i+1,j)]+1;
else down[a]=-1;
int ans=0,tmp[2];
for(j=1;j<=m;j++)
{
//j=4;
Add(1,tr,0,1);
int t;
for(i=1;i<=n;i++)
if(!col[t=calc(i,j)]){
//get ans
if((a=min(left[t],right[t])-1)>0 && down[t] > 0){
tmp[0]=tmp[1]=0;
get(1, a, tmp);
/*
if(tmp[0]||tmp[1]){
printf("(%d, %d) %d %d\n", i,j,tmp[0],tmp[1]);
}*/
tmp[0] = ((ll)tmp[0]*(a+1)-tmp[1])%MOD;
/*
if(down[t]*tmp[0] !=0){
printf("(%d, %d) %d\n", i,j,down[t]*tmp[0]);
}*/
ans = (ans + (ll)down[t]*tmp[0]) % MOD;
}
a = calc(i-1,j);
//update
if(i!=1 && i!=n && min(left[a],right[a])>=1 && up[a]>0){
Add(1,min(left[a],right[a]),up[a],0);
}
}else{
Add(1,tr,0,1);
}
}
if(ans < 0) ans += MOD;
printf("%d\n",ans);
return 0;
}

题解:
线段树
因为是双十字,所以我们维护上面的十字,枚举下面的十字就好了
先处理出down,left,right,up四个数组
然后对于枚举的下面的十字中心i答案是 for所有可能的水平宽j  down[i]*满足中心距离i大于1并且左右两边的宽度小于j的十字个数。
对于每一列维护一个线段树,维护的是距离当前枚举位置>1的,左右水平宽为i,的十字个数。
然后对于每个枚举点就相当与查询前缀和的前缀和……修改是区间add和区间set(因为要清零)
我一开始比较傻逼……以为会MLE,后来发现对每一列分开做就行了
  评论这张
 
阅读(263)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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