牛客143I vcd

题目大意：
“有 n(1 ≤ n ≤ 105 )个点，一个点集 S 是好的，当且仅当对于它的每个子集 T，存在一个右边无限长的矩形，使得这个矩形包含了 T，但是和 S-T 没有交。求这 n 个点里有几个好的点集。”
——SkyDec

知识点： 树状数组

解题思路：

        1、所有一个点的点集都是好的点集；
        2、所有两个点的点集都是好的点集，除非两个点的 y 坐标相同。因为没有办法单独取出左边那个点作为一个子集（相应的矩形跟右边的点一定有交）。由此推出：所有两个点及以上 y 坐标相同的点集都不好。
        3、三个点的点集的分布要满足 “<” 的形状才是好的点集。只有这样才能保证所有的子集都合法。
        4、三个点以上的点集都不好。只考虑所有三个点的子集，很明显没有办法使得所有的三个点的子集的分布都满足 “<” 的形状。
        1、2 的计算方法略，我们详细地说说 3 的计算方法。

        先将所有的点按照 y 坐标从大到小（或从小到大，后面要相应地改一下）排个序，然后扫一遍所有的点。维护两个树状数组，一个 tree[d] 保存所有 y 值大于目前的点且 x 值小于等于 d 的点对答案的贡献（贡献就相当于满足 y 值更大而 x 值也更大的点数），一个 pts[d] 保存 y 值大于目前的点且 x 值小于等于 d 的点数。对于每一个点 (x,y)，答案加上 tree[1...x-1] 之和即可。更新的时候要一层一层地更新（即将所有 y 值相同的点都遍历完了之后再更新）。

AC代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN=1e5+5;
const LL MOD=998244353;

struct Input{
    int x,y;
    bool operator <(const Input &b) const{
        return y<b.y;
    }
}inp[MAXN];
int xs[MAXN],cnt;
LL pts[MAXN],tree[MAXN];
int lowbit(int x){
    return x&(-x);
}
LL sum(LL nums[],int x){
    LL ret=0;
    while(x>0){
        ret+=nums[x];
        ret%=MOD;
        x-=lowbit(x);
    }
    return ret;
}
void add(int x,LL d){
    d%=MOD;
    while(x<=cnt){
        tree[x]+=d;
        tree[x]%=MOD;
        pts[x]++;
        pts[x]%=MOD;
        x+=lowbit(x);
    }
}
struct Queue{
    int x;
    LL d;
    Queue(int _x=0,LL _d=0){
        x=_x,d=_d;
    }
}que[MAXN];
int main(){
 //   freopen("out.txt","r",stdin);
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&inp[i].x,&inp[i].y);
        xs[i]=inp[i].x;
    }
    sort(inp+1,inp+1+n);
    sort(xs+1,xs+1+n);
    cnt=unique(xs+1,xs+1+n)-xs-1;

    LL ans=(1ll*n+1ll*n*(n-1)/2)%MOD;
    int ly=-1;
    LL now=0;
    for(int i=1;i<=n;i++){
        if(inp[i].y!=ly){
            for(int j=0;j<(int)now;j++)
                add(que[j].x,que[j].d);
            ans=((ans-(now-1)*now/2)%MOD+MOD)%MOD;
            ly=inp[i].y,now=1;
        }
        else
            now++;

        int pos=lower_bound(xs+1,xs+1+cnt,inp[i].x)-xs;
        ans=(ans+sum(tree,pos-1))%MOD;
        LL d=(sum(pts,cnt)-sum(pts,pos)+MOD)%MOD;
        que[now-1]=Queue(pos,d);
    }
    ans=((ans-(now-1)*now/2)%MOD+MOD)%MOD;
    printf("%lld\n",ans);

    return 0;
}