【bzoj1227】[SDOI2009]虔诚的墓主人

2015.02.03 16:40 Tue | 4次阅读 | 旧日oi | 固定链接 | 源码

Description

小W 是一片新造公墓的管理人。公墓可以看成一块N×M 的矩形,矩形的每个格点,要 么种着一棵常青树,要么是一块还没有归属的墓地。 当地的居民都是非常虔诚的基督徒,他们愿意提前为自己找一块合适墓地。为了体现自 己对主的真诚,他们希望自己的墓地拥有着较高的虔诚度。 一块墓地的虔诚度是指以这块墓地为中心的十字架的数目。一个十字架可以看成中间是 墓地,墓地的正上、正下、正左、正右都有恰好k 棵常青树。 小W 希望知道他所管理的这片公墓中所有墓地的虔诚度总和是多少

Input

第一行包含两个用空格分隔的正整数N 和M,表示公墓的宽和 长,因此这个矩形公墓共有(N+1) ×(M+1)个格点,左下角的坐标为(0, 0),右上角的坐标为(N, M)。 第二行包含一个正整数W,表示公墓中常青树的个数。 第三行起共W 行,每行包含两个用空格分隔的非负整数xi和yi,表示一棵常青树的坐 标。输入保证没有两棵常青树拥有相同的坐标。 最后一行包含一个正整数k,意义如题目所示。

Output

包含一个非负整数,表示这片公墓中所有墓地的虔诚度总和。 为了方便起见,答案对2,147,483,648 取模。

Sample Input

5 6 13 0 2 0 3 1 2 1 3 2 0 2 1 2 4 2 5 2 6 3 2 3 3 4 3 5 2 2

Sample Output

6

HINT

图中,以墓地(2, 2)和(2, 3)为中心的十字架各有3个,即它们的虔诚度均为3。其他墓
地的虔诚度为0。
对于30%的数据,满足1 ≤ N, M ≤ 1,000。
对于60%的数据,满足1 ≤ N, M ≤ 1,000,000。
对于100%的数据,满足1 ≤ N, M ≤ 1,000,000,000,0 ≤ xi ≤ N,0 ≤ yi ≤ M,1 ≤ W ≤ 100,000,
1 ≤ k ≤ 10。
存在50%的数据,满足1 ≤ k ≤ 2。
存在25%的数据,满足1 ≤ W ≤ 10000。

题解

首先这么大的数据范围一定要离散化一下,这题还是二维离散,但实际上是一维的,不太好写
之后如果用朴素算法O(N*M)会t,所以考虑优化
先预处理出组合数
对于每一列,我们可以在O(1)时间内求出当前的南北方向符合题意的方案数,对于连续的一些列,我们可以用树状数组维护总的方案数,而左右的方案数可以在循环中直接求出,每扫完一行更新这行出现的点对应的列的方案数,再加到树状数组上就行了时间复杂度是wlgw级的,可过。

我的程序

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#define maxn 100005
#define mod 2147483648ll
#define ll long long
using namespace std;
int n,m,w,k,t;
ll ans;
int numx[maxn],cntx,cnty;
vector<int> num[maxn];
int line[maxn];
ll c[maxn][12];
struct node{
    int x,y,idx;
}a[maxn];
struct BIT{
    ll c[maxn];
    int lowbit(int x){return x&(-x);}
    void add(int x,ll num)
    {
        for(;x<=w;x+=lowbit(x)) c[x]+=num;
    }
    ll query(int x,int y)
    {
        ll ret=0;
        for(;y;y-=lowbit(y)) ret+=c[y];
        for(;x;x-=lowbit(x)) ret-=c[x];
        return (ret+mod)%mod;
    }
}bit;
bool cmp1(const node &a,const node &b)
{
    return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
bool cmp2(const node &a,const node &b)
{
    return a.y<b.y||(a.y==b.y&&a.x<b.x);
}
void add(int x)
{
    ll tmp=c[line[x]][k]*c[numx[x]-line[x]][k]%mod;//之前的值 
    ll temp=c[++line[x]][k]*c[numx[x]-line[x]][k]%mod;//现在的值 
    bit.add(x,(temp-tmp+mod)%mod);//更新差值,注意负数取mod 
}
void Init()
{
    for(int i=0;i<=w;i++) c[i][0]=1;
    for(int i=1;i<=w;i++)
    for(int j=1;j<=min(i,k);j++)
    c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
}
int main()
{
    cin>>n>>m>>w;
    for(int i=1;i<=w;i++) scanf("%d%d",&a[i].x,&a[i].y);
    cin>>k;Init();
    a[0].x=a[0].y=-1;//预处理出来,使离散化后的点从1开始标号,防止树状数组死循环 
    sort(a+1,a+w+1,cmp1);//按照x为第一关键字排序 
    while((++t)<=w)
    {
        if(a[t].x==a[t-1].x) numx[cntx]++;
        else numx[++cntx]=1;
        a[t].idx=cntx;
    }//每列上点的个数 ,id[x]:离散化  
    sort(a+1,a+w+1,cmp2);t=0;//按照y为第一关键字排序 
    while((++t)<=w)
    {
        if(a[t].y==a[t-1].y) num[cnty].push_back(a[t].idx);
        else num[++cnty].push_back(a[t].idx);
    }//每行上点的个数以及位置 
    int temp,t1,t2;
    for(int i=1;i<=cnty;i++)
    {
        temp=t1=t2=0;
        for(int j=1;j<num[i].size();j++)
        {
            t1=num[i][j-1],t2=num[i][j];//两个相邻的点
            ans=(ans+bit.query(t1,t2-1)*c[++temp][k]%mod*c[num[i].size()-temp][k])%mod;
            //(t1+1列到t2-1列之间每一列方案数的总和*左面的组合数*右面的组合数 
        }
        for(int j=0;j<num[i].size();j++) add(num[i][j]);//更新树状数组 
    }
    cout<<ans;
}```