codeforces 1190D-Tokitsukaze and Strange Rectangle

灰太狼 2023-06-05 12:43 10阅读 0赞

传送门：[QAQQAQ][]

题意：给你在坐标轴上的N个点，问你用一条横线和两条竖线所划分出的不同点集的个数（不包括空集）

![1605368-20190805231602920-984257673.png][]

思路：在没想清楚的时候觉得这是一道水题：对于y轴排序，然后从下往上扫看上方x不同的个数s，ans+=(s+1)\*s/2即可，但后来发现这样会重复考虑一些集合，即在当前点时这几个点关于x轴排序是连续的，删掉这个点后仍是连续的，所以我们在对于y轴扫描时要减去这些重复的集合

即我们对于Y轴排序，从上至下扫描，对于当前新加入的一层y，先加上(s+1)\*s/2，再对于每一个x值寻找它们之间的空隙中原本存在了多少x，减去这些重复的集合tmp\*(tmp+1)/2即可

在代码实现方面，我们用线段树维护x值l,r区间内现存在多少点，每当一层扫完，把原先不存在的x值update成1，若x存在就不要管它，注意sum维护的是当前不同的x轴的个数，而不是总点数

在更新答案方面，对于同一层的两个x之间query一下原有不同x值个数，减一下tmp\*(tmp+1)/2即可，注意开头和结尾都要扫，而且线段树开到xn+1是为了防止越界

因为x,y<=1e9无法直接用线段树维护这么大一段区间，而n<=2e5，所以我们用常用技巧离散化一下即可

代码：（听说树状数组维护更方便，但我喜欢线段树啊……）

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const ll N=200005;
    const ll inf=2000000000;
     
    struct node{
        ll x,y;
        bool operator < (const node rhs) const{
            if(y==rhs.y) return x<rhs.x;
            return y>rhs.y;
        }
    }a[N];
     
    ll n,x[N],y[N],mx=-inf,vis[N];
     
    struct TREE{
        ll sum;
    }tree[N*4];
     
    void push_up(TREE &fa,TREE ls,TREE rs)
    {
        fa.sum=ls.sum+rs.sum;
    }
     
    void build(ll x,ll l,ll r)
    {
        if(l==r) 
        {
            tree[x].sum=0;
            return;
        }
        ll mid=(l+r)>>1;
        build(x+x,l,mid);
        build(x+x+1,mid+1,r);
        push_up(tree[x],tree[x+x],tree[x+x+1]);
    }
     
    void update(ll x,ll l,ll r,ll pos)
    {
        if(l==r)
        {
            tree[x].sum=1;
            return;
        }
        ll mid=(l+r)>>1;
        if(pos>mid) update(x+x+1,mid+1,r,pos);
        if(pos<=mid) update(x+x,l,mid,pos);
        push_up(tree[x],tree[x+x],tree[x+x+1]);
    }
     
    ll query(ll x,ll l,ll r,ll L,ll R)
    {
        if(L>R) return 0;
        if(L<=l&&r<=R) return tree[x].sum;
        ll mid=(l+r)>>1;
        if(mid>=R) return query(x+x,l,mid,L,R);
        if(mid<L) return query(x+x+1,mid+1,r,L,R);
        return query(x+x,l,mid,L,R)+query(x+x+1,mid+1,r,L,R);
    }
     
    int main()
    {
        scanf("%lld",&n);
        for(ll i=1;i<=n;i++) 
        {
            scanf("%lld%lld",&a[i].x,&a[i].y);
            x[i]=a[i].x; y[i]=a[i].y;
        }
        sort(x+1,x+n+1); sort(y+1,y+n+1);
        ll xn=unique(x+1,x+n+1)-x-1;
        ll yn=unique(y+1,y+n+1)-y-1;
        for(ll i=1;i<=n;i++)
        {
            a[i].x=lower_bound(x+1,x+xn+1,a[i].x)-x;
            a[i].y=lower_bound(y+1,y+yn+1,a[i].y)-y;
        }
        sort(a+1,a+n+1);
        build(1,1,xn+1);
        ll ans=0,sum=0;
        ll beg=1,now=1;
        memset(vis,0,sizeof(vis));
        while(beg<=n)
        {
            ll pre=0;
            while(a[beg].y==a[now].y&&now<=n)
            {
                ll tmp=query(1,1,xn+1,pre+1,a[now].x-1);
                ans-=tmp*(tmp+1)/2;
                pre=a[now].x;
                now++;
            }
            ll tmp=query(1,1,xn+1,pre+1,xn);
            ans-=tmp*(tmp+1)/2;
            while(beg<now)
            {
                if(!vis[a[beg].x])
                {
                    sum++;
                    vis[a[beg].x]=1;
                    update(1,1,xn+1,a[beg].x);
                }
                beg++;
            }
            ans+=(sum+1)*sum/2;
        }
        cout<<ans<<endl;
        return 0;
    }

转载于:https://www.cnblogs.com/Forever-666/p/11253460.html

[QAQQAQ]: https://codeforces.com/problemset/problem/1190/D
[1605368-20190805231602920-984257673.png]: /images/20230601/157628c5088142dea86e88d945d1ae36.png
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/606579ff1a8e478c91a804f3df1544d0.png