1 条题解

  • 0
    @ 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
    上传者