#P6554. [Ynoi2019 模拟赛] Yuno loves sqrt technology II

    ID: 6038 传统题 1000ms 256MiB 尝试: 2 已通过: 2 难度: 9 上传者: 标签>CF2600省选/NOI-普通莫队离线查询根号分块整块懒标记树状数组离散化差分转化

[Ynoi2019 模拟赛] Yuno loves sqrt technology II

题目描述

给你一个长为 nn 的序列 aa,mm 次询问,每次查询一个区间的逆序对数。

输入格式

第一行两个整数 n,mn,m。

第二行 nn 个整数表示这个序列。

之后 mm 行,每行两个整数表示查询的区间。

输出格式

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

样例 #1

样例输入 #1

4 1
1 4 2 3
2 4

样例输出 #1

2

提示

1≤n,m≤1051\leq n,m \leq 10^5,0≤ai≤1090 \leq a_i \leq 10^9。

我们已经有了低于 n1.5n^{1.5} 的算法。

Source By nzhtl1477