JZOJ4018. 【雅礼联考DAY02】Magic

Description

圆上有 2 ∗ n 个点和连接这些点的 n 条弦，这些弦不会在圆上相交。这2 ∗ n 个点按照在圆上的位置顺序依次标号为 1,2,…,2 ∗ n。
请求出有多少个无序的三元组，使得对应的三条弦可以通过距离的缩放中心对称。

Input

第一行一个数 n (n ≤ 100000)。
接下来 n 行，每行两个数，表示该弦的端点。保证一个数不会出现两次。

Output

输出一个数，表示方案数。

Sample Input

样例输入1：
4
5 4
1 2
6 7
8 3
样例输入2：
8
1 7
2 4
3 9
5 11
6 8
10 16
13 15
14 12

Sample Output

样例输出1：2
样例输出2：6

Data Constraint

对于30%数据，n ≤ 100.
对于60%数据，n ≤ 10000.
对于100%数据，n ≤ 100000.

题解

因为可以通过缩放来满足中心对称，
也就是说只用考虑他们的相对顺序。
先来看看任取3条边的情况，

可以知道2和5两种情况是满足题意的，
然而并不是很容易计算，
反而1这种情况是最简单的，
枚举一条边，用左边与它不相交的边和右边与它不相交的边乘在一起。
而只看3这种情况并不好算，而3、4又有个共同点，
有两条边相交，然后剩下一条边随便。
于是，对于每一条边考研计算出来：
$x_i$：左边与它不相交的边数
$y_i$：右边与它不相交的边数
$z_i$：与它相交的边数。
其中$x_i$和$y_i$可以用树状数组轻松算出来，
$z_i$=n-$x_i$-$y_i$-1

最后就用总的情况减去1、3、4的情况。

code

#include <queue>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string.h>
#include <cmath>
#include <math.h>
#include <time.h>
#define ll long long
#define N 100003
#define M 103
#define db double
#define P putchar
#define G getchar
#define inf 998244353
#define pi 3.1415926535897932384626433832795
using namespace std;
char ch;
void read(int &n)
{n=0;ch=G();while((ch<'0' || ch>'9') && ch!='-')ch=G();ll w=1;if(ch=='-')w=-1,ch=G();while('0'<=ch && ch<='9')n=(n<<3)+(n<<1)+ch-'0',ch=G();n*=w;
}int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
ll abs(ll x){return x<0?-x:x;}
ll sqr(ll x){return x*x;}
void write(ll x){if(x>9) write(x/10);P(x%10+'0');}struct node
{int x,y,id;
}a[N];bool cmp(node a,node b)
{return a.y<b.y;
}ll ans,s[N*2],x[N],y[N],z[N];
int n,id[N*2],p[N*2],sum;int x_(int x){return(-x)&x;}ll find(int x)
{ll p=0;for(int i=x;i;i=i-x_(i))p+=s[i];return p;
}void ins(int x)
{for(int i=x;i<=n*2;i=i+x_(i))s[i]++;
}int main()
{read(n);ans=(ll)n*(n-1)/2*(n-2)/3;for(int i=1;i<=n;i++){read(a[i].x),read(a[i].y);if(a[i].y<a[i].x)swap(a[i].y,a[i].x);a[i].id=id[a[i].x]=id[a[i].y]=i;p[a[i].x]=1,p[a[i].y]=2;}sum=0;for(int i=1;i<=n*2;i++)if(p[i]==1)x[id[i]]+=sum;else sum++;sum=0;for(int i=n*2;i;i--)if(p[i]==2)x[id[i]]+=sum;else sum++;sort(a+1,a+1+n,cmp);for(int i=1;i<=n;i++)y[a[i].id]=find(a[i].y)-find(a[i].x),ins(a[i].x);memset(s,0,sizeof(s));for(int i=n;i;i--)x[a[i].id]+=find(a[i].x),ins(a[i].x);for(int i=1;i<=n;i++)z[i]=n-x[i]-y[i]-1,ans=ans-x[i]*y[i]-(x[i]+y[i])*z[i]/2;printf("%lld\n",ans);return 0;
}