Codeforces Round #790 (Div. 4) H. Maximum Crossings

H1. Maximum Crossings (Easy Version)

H2. Maximum Crossings (Hard Version)

Let’s look at two wires from $i$ → $a_i$ and $j$ → $a_j$.

• If $a_i$ < $a_j$, there can never be any intersection.
• If $a_i$ > $a_j$, there has to be an intersection.
• If $a_i$ = $a_j$, it is possible that there is an intersection or not, depending on how we arrange the wires on the bottom terminal.

In the last case, if there are multiple wires that go to the same segment $a_i$, 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]$, 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)$ such that $a_i$ $\ge$ $a_j$. You can brute force all pairs in $O(n^2)$.

#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Read the solution of the easy version.
We want to count the number of pairs $(i,j)$ such that $i<j$ and $a_i$ $\ge$ $a_j$. This is a standard problem, and we can do this we can use a segment tree or BIT, for example. Insert the $a_j$ from $j$ $=$ $1$ to n, and then for each $a_j$ count the number of $a_i$ $\le$ $a_j$ using a BIT.

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(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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40