**Hello everybody**

**Problem**

**Thank you!**

**UPD:**

Before contest

Codeforces Round 940 (Div. 2) and CodeCraft-23

2 days

Register now »

Codeforces Round 940 (Div. 2) and CodeCraft-23

2 days

Register now »

*has extra registration

# | User | Rating |
---|---|---|

1 | ecnerwala | 3648 |

2 | Benq | 3580 |

3 | orzdevinwang | 3570 |

4 | cnnfls_csy | 3569 |

5 | Geothermal | 3568 |

6 | tourist | 3565 |

7 | maroonrk | 3530 |

8 | Radewoosh | 3520 |

9 | Um_nik | 3481 |

10 | jiangly | 3467 |

# | User | Contrib. |
---|---|---|

1 | maomao90 | 174 |

2 | adamant | 164 |

2 | awoo | 164 |

4 | TheScrasse | 160 |

5 | nor | 159 |

6 | maroonrk | 156 |

7 | -is-this-fft- | 150 |

7 | SecondThread | 150 |

9 | orz | 146 |

10 | pajenegod | 145 |

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/19/2024 15:16:15 (l2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Hi, I'm not at home right now, so I am unable to implement it. I think the intended solution is to use the fact that a[i] is small.

This inspires us to make each node have an array of size 40, to store the number of occurrences of each number. Then merging nodes is just counting the inversion number of the two arrays + inversion number of left array + inversion number of right array.

I didn't quite get it.

Hmmm, you can try understanding a node in the segment tree contains the information of all the numbers in the segment. When we want to combine two nodes, lets call them L and R, inversion of current node = inversion of L + inversion of R + inversion of array of (L, R). In order to do that, we can maintain a frequency table in each of the node (size 40). Also notice that it is better that we count that with a prefix sum in 40 operations, instead of doing a 40 * 40 operation (looping through i, j).

After merging the nodes, we still notice that our answer can't just simply sum all together, because the segment tree considers separated segments. But we can observe that the number of segments is around log N, so we can simply brute force them together to calculate the answer.

Code link here

the time complexity for my solution is $$$O(40 * N log N)$$$ which is passable.

thanks!=)

Hint 1Store frequency of elements in the range + count of inversion in the range

Hint2For combining brute for both ranges using frequency

combine — ans=inversion in left range + inversion in right range + inversion across range.

thanks, I will try to solve it

I think the idea is to use merge sort tree. If you don't know about it, then it's a special kind of segment tree with array/map/st/multiset stored in each node representing the count of each element in the range

I figured out how to solve the problem,

but`vector<pair<int, vector<int>(and I need the array size to be 40)> tree;`

`tree.assign(2*size, ????)`

what do I need to write where is the question mark? and I need the array size to be 40

Use arrays instead of vectors should be easier. But, if you really want to implement it that way, you can use vector(45, 0).

Auto comment: topic has been updated by I_love_Leyeli_Meredova (previous revision, new revision, compare).