bzoj 1824: [JSOI2010]下棋问题

2021-07-02 06:05

阅读：494

标签：坐标轴 node 枚举端点 bool sort printf 产生 define

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

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

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

而且第二问每个矩形的两个端点一定在1,3或2,4象限的单调栈里。

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

二四象限同理。

#include
#define N 5005
#define ll long long
using namespace std;
int n;
struct node
{
    int x,y;
}a[N];
ll ans1,ans2,now;
int p[N];
bool cmp(int x,int y)
{
    return a[x].xa[q4[top[4]]].y)q4[++top[4]]=t;
        }
    }
    int ans=top[1]+top[2]+top[3]+top[4];
    int p1=top[2],p2=0,p3=top[3]+1,p4=top[3];
    for(int i=1;i=1&&a[q2[p1]].y>a[q1[i]].y)p1--;
         
        while(p2+1a[q2[p1]].x))p3--;
         
        while(p4>=1&&(p2!=0&&a[q4[p2]].y>a[q3[p4]].y))p4--;
         
        if(p4>=p3)ans-=p4-p3+1;
    }
     
    p1=top[1]+1,p2=0,p3=top[4]+1,p4=top[4];
    for(int i=1;i=1&&a[q1[p1-1]].ya[q3[p2]].y))p3--;
         
        while(p4>=1&&(p1!=top[1]+1&&a[q4[p4]].x>a[q1[p1]].x))p4--;
         
        if(p4>=p3)ans-=p4-p3+1;
    }
     
    return ans;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i

bzoj 1824: [JSOI2010]下棋问题

标签：坐标轴 node 枚举端点 bool sort printf 产生 define

原文地址：http://www.cnblogs.com/ezyzy/p/7128566.html

上一篇：夺命雷公狗---linux NO:43 linux下编译apache整合php

下一篇：MVC 【Razor 视图引擎】案例分析

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：bzoj 1824: [JSOI2010]下棋问题
文章链接：http://soscw.com/index.php/essay/100661.html

亲，登录后才可以留言！

bzoj 1824: [JSOI2010]下棋问题

评论

热门文章

推荐文章

最新文章

置顶文章