这个题目一个队友没读懂, 然后我读错了题目, 还让他堆了半天的公式写了半天的代码, 交上去一直0.0, 另一队友问题目有没有读错, 我坚持没有读错, 然后坑了2个小时的时间,不然应该会早一点做出来。
题意: 平面上有n个不重和的点, 现在定义一个集合是好的, 那么就需要满足, 这个集合里的每一个子集 都存在一个 {(x, y) |x >= a, l <= y <= r}(a, l, r为任意实数) 的这个区域与原来集合求交 之后能表示出来。求这个n个点所组成的集合的非空子集有多少个是合法的。
解释一下样例的话 就是 对于 { (1,1) (2,2) (3,3) } 这个集合来说他不是好的一个好的集合, 他的子集{(1,1)} {(2,2)} {(3,3)} {(1,1) (2,2)} {(2,2) (3,3)} {(1,1) (2,2) (3,3)} 都可以通过原集合 和 一个{(x, y) |x >= a, l <= y <= r} 求交集得到, 但是对于 {(1,1) (3,3)} 这个子集来说, 不能求交集得到, 因为如果 存在(1,1) (3,3) 那么也一定存在 (2,2)。
题解:
只有一个点的情况 都是合法的
有2个点的情况 除了同y轴的任意2点组成的集合也是合法的
有3个点的情况 我们发现只有 一个点的 x 坐标小于 其他2个点的x坐标,并且 另外2个点的y坐标一个大于 这个点的y坐标 另一个小于 这个点的y坐标 这样的情况才会合法。
3个点以上的情况都是非法的。
我们每次处理到一个点 (x, y) 之后,我们都查询满足 (xi > x, yi > y)点的个数 设他为a, 然后查询(xi > x, yi < y) 的点的个数 设他为b,
先这个点与其他的点组个成2个点的情况 ans += a + b。
其次这个点与其他的点组成3个点的情况 ans += a * b。
这样处理完所有的点之后我们就可以求解了。
我们用树状数组来加快查询的速度。
首先存下所有的点, 离散化y的坐标, 然后在树状数组相应的位置加上值。
再从左到右处理所有的点, 每次处理到一个点的时候, 我们要先把所有的同x轴的点的值先删除掉, 因为同x轴的点只能和前面的点组成3个点的形式,但是这个东西在前面的点就处理过了,并且我们需要查询的是 后面的点的不同 y 的数目, 所以要先删除这些点的影响, 但是这些点都是可以两两组合的, 这个要先加上去。
代码:
#include<bits/stdc++.h>
using namespace std;
#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
typedef pair<int,int> pll;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL mod = ;
const int N = 1e5 + ;
pll p[N];
pll pp[N];
int vis[N];
int tree[N];
int k = ;
void add(int x, int c){
while(x <= k){
tree[x]+=c;
x += x&(-x);
}
}
int query(int x){
int ret = ;
while(x){
ret += tree[x];
x -= x&(-x);
}
return ret;
}
int main(){
int n;
scanf("%d", &n);
for(int i = ; i <= n; i++){
scanf("%d%d", &p[i].fi, &p[i].se);
pp[i].se = i;
pp[i].fi = p[i].se;
}
sort(pp+, pp++n);
for(int i = ; i <= n; i++){
if(pp[i].fi != pp[i-].fi) k++;
p[pp[i].se].se = k;
}
for(int i = ; i <= n; i++)
add(p[i].se, );
sort(p+, p+n+);
LL ans = n;
for(int i = ; i <= n; i++){
pp[] = p[i];
int j = i+, tt = ;
while(j <= n && p[j].fi == pp[].fi)
pp[tt++] = p[j++];
i = j - ;
for(int z = ; z < tt; z++)
add(pp[z].se, -);
ans += 1ll * tt * (tt-) / ;
for(int z = ; z < tt; z++){
int y = pp[z].se;
LL t1 = query(k) - query(y);
LL t2 = query(y-);
ans = ans + t1 * t2 + t1 + t2;
ans %= mod;
}
}
cout << ans << endl;
return ;
}