[2018.10雅礼] Rectangle 题解【树状数组】【枚举】【区间统计】

作者: wjyyy 分类: 前缀和,区间统计,枚举,树状数组,解题报告 发布时间: 2018-10-09 19:16

点击量:9

 

   非常有意思的枚举技巧,可是它还是好难啊= =

 

题目描述

平面上有\(n\)个点,第\(i\)个点的坐标\(X_i,Y_i\)。对于其中的一个非空点集\(S\),定义\(f(S)\)为一个最小矩形,满足:

  • 覆盖\(S\)中所有的点(在边界上也算覆盖);
  • 边与坐标轴平行。

 

求所有不同的\(f(S)\)的面积和对\(10^9+7\)取模的结果。

 

两个矩形被认为是不同的,当且仅当它们顶点坐标不同。

 

输入输出格式

输入格式:

第一行一个整数\(n\)。

 

接下来\(n\)行,每行两个整数\(X_i,Y_i\)。

 

输出格式:

一行一个整数表示答案

输入输出样例

输入样例#1:

4
1 2
3 1
4 4
5 1
输出样例#1:

45

说明

有\(8\)个面积大于\(0\)的不同矩形,以下是它们左下角和右上角的坐标:

 

\((1, 1) ,(3, 2) ; (1, 1) ,(4, 4) ; (1, 1) ,(5, 2); (1, 1) ,(5, 4)\)

\((1, 2) ,(4, 4) ; (3, 1) ,(4, 4) ; (3, 1) ,(5, 4); (4, 1) ,(5, 4)\)

 

对于所有数据,满足\(2≤n≤10^4,1≤X_i,Y_i≤2500\),没有重复的点。

  • \(\text{Subtask1}(13\%),n ≤ 18\).
  • \(\text{Subtask2}(9\%),n ≤ 50\).
  • \(\text{Subtask3}(25\%),n ≤ 300\).
  • \(\text{Subtask4}(21\%),n ≤ 2500,X_i \not= X_j,Y_i \not= Y_j\).
  • \(\text{Subtask5}(19\%),n ≤ 2500\).
  • \(\text{Subtask6}(13\%)\), 没有特殊的约束。

