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

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

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

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

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

二四象限同理。

#include<bits/stdc++.h>
#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].x<a[y].x;
}
int q1[N],q2[N],q3[N],q4[N],top[5];
int solve(int x)
{
memset(top,0,sizeof(top));
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(!top[1]||a[t].y<a[q1[top[1]]].y)q1[++top[1]]=t; if(op==2)
{
while(top[2]&&a[t].y<a[q2[top[2]]].y)top[2]--;
q2[++top[2]]=t;
} if(op==3)
{
while(top[3]&&a[t].y>a[q3[top[3]]].y)top[3]--;
q3[++top[3]]=t;
} if(op==4)if(!top[4]||a[t].y>a[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<=top[1];i++)
{
while(p1>=1&&a[q2[p1]].y>a[q1[i]].y)p1--; while(p2+1<=top[4]&&a[q4[p2+1]].x<a[q1[i]].x)p2++; while(p3-1>=1&&(!p1||a[q3[p3-1]].x>a[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<=top[2];i++)
{
while(p1-1>=1&&a[q1[p1-1]].y<a[q2[i]].y)p1--; while(p2<=top[3]&&a[q3[p2]].x<a[q2[i]].x)p2++; while(p3-1>=1&&(p2==top[3]+1||a[q4[p3-1]].y>a[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<=n;i++)scanf("%d%d",&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+=solve(i);
if(i&1)ans1+=now;
else ans2+=now;
}
printf("%lld %lld\n",ans1,ans2);
return 0;
}

  

最新文章

  1. Yii2 使用a标签发送post请求
  2. hdu 1124 Factorial(数论)
  3. C/C++运算符优先级
  4. Hibernate、Mybatis 通过数据库表反向生成java类和配置
  5. ContentProvider深度探索
  6. bzoj 2482: [Spoj GSS2] Can you answer these queries II 线段树
  7. SQL Server2005使用CTE实现递归
  8. Convert Binary Search Tree (BST) to Sorted Doubly-Linked List
  9. java实现随机验证码的图片
  10. UIImagePickerController本地化控件文字
  11. spring集成redis
  12. 【Android 应用开发】分析各种Android设备屏幕分辨率与适配 - 使用大量真实安卓设备采集真实数据统计
  13. js将某个值转换为String字符串类型或转换为Number数字类型
  14. 基于C#&amp;.net2.0的windows服务创建与安装
  15. 从零开始搭建vue开发环境及构建vue项目
  16. Javadoc转换chm帮助文档的四种方法总结
  17. Java SE 之 DAO层接口设计思想
  18. 表单数据转换成json格式数据
  19. LeetCode 7. Reverse Integer 一个整数倒叙输出
  20. Android 进价5_自定义广播 通过广播更新ListView的适配器 下载管理

热门文章

  1. 20155339 Exp5 MSF基础应用
  2. 20155339平措卓玛 Exp2 后门原理与实践
  3. HTML5 本地存储实现购物车功能
  4. Luogu P1196 [NOI2002]银河英雄传说
  5. 06-Git-Linux命令
  6. Kubernetes学习之路(二十一)之网络模型和网络策略
  7. Unix domain socket 简介
  8. 全局最小割StoerWagner算法详解
  9. nginx安装(转发)
  10. ns3的输入输出奥秘(三) Tracing系统