自动搬运

查看原文

来自洛谷，原作者为

	Sky__Dream 自从遇见你，凛冬散尽，星河长明⎛⎝≥⏝⏝≤⎛⎝||主页暂时搬迁：https://www.luogu.com.cn/paste/80hamthc

搬运于2025-08-24 22:15:41，当前版本为作者最后更新于2024-02-19 09:57:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

第一次发一道题的第一篇题解，好激动！

题目传送门

解题思路

考虑每次新放一个棋子会产生多少新的矩形，以及减掉多少旧的矩形。

用第 $i$ 个点的坐标把坐标轴分成 $4$ 个象限。

第一问的答案用四个单调栈就能解决。

第二问每个矩形的两个端点一定在一、三或二、四象限的单调栈里。

枚举第一象限里的一个点，剩下三个象限里维护 $3$ 个指针，就能找出来第三象限里能和当前点组成矩形的点。

二四象限同理。

AC Code：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5010; 
int n;
struct data
{
    int x,y;
}a[N];
ll ans1,ans2,now;
bool cmp(int x,int y)
{
    return a[x].x<a[y].x;
}
int p[N],s1[N],s2[N],s3[N],s4[N],sum[5];
int dfs(int x)
{
    memset(sum,0,sizeof(sum));
    for(int i=1;i<=n;i++)
    {
        if(p[i]<x)
        {
            int op=1;
            int t=p[i];
            if(a[t].x<a[x].x&&a[t].y>a[x].y)op=2;
            if(a[t].x<a[x].x&&a[t].y<a[x].y)op=3;
            if(a[t].x>a[x].x&&a[t].y<a[x].y)op=4;
            if(op==1) if(!sum[1]||a[t].y<a[s1[sum[1]]].y) s1[++sum[1]]=t;
            if(op==2)
            {
                while(sum[2]&&a[t].y<a[s2[sum[2]]].y) sum[2]--;
                s2[++sum[2]]=t;
            }
            if(op==3)
            {
                while(sum[3]&&a[t].y>a[s3[sum[3]]].y) sum[3]--;
                s3[++sum[3]]=t;
            }
            if(op==4) if(!sum[4]||a[t].y>a[s4[sum[4]]].y) s4[++sum[4]]=t;
        }
    }
    int ans=sum[1]+sum[2]+sum[3]+sum[4];
    int p1=sum[2],p2=0,p3=sum[3]+1,p4=sum[3];
    for(int i=1;i<=sum[1];i++)
    {
        while(p1>=1&&a[s2[p1]].y>a[s1[i]].y) p1--;
        while(p2+1<=sum[4]&&a[s4[p2+1]].x<a[s1[i]].x) p2++;
        while(p3-1>=1&&(!p1||a[s3[p3-1]].x>a[s2[p1]].x)) p3--;
        while(p4>=1&&(p2!=0&&a[s4[p2]].y>a[s3[p4]].y)) p4--;
        if(p4>=p3) ans-=p4-p3+1;
    }
    p1=sum[1]+1,p2=0,p3=sum[4]+1,p4=sum[4];
    for(int i=1;i<=sum[2];i++)
    {
        while(p1-1>=1&&a[s1[p1-1]].y<a[s2[i]].y) p1--;
        while(p2<=sum[3]&&a[s3[p2]].x<a[s2[i]].x) p2++;
        while(p3-1>=1&&(p2==sum[3]+1||a[s4[p3-1]].y>a[s3[p2]].y)) p3--;
        while(p4>=1&&(p1!=sum[1]+1&&a[s4[p4]].x>a[s1[p1]].x)) p4--;
        if(p4>=p3) ans-=p4-p3+1;
    }
    return ans;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
    for(int i=1;i<=n;i++) p[i]=i;
    sort(p+1,p+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        now+=dfs(i);
        if(i&1) ans1+=now;
        else ans2+=now;
    }
    printf("%lld %lld\n",ans1,ans2);
    return 0;
}

参考自这里，我的博客使用更佳！