做题网站推荐: OpenJudge VIJOS UOJ CF JOYOI CODEVS 洛谷 RQNOJ BZOJ POJ HDU

本站题目推荐: 高精度 模拟 排序 递推 贪心 递归 搜索 动态规划 数学 图论 数据结构 实名认证 卡评测举报

输入输出 变量类型 顺序结构 选择结构 循环结构 一维数组 NOIP 资源下载


问题 2513. -- 蒜头君的排序

2513: 蒜头君的排序

时间限制: 2 Sec  内存限制: 256 MB
提交: 7  解决: 0
[上一题][提交][讨论版][状态][下一题]

题目描述

蒜头君是一个爱思考的好孩子,这一天他学习了冒泡排序,于是他就想,把一个乱序排列通过冒泡排序排至升序需要多少次交换,这当然难不倒他,于是他想来点刺激的,给定一个 1n1 \ldots n1n 的排列,每次从该排列中选择一个区间 [l,r][l,r][l,r],问使用冒泡排序将该区间排至升序需要多少次交换操作。

输入

第一行一个整数 nnn,表示排列长度。

接下来一行 nnn 个整数,表示该排列。

接下来一行一个整数 mmm,表示询问次数。

接下来 mmm 行,每行 222 个整数 l,rl,rl,r,表示询问 [l,r][l,r][l,r] 区间。

输出

输出 mmm 行,每行 111 个整数,第 iii 行表示第 iii 个询问的答案。

样例输入

10
9 8 7 4 5 6 10 3 2 1
5
2 4
8 10
2 8
5 9
4 9

样例输出

3
3
13
7
9

提示

对于 303030% 的数据,满足 1n,m3001 \le n,m \le 3001n,m300

对于 606060% 的数据,满足 1n,m10001 \le n,m \le 10001n,m1000

对于 100100100% 的数据,满足 1n,m30000,1 \le n,m \le 30000,1n,m30000, l<r,l<r,l<r, l[i]l[i1] +\sum | l[i]-l[i-1] |\ +l[i]l[i1] + r[i]r[i1]\sum | r[i]-r[i-1] | \ler[i]r[i1] 7×1067 \times 10^6 7×106

标签

[上一题][提交][讨论版][状态][下一题]