CF297E JZOJ 4018.【雅礼联考DAY02】Magic

$Hyperlink$

https://www.luogu.com.cn/problem/CF297E

$Description$

在一个园上分布着$2n$个点，对应$n$条弦

请求出有多少个无序的三元组，使得对应的三条弦可以通过距离的缩放中心对称

数据范围：$n\le 10^5$

$Solution$

三条弦可能的情况有下列5种

答案即为第二种和第五种的组合，显然用容斥可以更好得到答案

所有的组合情况共为$C_n^3$，我们直接当做$Ans=n(n-1)(n-2)/6$，然后减去1、3、4三种情况即可

第一种情况比较好计算，我们只需要找到第$i$条弦左边不与它相交的弦的数量$x_i$，以及右边不与它相交的弦的数量$y_i$，答案即为$x_i\times y_i$

既然左右两边不相交的弦的数量是$x_i+y_i$，则与$i$相交的弦即为所有的弦出去本身（$n-1$）减去不想交的弦的数量，即$z_i=n-1-(x_i+y_i)$

则第三第四种的总和即为$z_i\times (x_i+y_i)$【相交的一个，不相交的两个】

则最终答案即为$Ans-{\sum }_{i=1}^n(x_i{y}_i+z_i\times (x_i+y_i))$

在算法实现中，具体的流程与上述描述的略为不同，我们不是直接求出不相交的，而是通过树状数组维护相交的弦的数量，再通过容斥计算得出

首先将所有的弦按照右端点升序排序，这样可以保证后面的弦的右端点一定在前面的弦的右端点的后边

假设我们现在要求相交的弦的数量，即$z_i$，定义与它相交的弦是$j$，有两种情况

1. $j$左端点在$i$的左边，且$j$的右端点在$i$之间
2. $j$的左端点在$i$之间，且$j$的右端点在$i$右边

用$Tp$（一个区间修改，单点查询的树状数组）计算所有右端点在$i$左侧的弦【一段区间】，表示这段区间有一条弦是可以作为$j$的端点的，如果$p[i].l$在这段区间内，那么就会有贡献，我们查询$Tp.ask(p[i].l)$即可，由于我们维护的是右端点在$i$左侧的弦，所以我们要做完$i$之后将这条线更新进去，即$Tp.add(p[i].l,1)Tp.add(p[i].r,-1)$

用$Ta$（一个单点修改，区间查询的树状数组）计算所有的右端点在$i$右侧的左端点，因为我们已经排了序，所以我们先放入所有的左端点，在做每一条弦之前把这条弦删掉（因为它不可能在自己的右边），这样我们就知道了右端点在$i$的右边的左端点的分布情况（即第二种），那么我们只需要知道在$p_i.l\sim p_i.r$之间有多少个合法的左端点即可，即$Ta.ask(p[i].r)-Ta.ask(p[i].l)$

于是我们求出了$z_i$，现在考虑用它求$x_i$和$y_i$中的其中一个，就可以求出剩下那个，由于我们是按照右端点升序排序的，那么满足前面的右端点一定不会伸到后面去，所以$r$已经在里面了，只需要找到$p[i].l<p[j].l<p[i].r$的【即所有左边的弦】减去所有相交的弦再除以2就可以得到$x_i$

然后$y_i=n-1-(x_i+z_i)$

直接统计即可

时间复杂度：$O(nlogn)$

$Code$

#include<cctype>
#include<cstdio>
#include<algorithm>
#define LL long long
#define N 100010
using namespace std;int n;
struct node{int l,r;}p[N];
LL ans,x,y,z;
inline LL read()
{char c;LL d=1,f=0;while(c=getchar(),!isdigit(c)) if(c=='-') d=-1;f=(f<<3)+(f<<1)+c-48;while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48;return d*f;
}
inline bool cmp(node x,node y){return x.r<y.r;}
struct sszz
{LL C[N*2];inline void add(int x,int v){for(;x<=2*n;x+=x&-x) C[x]+=v;return;}inline LL ask(int x){LL T=0;for(;x;x-=x&-x)T+=C[x];return T;}
}Ta,Tp;
signed main()
{n=read();for(register int i=1;i<=n;i++){p[i].l=read();p[i].r=read();if(p[i].l>p[i].r) swap(p[i].l,p[i].r);}sort(p+1,p+1+n,cmp);ans=(long long)n*(n-1)*(n-2)/6ll;for(register int i=1;i<=n;i++) Ta.add(p[i].l,1);for(register int i=1;i<=n;i++){Ta.add(p[i].l,-1);z=Tp.ask(p[i].l)+Ta.ask(p[i].r)-Ta.ask(p[i].l);x=(p[i].r-p[i].l-1-z)/2;y=n-1-x-z;ans-=x*y+z*(x+y)/2;Tp.add(p[i].l,1);Tp.add(p[i].r,-1);}                printf("%lld",ans);
}