?

題目描述

輸入一個(gè)正整數(shù)n，隨后給出一個(gè)長度為n的整數(shù)序列 a[0],a[1],a[2],...,a[n-1] ，再給定多組數(shù)組下標(biāo)范圍，求給定序列的逆序數(shù)。

輸入

多組測試數(shù)據(jù)(不超過10組)，以EOF結(jié)尾。

每組測試數(shù)據(jù)第一行為數(shù)組長度n，正整數(shù)，代表數(shù)組長度，數(shù)據(jù)范圍為0<n<=10000

第二行為n個(gè)整數(shù)，為數(shù)組an，保證數(shù)組中每個(gè)數(shù)在int范圍內(nèi)。

第三行為一個(gè)整數(shù)t，代表t次查詢，0<t<=1000

接下來t行，每行兩個(gè)數(shù)x，y，代表數(shù)組下標(biāo)區(qū)間，保證0<=x<=y<=n-1

輸出

對于每次查詢，輸出一行，每行一個(gè)數(shù)，代表所求逆序數(shù)。

具體參見樣例。

輸入樣例

輸出樣例

提示

使用時(shí)間復(fù)雜度為O(n2)O(n2) 的算法會超時(shí)。

聯(lián)系下歸并排序~

思路

轉(zhuǎn)載于:https://www.cnblogs.com/zjsyzmx0527/p/10182621.html

總結(jié)

以上是生活随笔為你收集整理的A1-2017级算法上机第一次练习赛 H 模式寻对的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。