本文共 2139 字，大约阅读时间需要 7 分钟。

一、题意

定义点集S是好点集：S的每一个子集都能被一个左边界和宽固定，长度无限长的矩形覆盖，并且只会覆盖该子集中的点。

给一个n个点的集合T，问集合T的子集有几个是好点集。每个点记作(x,y)。

数据范围：

二、题解

设满足好点集要求的T的子集为R

（1）R的子集的大小是1都是可以的。

（2）R的子集的大小是2，需要纵坐标不同。这个直接统计就好了。

（3）R的子集的大小是3，需要构成'<'这个形状，即下图所示。先排序，再pbds或者bit都行。

（4）4个点及以上不可以。

三、感受

查排名直接order_of_key，不用先lower_bound

四、代码

#include
   
    #include
    
     #include
     
      #define pb push_back#define fi first#define se second#define sz(x)  (int)x.size()#define cl(x)  x.clear()#define all(x)  x.begin() , x.end()#define rep(i , x , n)  for(int i = x ; i <= n ; i ++)#define per(i , n , x)  for(int i = n ; i >= x ; i --)#define mem0(x)  memset(x , 0 , sizeof(x))#define mem_1(x)  memset(x , -1 , sizeof(x))#define mem_inf(x)  memset(x , 0x3f , sizeof(x))#define debug(x)  cerr << #x << " = " << x << '\n'#define ddebug(x , y)  cerr << #x << " = " << x << "   " << #y << " = " << y << '\n'#define ios std::ios::sync_with_stdio(false) , cin.tie(0)using namespace std ;using namespace __gnu_pbds ;template
      
        using ordered_set = tree
       
         , rb_tree_tag, tree_order_statistics_node_update> ;typedef long long ll ;typedef long double ld ;typedef pair
        
          pii ;typedef pair
         
           pll ;const int mod = 998244353 ;const int maxn = 2e5 + 10 ;const int inf = 0x3f3f3f3f ;const double eps = 1e-6 ; mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count()) ; int n ;ordered_set
          
            s ;struct node{ ll x , y ;} p[maxn] ;bool cmp1(node s , node t){ return s.y < t.y ;}bool cmp2(node s , node t){ return s.x > t.x ;}int main(){ ios ; ll ans = 0 ; cin >> n ; rep(i , 1 , n) cin >> p[i].x >> p[i].y ; //1个点 ans += n ; //2个点 sort(p + 1 , p + n + 1 , cmp1) ; rep(i , 1 , n) { int j = i ; while(j + 1 <= n && p[j + 1].y == p[j].y) j ++ ; ans += 1ll * (j - i + 1) * (n - j) % mod , ans %= mod ; i = j ; } //3个点 sort(p + 1 , p + n + 1 , cmp2) ; rep(i , 1 , n) { int j = i ; while(j + 1 <= n && p[j + 1].x == p[j].x) j ++ ; rep(k , i , j) { ll t1 = sz(s) - s.order_of_key({p[k].y + 1 , 0}) ; ll t2 = s.order_of_key({p[k].y - 1 , 10000000}) ; ans += t1 * t2 % mod , ans %= mod ; } rep(k , i , j) s.insert({p[k].y , k}) ; i = j ; } cout << ans << '\n' ; return 0 ;}