首页 > 代码库 > bzoj 1824: [JSOI2010]下棋问题
bzoj 1824: [JSOI2010]下棋问题
考虑每次新放一个棋子会产生多少新的矩形，以及减掉多少旧的矩形。
用第$i$个点的坐标把坐标轴分成4个象限。
显然第一问的答案用四个单调栈就能解决。
而且第二问每个矩形的两个端点一定在1,3或2,4象限的单调栈里。
枚举第一象限里的一个点，剩下三个象限里维护3个指针，就能找出来第3象限里能和当前点组成矩形的点。
二四象限同理。
#include<bits/stdc++.h>#define N 5005#define ll long longusing 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;}
bzoj 1824: [JSOI2010]下棋问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。