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

点击量：264

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

目录

题目描述

平面上有\(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;
}