洛谷 P3660 USACO17FEB Why Did the Cow Cross the Road III 题解

题意

有一个圆，圆周上按顺时针方向给出$2n$个点。第$i$个点的颜色是$colo{r}_i$，其中数据保证$1\le colo{r}_i\le n$，而且每种不同的颜色有且只有两个点。不存在位置重叠的点。在颜色相同的两个点之间连一条边（线段）。

求有多少对边是交叉的？

$1\le n\le 50000$

思路

转换一下题意，把所谓的“圆圈”拉平成一条直线上的$2n$个点，以相等的两个数的下标作为两端点连一条线段，求线段存在交集且不存在全包含关系的对数。
遇到线段覆盖问题，可以考虑使用树状数组来维护区间内的点数个数。枚举到一条线段，就在树状数组上给两端端点分别加一；计算一条线段$i(le-ri)$的贡献就是$query(r{i}_i-1)-query(l{e}_i)$

这样算难道不会算重吗？

可以先考虑处理长度更长的线段，如果一条线段$b$被线段$a$完全覆盖，必然有$le{n}_a>le{n}_b$，此时会先处理$a$再处理$b$，就不会多算$b$的两端节点了。

对于其它的线段，要么与线段$a$本身相离，当然不会计入贡献，要么一端端点在开区间$(l{e}_a,r{i}_a)$内，计入贡献为$1$。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ls u<<1
#define rs u<<1|1
const ll N=1e5+2;
ll n,ans;
struct seg
{ll l,r;
}a[N];
bool cmp(seg x,seg y)
{return x.r-x.l>y.r-y.l;
}
struct BT
{ll T[N];ll lowbit(ll x){return x&(-x);}void add(ll x,ll k){for(int i=x;i<=n*2;i+=lowbit(i))T[i]+=k;}ll query(ll x){ll ret=0;for(int i=x;i>=1;i-=lowbit(i))ret+=T[i];return ret;}
}B;
int main()
{scanf("%lld",&n);for(int i=1;i<=n*2;i++){ll x;scanf("%lld",&x);if(!a[x].l)a[x].l=i;else a[x].r=i;}sort(a+1,a+n+1,cmp);for(int i=1;i<=n;i++){B.add(a[i].l,1);B.add(a[i].r,1);ans+=B.query(a[i].r-1)-B.query(a[i].l);}printf("%lld",ans);return 0;
}