Sequence and Queries 23
Time limit5sMemory limit512 MB
Given a sequence and range queries, count for each query the number of pairs inside the range where an earlier element exceeds a later one.
- Level
Medium7 of 10
- Topics
- Divide and conquer, Sorting, Binary search, Prefix sum
- Solved
- No attempts yet
Problem
A sequence A1, A2, ..., AN of length N is given. Write a program that processes the following queries.
s e: Print the number of pairs (i, j) such that s ≤ i < j ≤ e and Ai > Aj. (1 ≤ s ≤ e ≤ N)
Input
The first line gives the length of the sequence N (1 ≤ N ≤ 100,000) and the number of queries M (1 ≤ M ≤ 100,000).
The second line gives A1, A2, ..., AN. (1 ≤ Ai ≤ 1,000,000,000)
Each of the next M lines gives one query.
Output
Print the answer for each query.