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

ydc的博客

 
 
 

日志

 
 

bzoj 2727 (hnoi2012) 双十字  

2013-02-08 16:38:01|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

我没注意到512MB的内存下,10000*10000的数组是无压力的啊……

于是我就缩成1000000的数组了

怎么缩呢?很简单,用个一维数组存,那么一维数组的某元素与二维数组的某元素的位置对应关系很容易出来的。

以上是实现技巧,下面进入正题


下左右三个方向都用数组存一下,L,R,Down分别表示向左右下最多扩展多少且本身不算。比如010中那个1的L,R值等于0。01110中中间那个1的L,R才等于1

然后C[i]=min(L[i],R[i]),当然i是一维数组下的,也就是对应二维数组的一个东西

我们枚举第二条横线上的点i,寻找他上方的使这条竖线是1的j(也就是i-j小于等于i的最大往上扩展值,这个最上扩展值可以像另外三个方向再开个数组记一下,也可以用个变量记就够了),然后已知C[i],C[j],能构成多少个呢?用等差数列随便推一下可得:

if(C[i]>=C[j])  (C[i]*C[j]-C[j]*(C[j]+1)/2)*(j-top)
if(C[i]<C[j])  C[i]*(C[i]-1)/2*(j-top)

top就是向上的最多扩展值

看上去好像是对的吧?其实这样做是0分

为什么呢?因为还要乘以Down[i]啊!

我去年这题就是这样爆零的!!!

这样做了之后就90分了啊啊啊!!

 

好吧剩下来十分怎么搞呢?

拆开之后,如果不管C[i],我们得到这样的三个量

a1=C[j]*(j-top) a2=C[j]*(C[j]+1)/2*(j-top) a3=j-top

如果我们可以把a1,a2,a3记下来每次能在O(logn)以下的时间查询的话就木有问题了

这三个量是跟C[i]值有关的

那么我们开三个树状数组,a1[i]表示C[j]小于等于i的C[j]*(j-top)的sigma一下,a2[i]表示C[j]小于等于i的C[j]*(C[j]+1)/2*(j-top)的sigma以下,a3[i]表示C[j]小于等于i的j-top的sigma一下

当然a3要补集转化一下啦

所以枚举到i时答案就是C[i]*a1[C[i]]-a2[C[i]]+C[i]*(C[i-1])/2*(a3[m]-a3[C[i]])。

千万别忘了乘以Down[i]啊啊啊否则会爆零啊

然后由于两行不能相邻所以得在下面一行算完才插进去

所以你遇到不可走的点来清空树状数组时就有点麻烦了因为最后一个你不清楚插没插。

不过虽然麻烦还是容易解决的用个bool变量记一下就可以了

可是我人懒,我做了罪恶的事情……

 

我for(int i=0;i<=m;i++)的把树状数组清空了!!

然后就过了……

如果用上面说的来做的话,时间复杂度:O(rclogr),因为一个点最多被删一次。

1s内通过无压力

如果用我的方法……时间复杂度不清楚

10s内通过压力不大

/*
if(C[i]>=C[j])  (C[i]*C[j]-C[j]*(C[j]+1)/2)*(j-top)*Down[i]
if(C[i]<C[j])  C[i]*(C[i]-1)/2*(j-top)*Down[i]
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MOD 1000000009
#define MAXN 2000010
#define lowbit(p) (p&(-p))
using namespace std;
typedef long long LL;
LL total1[MAXN],total2[MAXN],total3[MAXN],C[MAXN],ans;
int queue[MAXN],n,m;
bool mark[MAXN];
LL Down[MAXN];
int ID(int a,int b){  return (a-1)*m+b;  }
void read()
{
    int tot;
    scanf("%d %d %d",&n,&m,&tot);
    for(int i=1,a,b;i<=tot;i++)
    {
        scanf("%d %d",&a,&b);
        mark[ID(a,b)]=true;
    }
}
void ptm()
{
    static int L[MAXN],R[MAXN];  
    for(int i=1;i<=n;i++)
    {
        L[ID(i,1)]=mark[ID(i,1)]?-1:0;
        R[ID(i,m)]=mark[ID(i,m)]?-1:0;      
        for(int j=2;j<=m;j++)
        {
            if(mark[ID(i,j)])  L[ID(i,j)]=-1;
            else L[ID(i,j)]=L[ID(i,j-1)]+1;
        }
        for(int j=m-1;j>=1;j--)
        {
            if(mark[ID(i,j)])  R[ID(i,j)]=-1;
            else R[ID(i,j)]=R[ID(i,j+1)]+1;
            C[ID(i,j)]=min(L[ID(i,j)],R[ID(i,j)]);
        }
    }
    for(int j=1;j<=m;j++)
    {
        Down[ID(n,j)]=mark[ID(n,j)]?-1:0;
        for(int i=n-1;i>=1;i--)
        {
            if(mark[ID(i,j)])  Down[ID(i,j)]=-1;
            else Down[ID(i,j)]=Down[ID(i+1,j)]+1;
        }
    }
}
void Insert(LL sum[],int p,LL k)
{
    for(int i=p;i<=m;i+=lowbit(i))
        sum[i]=(sum[i]+k)%MOD;
}
LL Get(LL sum[],int p)
{
    LL ans=0;
    for(int i=p;i;i-=lowbit(i))
        ans=(ans+sum[i])%MOD;
    return ans;
}
void Clear(int &top,int &rear)
{
    top=rear=0;
    for(int i=1;i<=m;i++)
        total1[i]=total2[i]=total3[i]=0; 
}
void work()
{
    int rear=0,top=0;
    LL last;
    for(int j=1;j<=m;j++)
    {
        Clear(top,rear);
        for(int i=1;i<=n;i++)
        {
            int p=ID(i,j);
            if(mark[p])  Clear(top,rear);
            else if(top==0)  top=i;
            else if(C[p]!=0)
            {
                LL sum1=Get(total1,C[p])*C[p]%MOD;
                LL sum2=Get(total2,C[p]);
                LL sum3=C[p]*(C[p]-1)/2%MOD*(Get(total3,m)-Get(total3,C[p]))%MOD;
                last=(sum1-sum2+sum3+MOD)%MOD,ans=(ans+last*Down[p])%MOD;
                if(queue[rear]==ID(i-1,j))
                {
                    int p=queue[rear],h=(p-1)/m+1;
                    Insert(total1,C[p],C[p]*(h-top)%MOD);
                    Insert(total2,C[p],C[p]*(C[p]+1)/2%MOD*(h-top)%MOD);
                    Insert(total3,C[p],h-top);
                }
                queue[++rear]=p;
                continue;
            }
            if(rear&&queue[rear]==ID(i-1,j))
            {
                int p=queue[rear],h=(p-1)/m+1;
                Insert(total1,C[p],C[p]*(h-top)%MOD);
                Insert(total2,C[p],C[p]*(C[p]+1)/2%MOD*(h-top)%MOD);
                Insert(total3,C[p],h-top);
            }
        }
    }
}
int main()
{
    read();
    ptm();
    work();
    printf("%lld\n",ans);
    return 0;
}


 

  评论这张
 
阅读(575)| 评论(2)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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