kindly help in problem 1677A - Tokitsukaze and Strange Inequality,i dont want to use data structure like fenwick tree.I tried to understand it from editorial but am unable to.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | awoo | 161 |
1 | cry | 161 |
3 | maomao90 | 160 |
4 | atcoder_official | 156 |
4 | -is-this-fft- | 156 |
6 | nor | 155 |
7 | adamant | 153 |
7 | maroonrk | 153 |
9 | Um_nik | 152 |
10 | djm03178 | 146 |
kindly help in problem 1677A - Tokitsukaze and Strange Inequality,i dont want to use data structure like fenwick tree.I tried to understand it from editorial but am unable to.
Name |
---|
Auto comment: topic has been updated by BLUmOOn (previous revision, new revision, compare).
Fix indices a and c such that $$$p_a<p_c$$$ as given in the condition. Then count the number of inversions in the range [a+1,n]. This can be precomputed for all values of a in $$$O(N^2)$$$ or can also be calculated individually for each a as you traverse using an ordered_set or segment tree in $$$O(NlogN)$$$ for each a, resulting in a total of $$$O(N^2logN)$$$. Even though, I doubt that the second approach will pass the given constraints or might just barely manage to escape TLE.
Let the number of inversions in range [i,j] be denoted by $$$Inv(i,j)$$$. Even without precomputation Inv(i,j) can be calculated in $$$O(NlogN)$$$ as mentioned above.
Now, for each index a, the Inv(a+1,n) will contain pair such that both b and d lie in range [a+1,c] or both lie in range [c,n]. Since we want to avoid those cases as it violates the condition $$$a<b<c<d$$$, we subtract $$$Inv(a+1,c)$$$ and $$$Inv(c,n)$$$ from $$$Inv(a+1,n)$$$.
Hence the final answer will be
thanks for the reply,what are u defining inv(i,j) to be?Won't subtracting inv(a+1,c) mean we are subtracting some pairs of (b,d) that would instead should have been counted.
No, if we count pairs of inversions in the range [a+1,c] that would just mean we are counting all those pairs of {b,d} which satisfy $$$b<d$$$ and $$$p_b>p_d$$$ and lie in range [a+1,c]. But this means that, $$$a<b<d<=c$$$, which violates the condition on indices.