题目大意:
“有 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; }
全部评论
(0) 回帖