14241: 【原4241】区间逆序对
题目
题目描述
author: Online Judge 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4241
Description
给定一个排列\( a_1, a_2, ..., a_n\)和一个非负整数\(K\)。
有\(m\)次询问，每次询问给定一个区间\([l, r]\),求这个区间内逆序对个数恰好为\(K\)的子区间的个数。
Input Format
第一行一个整数T，代表数据组数。接下来的每组数据：
第一行输入三个整数\(n、m、K\)。
接下来一行有\(n\)个整数，表示\( a_1, a_2, ..., a_n\)，代表输入的排列。
接下来\(m\)行，每行两个整数\(l，r\)， 表示询问区间为\([l, r]\)。
Output Format
对于每个询问输出一行，表示区间内逆序对数恰好等于\(K\)的子区间个数。
Sample Input
1
6 4 1
3 1 5 4 2 6
2 4
2 3
3 4
1 5
Sample Output
2
0
1
5
Limit
对于 \(30\%\) 的数据，\(n,m \leq 400\)
对于 \(60\%\) 的数据，\(n,m \leq 2000\)
对于 \(100\%\) 的数据，\(1 \leq n,m \leq 200000, 1 \leq T \leq 5, 0 \leq K \leq \frac{n*(n+1)}{2}\)
时间限制1.5s, 内存限制128MB。
Hint
由于\(100\%\)数据输入量较大，建议使用 scanf 和 printf 进行输入输出，
或者只使用cin和cout,并使用以下代码关闭同步
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
注：不要使用endl，尽量使用\n，否则有极大概率TLE！
Oops! 本题目还没有解答！
助教老师们编题的速度，已经超过了解题的速度！
OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。
如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！