Hi I faced a problem and I'll be glad if you help me. We have two arrays a and b we want to calculate number of pairs (i,j) such that:

*i < j*

*a[i] > b[j]*

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

1 | tourist | 3619 |

2 | Um_nik | 3493 |

3 | ecnerwala | 3446 |

4 | Radewoosh | 3383 |

5 | ksun48 | 3357 |

6 | yosupo | 3324 |

7 | Benq | 3299 |

8 | maroonrk | 3243 |

9 | apiadu | 3238 |

10 | Petr | 3217 |

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

1 | Errichto | 207 |

2 | Monogon | 199 |

3 | SecondThread | 195 |

4 | vovuh | 189 |

5 | antontrygubO_o | 186 |

5 | Um_nik | 186 |

7 | pikmike | 184 |

8 | Ashishgup | 182 |

9 | pashka | 169 |

10 | Radewoosh | 167 |

Hi I faced a problem and I'll be glad if you help me. We have two arrays a and b we want to calculate number of pairs (i,j) such that:

*i < j*

*a[i] > b[j]*

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/27/2020 00:57:12 (f3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Auto comment: topic has been updated by radal (previous revision, new revision, compare).You can easily find the solution on stackoverflow

For each a[i] can't you just count the number of elements in b to its right that are smaller than it? This is the same as counting inversions in a single array.

Thank you guys, it was really helpful.

If the values of array are upto 10^9 then we first compress all values in range [1, 1e6] (whatever the size of array) because we are not actually interested in values themselves but the comparison between them. Then use fenwik tree to maintain count of each element upto every index, then anytime if we want number of values less than particular value for example X then we can simply write query(1, X — 1). You can also try a similar question https://codeforces.com/problemset/problem/459/D