1 条题解
-
0大金狮 (mengqingyu) LV 10 @ 2024-9-27 18:19:29
#include<bits/stdc++.h> #define ls v<<1 #define rs v<<1|1 using namespace std; const int M=1e5+5; struct Point{int x,y,val;}pt[M]; struct node{int le,ri,sum;}tree[M<<2]; bool cmpy(Point a,Point b){return a.y==b.y?a.x<b.x:a.y<b.y;} bool cmpx(Point a,Point b){return a.x==b.x?a.y<b.y:a.x<b.x;} int n,ans,x[M],tot; void up(int v){tree[v].sum=tree[ls].sum+tree[rs].sum;} void build(int v,int le,int ri) { tree[v].le=x[le],tree[v].ri=x[ri]; if(le==ri)return; int mid=le+ri>>1; build(ls,le,mid),build(rs,mid+1,ri); } void add(int v,int x,int val) { if(val>1)return; if(tree[v].le==tree[v].ri){tree[v].sum+=val;return;} if(x<=tree[ls].ri)add(ls,x,val); else add(rs,x,val); up(v); } int ask(int v,int le,int ri) { if(le<=tree[v].le&&tree[v].ri<=ri)return tree[v].sum; int r=0; if(le<=tree[ls].ri)r=ask(ls,le,ri); if(tree[rs].le<=ri)r+=ask(rs,le,ri); return r; } void in() { scanf("%d",&n); for(int i=1;i<=n;++i)scanf("%d%d",&pt[i].x,&pt[i].y),x[i]=pt[i].x; } void ac() { sort(pt+1,pt+1+n,cmpx); for(int i=1;i<=n;++i) { x[i]=pt[i].x; if(pt[i].x!=pt[i-1].x&&pt[i].x!=pt[i+1].x){pt[i].val=2;continue;} if(pt[i].x!=pt[i-1].x)pt[i].val=1; else if(pt[i].x!=pt[i+1].x)pt[i].val=-1; } tot=unique(x+1,x+1+n)-x-1; build(1,1,tot); sort(pt+1,pt+1+n,cmpy); for(int i=1,j=1,le,ri;i<=n;++i) { for(j=i,le=INT_MAX,ri=-INT_MAX;pt[i].y==pt[i+1].y;++i)add(1,pt[i].x,pt[i].val),le=min(le,pt[i].x),ri=max(ri,pt[i].x); add(1,pt[i].x,pt[i].val),le=min(le,pt[i].x),ri=max(ri,pt[i].x); for(j+=1;j<i;++j)ans-=(!pt[j].val||pt[j].val==1); if(le!=ri)ans+=ask(1,le+1,ri-1); } printf("%d\n",ans+n); } int main() { in(),ac(); //system("pause"); }
- 1
信息
- ID
- 173
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 10
- 标签
- 递交数
- 6
- 已通过
- 3
- 上传者