题解:

   这道题乍一看,题意感觉非常难懂。实际上所说的矩形就是在这些点中选择\(k\)个\((k\in [2,n])\)个点,能把它们包围的最小矩形。因此我们需要把这些矩形按某种方式,不重不漏地定下来。

 

   如果\(X_i\)互不相等,那么我们可以轻松地枚举矩形的左右边界。设左边界在\(x_i\),则确定左边界的点在\((x_i,y_i)\),那么\(x_i<x_j\),确定右边界的点在\((x_j,y_j)\)。为了延展到这两个边界,矩形必须包含这两个点。因此确定上下边界的点需要满足\(x\in[x_i,x_j],y\in(0,\min(y_i,y_j)]\bigcup [\max(y_i,y_j))\)。因为要计算面积,所以在枚举左右边界时,固定其中一个,然后把另一个往远处移,在这时一边在树状数组中加入答案,一边更新当前左右边界的答案。

 

   如果\(X_i\)有重复,那么确定边界的点就不能确定。此时我们仍然要枚举。假设我们枚举到两个点,形成上面的情况,那么答案统计仍然和这个一样,那么对于下面两种情况,它们所确定的矩形是有交集的。

 

   由右边第一个点和左边界限制(①+②)的矩形,一定全部包含在右边第二个点和左边界限制(仅②)的矩形中。那么我们在枚举上下界的时候,就要注意让两侧的限制点尽可能靠近,以避免重复计算

 

   同时,也是为了防止重复计算,在每次统计的时候只统计到下面一个区间的。什么意思呢?

   如果当前由右边第一个点和左边界限制(①区域),那么可以对答案做出贡献的点所在的集合是③,②∪④。如果当前由右边第二个点和左边界限制(②区域),那么可以对答案做出贡献的点所在的集合是③∪①,④。此时③和④就有了重合部分,为了避免容斥,我们第一次只让②做出贡献即可,毕竟③早晚要和④相遇,那么我们就把它留到最后,每次答案只统计当前限制区域以上和下面仅一个区间,还要保证上一段中提到的限制区域最小

 

   这样一来,让\([x_i,x_j]\)的部分用树状数组维护,剩下的边界暴力枚举就可以了。因为在树状数组中查询是\(O(log m)\),横坐标一共有\(m=2,500\)种,每个点在纵坐标上至多只会被枚举\(n\)次,那么时间复杂度为\(O(n(m+n)\log m)\)。(也许这题\(m\)给大一点\(n\)给小一点可以离散化??sxbk

 

   这道题细节还是挺多的,还要注意取模的时机,不小心就爆了long long 。。。不过在用不着long long的情况还是不要用,比如树状数组中;不怕被卡常的话就随便用了。

 

Code:

#include<cstdio>
#include<cstring>
#include<algorithm>
#define P 1000000007
long long dec(long long x,long long y)//带模减法
{
    x=((x-y)%P+P)%P;
    return x;
}
int c[2][2505];//树状数组
int lowbit(int x)
{
    return x&(-x);
}
void change(int t,int p,int x)
{
    while(p<=2500)
    {
        c[t][p]=(c[t][p]+x)%P;
        p+=lowbit(p);
    }
}
int ask(int t,int p)
{
    int ans=0;
    while(p)
    {
        ans+=c[t][p];
        p-=lowbit(p);
    }
    return ans;
}
int p[2505][2505];
int cnt[2505];
long long sum=0;
int main()
{
    int n;
    scanf("%d",&n);
    int u,v;
    for(int i=1;i<=n;++i)
    {
        scanf("%d%d",&u,&v);
        p[u][++cnt[u]]=v;
    }
    for(int i=1;i<=2500;++i)
        std::sort(p[i]+1,p[i]+1+cnt[i]);
    for(int r=1;r<=2500;++r)//枚举右边界
        if(cnt[r])
        {
            memset(c,0,sizeof(c));
            for(int i=1;i<=cnt[r];++i)
            {
                change(0,p[r][i],1);
                change(1,p[r][i],p[r][i]);
            }
            for(int l=r-1;l;--l)//调整左边界
                if(cnt[l])
                {
                    for(int i=1;i<=cnt[l];++i)
                        if(ask(0,p[l][i])-ask(0,p[l][i]-1)==0)
                        {
                            change(0,p[l][i],1);
                            change(1,p[l][i],p[l][i]);
                        }
                    int tl=cnt[l],tr=cnt[r];
                    while(tl&&tr)
                    {
                        if(p[l][tl]>p[r][tr])
                        {
                            while(p[l][tl-1]>p[r][tr])//调整到最近
                                --tl;
                            sum=(sum+(r-l)*dec(ask(1,2500),ask(1,p[l][tl]-1))%P*dec(ask(0,p[r][tr]),ask(0,p[l][tl-1])))%P;
                                    //上面的区域             这一段是以0为下边界的矩形             下面的区域
                            sum=dec(sum,(r-l)*dec(ask(1,p[r][tr]),ask(1,p[l][tl-1]))%P*dec(ask(0,2500),ask(0,p[l][tl]-1)));
                                    //下面的区域                   这一段是被挖掉的             上面的区域
                            --tl;
                        }
                        else
                        {
                            while(p[r][tr-1]>=p[l][tl])
                                --tr;
                            sum=(sum+(r-l)*dec(ask(1,2500),ask(1,p[r][tr]-1))%P*dec(ask(0,p[l][tl]),ask(0,p[r][tr-1])))%P;
                            sum=dec(sum,(r-l)*dec(ask(1,p[l][tl]),ask(1,p[r][tr-1]))%P*dec(ask(0,2500),ask(0,p[r][tr]-1)));
                            --tr;
                        }
                    }
                }
        }
    printf("%lld\n",sum);
    return 0;
}

说点什么

avatar
  Subscribe  
提醒
/* */