#P6199. 「THUPC 2021」本质不同逆序对

    ID: 5489 传统题 4000ms 512MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF3000莫队分块数据结构排序树状数组

「THUPC 2021」本质不同逆序对

题目描述

给定一个长为 nn 的序列 aa。

有 mm 次询问,每次询问给定一个区间 [l,r][l,r],求 ∣{(ai,aj):l≤i<j≤r∧ai>aj}∣|\{(a_i,a_j) : l\le i<j\le r \wedge a_i>a_j\}|。

1≤n≤1051\le n\le 10^5,1≤m≤5×1051\le m\le 5\times 10^5。

输入格式

第一行一个正整数 nn。

第二行 nn 个正整数,其中第 ii 个数 aia_i 表示序列第 ii 个位置的值,保证 1≤ai≤n1\leq a_i \leq n。

第三行一个正整数 mm。

之后 mm 行,每行用两个空格隔开的正整数,分别表示 l,rl,r,表示一次询问,保证 1≤l≤r≤n1\leq l\le r \leq n。

输出格式

输出 mm 行,第 ii 行输出一行一个整数,表示第 ii 次询问的答案。

5
2 1 3 2 1
4
2 4
1 5
3 5
2 2

1
3
3
0