nowcoder多校5I(计数+bit)

nowcoder多校5I(计数+bit)

题意看了半天（雾。。

然后可以发现1个点一定可以，2个点只要连线不与y平行就可以。。

然后考虑3个点的。。3个点的话画几次可以发现必须得是<的才可以。。

然后4个点发现怎么画都画不出来。。

然后主要是算3点的。。枚举顶点，需要找x比他小的，y和他不同的点个数。。分侧求出后乘起来即可。。

然后这个可以按x从大到小枚举一下，用bit去维护对应y上的位置（当然要离散化）。。

x相同的时候需要注意add的顺序。。

/***　　　　　　  　　┏┓　　 　┏┓* 　　　　　  　　┏┛┗━━━━━━━┛┗━━━┓* 　　　　　  　　┃　　　　　　　┃ 　* 　　　　　  　　┃　　　━　　 　┃* 　　　　　  　　┃　＞　　　＜　┃* 　　　　　  　　┃　　　　　　　┃* 　　　　　  　　┃...　⌒　... 　┃* 　　　　　　  　┃              ┃* 　　　　　　  　┗━┓          ┏━┛* 　　　　　　　　　┃          ┃　Code is far away from bug with the animal protecting　　　　　　　　　　* 　　　　　　　　　┃          ┃   神兽保佑,代码无bug* 　　　　　　　　　┃          ┃　　　　　　　　　　　* 　　　　　　　　　┃          ┃  　　　　　　* 　　　　　　　　　┃          ┃* 　　　　　　　　　┃          ┃　　　　　　　　　　　* 　　　　　　　　　┃          ┗━━━┓* 　　　　　　　　　┃              ┣┓* 　　　　　　　　　┃              ┏┛* 　　　　　　　　　┗┓┓┏━━━━━━━━┳┓┏┛* 　　　　　　　　　　┃┫┫       ┃┫┫* 　　　　　　　　　　┗┻┛       ┗┻┛*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include<bits/stdc++.h>
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,l,r) for(int i=l;i>=r;i--)
#define link(x) for(edge *j=h[x];j;j=j->next)
#define mem(a) memset(a,0,sizeof(a))
#define ll long long
#define eps 1e-8
#define succ(x) (1LL<<(x))
#define lowbit(x) (x&(-x))
#define sqr(x) ((x)*(x))
#define mid (x+y>>1)
#define NM 100005
#define nm 100005
#define N 1000005
#define M(x,y) x=max(x,y)
const double pi=acos(-1);
const ll inf=998244353;
using namespace std;
ll read(){ll x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();return f*x;
}struct P{int x,y;bool operator<(const P&o){return x&(x==o.x&&y<o.y);}
}p[NM];
int n,b[NM],m;
ll ans,a[NM];
void add(int x){for(;x<=m;x+=lowbit(x))a[x]++;}
int sum(int x,int s=0){for(;x;x-=lowbit(x))s+=a[x];return s;}int main(){n=read();inc(i,1,n)p[i].x=read(),b[i]=p[i].y=read();sort(b+1,b+1+n);m=unique(b+1,b+1+n)-b-1;inc(i,1,n)p[i].y=lower_bound(b+1,b+1+m,p[i].y)-b;sort(p+1,p+1+n);ans=(ll)n*(n-1)/2%inf;ans+=n;ans%=inf;p[n+1].x=inf;inc(i,1,n){int j;for(j=i;p[i].x==p[j].x;j++){ll t=sum(m)-sum(p[j].y),k=sum(p[j].y-1);ans+=k*t%inf;ans%=inf;}j--;inc(k,i,j)add(p[k].y);i=j;}inc(i,1,m){int t=sum(i)-sum(i-1);ans=(ans-t*(t-1)/2%inf+inf)%inf;}return 0*printf("%lldn",ans);
}

vcd

链接：
来源：牛客网
 

时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

Kanade has an infinity set H contain all of sets such as {(x,y)|x>=a,l<=y<=r}  (a,l,r are arbitrary real numbers)

A point set S is good if and only if for each subset T of S there exist h in H satisfy 

Now kanade has n distinct points and she want to know how many non-empty subset of these points is good.

You need to output the answer module 998244353

输入描述:

The first line has one integer nThen there are n lines,each line has two integers x,y denote a point (x,y)

输出描述:

Output the answer module 998244353

示例1

输入

复制

3
1 1
2 2
3 3

输出

复制

6

备注:

1<=n<=10^51<=x, y<=10^9