Let’s look at two wires from i i i → a i a_i ai and j j j → a j a_j aj.
In the last case, if there are multiple wires that go to the same segment a i a_i ai, we can make all pairs of them cross by arranging the points in which they hit this segment from right to left. For example, if a = [ 1 , 1 , 1 , 1 ] a=[1,1,1,1] a=[1,1,1,1], then we can make all pairs of segments cross as shown.
Since we want to maximize the number of intersections, we just need to count the number of pairs
(
i
,
j
)
(i,j)
(i,j) such that
a
i
a_i
ai
≥
≥
≥
a
j
a_j
aj. You can brute force all pairs in
O
(
n
2
)
O(n^2)
O(n2).
#include
using namespace std;
int main()
{
int T;cin>>T;
while(T--)
{
int n;cin>>n;
vector<int> a(n);
for(int i=0;i<n;i++) cin>>a[i];
int res=0;
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
if(a[i]>=a[j])
res++;
cout<<res<<endl;
}
return 0;
}
Read the solution of the easy version.
We want to count the number of pairs
(
i
,
j
)
(i,j)
(i,j) such that
i
<
j
i
It is also related to the problem of counting inversions, so you can solve it using a modification of merge sort.
Either way, the solution is O ( n l o g n ) O(nlogn) O(nlogn).
#include
using namespace std;
typedef long long LL;
const int N = 200010;
int tr[N],a[N],n;
void add(int x,int y)
{
for(;x<=n;x+=(x&-x))
tr[x]+=y;
}
LL query(int x)
{
LL res=0;
for(;x;x-=(x&-x))
res+=tr[x];
return res;
}
int main()
{
int T;cin>>T;
while(T--)
{
memset(tr,0,sizeof tr);
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
LL res=0;
for(int i=0;i<n;i++)
{
res+=query(n)-query(a[i]-1);
add(a[i],1);
}
cout<<res<<endl;
}
return 0;
}