Sherlock and Inversions
All submissions for this problem are available.
After a long series of jobless days, Sherlock and Watson frustated by the lack of new cases, decide to turn their minds toward something interesting like solving few logical problems. One of the problems they have to solve now is as follows:
Given an array A of size N and a list of Q number of queries, where each query has two numbers L and R, find for each query the number of inversions in the subarray from Lth to Rth position (both inclusive) of the array A( array has 1-based index).
For an array A two elements A[i] and A[j] form an inversion if A[i] > A[j] and i < j. Help them to solve this problem.
- First line contains a single integer, length N of the array.
- Second line has N space separated numbers, where ith element is A[i].
- Third line has a single integer Q.
- Next Q lines have 2 space separated integers L and R of that query.
- Output Q lines, ith line having a single integer, the answer to the ith query
- 1 ≤ N ≤ 20000
- 0 ≤ A[i] ≤ 10^9
- 1 ≤ Q ≤ 20000
- 1 ≤ L ≤ R ≤ N
7 7 9 3 5 1 6 4 4 1 4 3 5 1 2 1 7Output:
4 2 0 14
|Tags||bit, dbyz2014, iiti_adm, medium-hard, offline-process|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.