|
||||||||||
DZY Loves InversionsTime Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 525 Accepted Submission(s): 163 Problem Description DZY has a array $a$, consisting of $n$ positive integers, indexed from 1 to $n$. Let's denote the number with index $i$ as $a_i$. DZY wants to count, with a given pair ($l,r$)$(l\leq r)$, how many pairs of integers $i$ and $j$ are there, such that $l \leq i \leq j \leq r$ and the sequence $b=a_{i}a_{i+1}\cdots a_{j}$ has exactly $k$ inversions. Moreover, DZY has $q$ queries. Input The input consists several test cases.($TestCase\leq 5$) The first line contains three integers $n, q, k(1 \leq n \leq 10^5, 1 \leq q \leq 10^5, 0 \leq k \leq 10^{18})$. The next line contains $n$ positive integers, separated by single spaces, $a_1,a_2,\cdots ,a_n(1 \leq a_i \leq 10^9)$. Each of the next $q$ lines has two integers: $l,r$, representing a query. Output For each query, please print a line containing the answer. Sample Input
Sample Output
Hint query 1. (2,4), (3,4) are ok. query 2. No such pair. query 3. (3,4) is ok. query 4. (1,2), (1,3), (2,4), (3,4), (4,5) are ok. Source | ||||||||||
|