题解 辣鸡

· · 个人记录

Description

辣鸡ljh NOI之后就退役了 , 然后就滚去学文化课了 .
然而在上化学课的时候 , 数学和化学都不好的ljh却被一道简单题难住了 , 受到了大佬的嘲笑 .
题目描述是这样的 :
在一个二维平面上有一层水分子 , 请问形成了多少个氢键？
这个二维平面可以看做一个类似棋盘的东西 , 每个格子可以容纳一个水分子 , 左下角的格子为 (0,0) , 这个格子右边的格子为 (1,0) , 上方格子为 (0,1) , 以此类推 .
辣鸡ljh当然不会做了 , 所以他来求助JeremyGou , JeremyGou一眼就看穿了真相 , 并想用这道题来考一考正在做NOIP模拟赛的你 .
注 : 在本题中 , 我们认为一个水分子能与和它曼哈顿距离为 2 且直线距离小于 2 的其他格子形成氢键 .

输入格式

一个整数 n ,
接下来 n 行 , 每行给出四个整数 x1,y1,x2,y2 ,
表示以 (x1,y1) 为左下角 , (x2,y2) 为右上角的矩形中每个格子都有一个水分子 .
给出的所有矩形没有交集。

n\leq 10^5\quad x,y\leq10^9

Solution

矩阵内部的贡献可以 O(1) 计算 , 对于给定的两个矩阵也可以 O(1) 计算它们之间的贡献 , 问题枚举两个相邻矩阵的复杂度为 O(n^2) , 对矩阵排序 , 就可以用二分 O(log\ n) 找出与之相邻的矩阵 .
复杂度 O(nlog\ n) 大概

Code


#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
int read()
{
    int ret=0;char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')ret=(ret<<3)+(ret<<1)+(c^48),c=getchar();
    return ret;
}
const int maxn=1e5+5;
int n;
ll ans;
class water
{
    public:
    int x1,y1,x2,y2;
    bool operator <(water a)const{if(x1==a.x1)return y1<a.y1;return x1<a.x1;}
}w[maxn];
int count(int x,int y)
{
    if(w[x].y2==w[y].y1-1||w[x].y1==w[y].y2+1)
        return max(0,min(w[x].x2,w[y].x2+1)-max(w[x].x1,w[y].x1+1)+1)+max(0,min(w[x].x2,w[y].x2-1)-max(w[x].x1,w[y].x1-1)+1);
    if(w[x].x2==w[y].x1-1||w[x].x1==w[y].x2+1)
        return max(0,min(w[x].y2,w[y].y2+1)-max(w[x].y1,w[y].y1+1)+1)+max(0,min(w[x].y2,w[y].y2-1)-max(w[x].y1,w[y].y1-1)+1);
    return 0;
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        w[i].x1=read();w[i].y1=read();w[i].x2=read();w[i].y2=read();
        ans+=2ll*(w[i].x2-w[i].x1)*(w[i].y2-w[i].y1);
    }
    sort(w+1,w+n+1);
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;)
        {
            if(w[j].x1>w[i].x2+1)break;
            ans=ans+count(i,j);
            if(w[j].y1>w[i].y2)j=lower_bound(w+1,w+n+1,water{w[j].x1+1,-1})-w;
            else j++;
        }
    }
    printf("%lld",ans);
    return 0;
}