牛客网暑期多校第五场I (vcd)

n个点，一个点集S是好的，当且仅当对于他的每个子集T，存在一个右边无限延长的矩形，使的这个矩形包含了T，但是和S-T没有交集。

求有多少个这种集合。

画图找规律可得

当我们求的集合中的点只有一个时，肯定满足要求 。

当有两个点且这两个点y坐标不相等也满足要求。

当有三个点组成一个小于号形状的集合S时，这个集合S的子集T一定与S-T无交集，当组成一个大于号时。我们取大于号左边的两个端点组成的T集合一定与右边的那个端点有交集。

当有四个点组成的S点集他一定存在一个子集T和S-T有交集。

所以我们计算小于等于三个点的情况就行了。

一的情况直接是n。

二的情况总的情况减去y坐标相等的点的情况就行了。

三的情况就是数一下有多少个小于号的情况，树状数组维护一下就行了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod=998244353;
struct node
{
    ll x,y,pos;
} a[100005];
ll c[100005],d[500005],b[100005];
ll n;
ll lowbit(ll x)
{
    return x&-x;
}
void add(ll x,ll y)
{
    while(x<=n)
    {
        d[x]+=y;
        x+=lowbit(x);
    }
}
ll Sum(ll x)
{
    ll sum=0;
    while(x>0)
    {
        sum+=d[x];
        x-=lowbit(x);
    }
    sum%=mod;
    return sum;
}
bool cmp(node q,node w)
{
    return q.x>w.x;
}
int main()
{
    cin>>n;
    for(ll i=1; i<=n; i++)
    {
        cin>>a[i].x>>a[i].y;
        b[i]=a[i].y;
    }
    sort(b+1,b+1+n);
    for(ll i=1; i<=n; i++)
    {
        a[i].y=lower_bound(b+1,b+1+n,a[i].y)-b;        //分类统计。
        c[a[i].y]++;
    }
    sort(a+1,a+1+n,cmp);
    ll ans=n+n*(n-1)/2;            // 1个点和两个点的总个数 
    for(ll i=1;i<=n;i++)        //减去同一条y上的两个点的情况 
    {
        ans-=c[i]*(c[i]-1)/2;
    }
    ans%=mod;
    ll now=1;        
    for(ll i=1;i<=n;i++)        //统计有几个小于号 
    {        
        ll up=Sum(n)-Sum(a[i].y);    //上面 
        ll down=Sum(a[i].y-1);        //下面 
        ans+=(down*up)%mod;            //两两组合 
        ans%=mod;
        if(a[i].x!=a[i+1].x)//x大于a[i+1].x的点扔进树状数组,这些点都可以当成小于号左边的那两个个点 
        {
            //cout<<a[i].x<<endl;
            for(;now<=i;now++)        
            {
                add(a[now].y,1);
            }
        }
    }
    cout<<ans%mod;
    return 0;
}
/*
3
1 2
2 1
2 3
*/