第一式：https://ac.nowcoder.com/acm/contest/143/I
题意：
有 n 个点，一个点集 S 是好的，当且仅当对于他的每个子集 T，存在一个右边无限长的矩形，使得这个矩形包含了 T，但是和 S-T 没有交
求这 n 个点里有几个好的点集
1<=n<=10^5
1）：当只选取1个点时，我们可以发现，任何一个点都满足题意。
2）：当我们选取2个点时，我们可以发现如果要满足一个无限向右的矩形只框住一个点，当且仅当两个点的纵坐标不相同。因此，对于选2个点的总的方案数等于C(n,2)-C(纵坐标相同的个数，2）
3）：当我们选3个点的时候（假设三个点为a,b,c），我们可以发现，当我们选取{a,b}作为子集，倘如第三个点c在{a,b}的右边，则我们发现由{a,b}组成的矩形一定包含{c}，故不成立。因此{c}必定在{a,b}的左边，即当且仅当三个点的能够构成一个‘<‘号的形式才能够符合题意。
4）：当选4个点及以上时，我们发现不管怎么样摆，均不可能出现3）的情况，故4个点以上的点是不合理的。
因此现在我们只需要处理的就是3）中的情况。对于3）的情况。我们只要求出在第i个点之前，有多少个点的x坐标比当前点大(记位below)，再求出在第i个点之后有多少个点的x坐标比当前点大(记位above)，那么对于第i个点而言，该点的方案数即为below*above了。
而对于below和above值的维护，我们需要先将y坐标进行离散化，然后将数组按照x坐标进行排序，然后用树状数组对区间进行维护即可。
现在问题的转化为在平面上有多少个不同的3对点集可以构成 "<" 的形状
现在观察此图可以发现：
对于包括点1的点集的情况无非就是 在点1上面的点与在点1下面的点来构成，那总的答案就一个组合的问题 cnt1*xcnt2;
所以我们就要只要在点1上面的点的个数与在点一下面点的个数（还要保证是在点1的右边）
所以很自然的想到对x排序,然后从x大开始便利（因为比当前点的 x小的点是没有价值的），用树状树状维护一个y上面的前缀和既可
#include<bits/stdc++.h> using namespace std; #define ll long long const int mod = 998244353; const int maxn=100010; ll n; struct no { int x,y; }a[maxn]; int tree[maxn*4],b[maxn]; ll box[maxn]; void add(int x , int c) { while(x<=n) { tree[x]+=c; x+=(x&(-x)); } } int sum(int x) { int ret=0; while(x) { ret+=tree[x]; x-=(x&(-x)); } return ret; } bool cmp(no a , no b) { return a.x>b.x; } int main() { scanf("%lld",&n); for(int i=1 ; i<=n ; i++) { scanf("%d%d",&a[i].x,&a[i].y); b[i]=a[i].y; } sort(b+1,b+1+n); for(int i=1 ; i<=n ; i++) { a[i].y=lower_bound(b+1,b+1+n,a[i].y)-b; box[a[i].y]++; } ll ans=n+n*(n-1)/2; ///统计一个点和两个点的情况 for(int i=1 ; i<=n ; i++) ans-=box[i]*(box[i]-1)/2; ///减去两个点有相同的y ans=(ans+mod)%mod; ///统计 "<" 的情况 int L=1; sort(a+1,a+1+n,cmp); for(int i=1 ; i<=n ; i++) { ll down=sum(a[i].y-1); ll up=sum(n)-sum(a[i].y); ans=(ans+down*up)%mod; if(a[i].x!=a[i+1].x) { for(;L<=i ; L++) add(a[L].y,1); } } printf("%lld\n",ans); return 0; }
第二式：http://codeforces.com/contest/1191/problem/F
题意： 给出在二维平面上的点，问有多少个上面无限延长的矩阵是不同的 ， 不同的定义为矩阵里面的点集是不同的
分析：这需要对x,y进行一个离散化的操作：
注意到其实从上往下一行一行扫过去，每次必须新增的元素才是新的集合，那很容易想到一个不重不漏的办法就是每次计算“以点p[i]为加进去的新点中的结束的集合”，那么假设一开始p[i]的左侧有cntl个点，那么显然有(cntl+1)条线在p[i]的左侧，而p[i]的右侧有cntr个点，也是(cntr+1)条线。
这个cntl显然就是query(1,p[i].x-1)，而右侧则是query(p[i].x+1,p[i+1].x-1)，因为不能包含同y的下一个点p[i+1]，而其中，上面的点选法也会产生区别。
这个线段树的更新操作是赋值而不是加+1 ， （因为如果同一条竖线上有多个点那其实排序去选择也只有一个价值而已）
那么每层加入一个正无穷也就是xn+1就可以了。
原文：https://www.cnblogs.com/shuaihui520/p/11188103.html
