青岛网站设计公司电话,潍坊高新区建设局门户网站,嘉兴建站公司,做游戏网站的需求分析题意
有一个圆#xff0c;圆周上按顺时针方向给出 2 n 2n 2n个点。第 i i i个点的颜色是 c o l o r i color_i colori#xff0c;其中数据保证 1 ≤ c o l o r i ≤ n 1\le color_i\le n 1≤colori≤n#xff0c;而且每种不同的颜色有且只有两个点。不存在位置重叠的点…题意
有一个圆圆周上按顺时针方向给出 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 思路
转换一下题意把所谓的“圆圈”拉平成一条直线上的 2 n 2n 2n个点以相等的两个数的下标作为两端点连一条线段求线段存在交集且不存在全包含关系的对数。 遇到线段覆盖问题可以考虑使用树状数组来维护区间内的点数个数。枚举到一条线段就在树状数组上给两端端点分别加一计算一条线段 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_alen_b lenalenb此时会先处理 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。
代码
#includebits/stdc.h
using namespace std;
#define ll long long
#define ls u1
#define rs u1|1
const ll N1e52;
ll n,ans;
struct seg
{ll l,r;
}a[N];
bool cmp(seg x,seg y)
{return x.r-x.ly.r-y.l;
}
struct BT
{ll T[N];ll lowbit(ll x){return x(-x);}void add(ll x,ll k){for(int ix;in*2;ilowbit(i))T[i]k;}ll query(ll x){ll ret0;for(int ix;i1;i-lowbit(i))retT[i];return ret;}
}B;
int main()
{scanf(%lld,n);for(int i1;in*2;i){ll x;scanf(%lld,x);if(!a[x].l)a[x].li;else a[x].ri;}sort(a1,an1,cmp);for(int i1;in;i){B.add(a[i].l,1);B.add(a[i].r,1);ansB.query(a[i].r-1)-B.query(a[i].l);}printf(%lld,ans);return 0;
}
