洛谷 P3660 USACO17FEB Why Did the Cow Cross the Road III 题解
题意有一个圆，圆周上按顺时针方向给出 2 n 2n 2n个点。第 i i i个点的颜色是 c o l o r i color_i colori，此中数据包管 1 ≤ c o l o r i ≤ n 1\le color_i\le n 1≤colori≤n，而且每种不同的颜色有且只有两个点。不存在位置重叠的点。在颜色雷同的两个点之间连一条边（线段）。
求有多少对边是交叉的？
1 ≤ n ≤ 50000 1\le n \le 50000 1≤n≤50000
https://i-blog.csdnimg.cn/direct/71203c1f276541d38f81005c7306c90a.png
思路
转换一下题意，把所谓的“圆圈”拉平成一条直线上的 2 n 2n 2n个点，以相等的两个数的下标作为两头点连一条线段，求线段存在交集且不存在全包含关系的对数。https://i-blog.csdnimg.cn/direct/8d21fa26442249cb8845fe63a9fd7155.png#pic_center
遇到线段覆盖题目，可以考虑使用树状数组来维护区间内的点数个数。罗列到一条线段，就在树状数组上给两头端点分别加一；计算一条线段 i ( l e − r i ) i(le-ri) i(le−ri)的贡献就是 q u e r y ( r i i − 1 ) − q u e r y ( l e i ) query(ri_i-1)-query(le_i) query(rii−1)−query(lei)
如许算难道不会算重吗？
可以先考虑处置惩罚长度更长的线段，假如一条线段 b b b被线段 a a a完全覆盖，必然有 l e n a > l e n b len_a>len_b lena>lenb，此时会先处置惩罚 a a a再处置惩罚 b b b，就不会多算 b b b的两头节点了。
对于别的的线段，要么与线段 a a a自己相离，固然不会计入贡献，要么一端端点在开区间 ( l e a , r i a ) (le_a,ri_a) (lea,ria)内，计入贡献为 1 1 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;
bool cmp(seg x,seg y)
{
return x.r-x.l>y.r-y.l;
}
struct BT
{
ll T;
ll lowbit(ll x)
{
return x&(-x);
}
void add(ll x,ll k)
{
for(int i=x;i<=n*2;i+=lowbit(i))
T+=k;
}
ll query(ll x)
{
ll ret=0;
for(int i=x;i>=1;i-=lowbit(i))
ret+=T;
return ret;
}
}B;
int main()
{
scanf("%lld",&n);
for(int i=1;i<=n*2;i++)
{
ll x;
scanf("%lld",&x);
if(!a.l)a.l=i;
else a.r=i;
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)
{
B.add(a.l,1);
B.add(a.r,1);
ans+=B.query(a.r-1)-B.query(a.l);
}
printf("%lld",ans);
return 0;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]