BZOJ3289 - Click Here
Description
Mato同学从各路神犇以各种方式（你们懂的）收集了许多资料，这些资料一共有n份，每份有一个大小和一个编号。为了防止他人偷拷，这些资料都是加密过的，只能用Mato自己写的程序才能访问。Mato每天随机选一个区间[l,r]，他今天就看编号在此区间内的这些资料。Mato有一个习惯，他总是从文件大小从小到大看资料。他先把要看的文件按编号顺序依次拷贝出来，再用他写的排序程序给文件大小排序。排序程序可以在1单位时间内交换2个相邻的文件（因为加密需要，不能随机访问）。Mato想要使文件交换次数最小，你能告诉他每天需要交换多少次吗？
Input
第一行一个正整数n，表示Mato的资料份数。
第二行由空格隔开的n个正整数，第i个表示编号为i的资料的大小。
第三行一个正整数q，表示Mato会看几天资料。
之后q行每行两个正整数l、r，表示Mato这天看[l,r]区间的文件。
n,q <= 50000
Output
q行，每行一个正整数，表示Mato这天需要交换的次数。
Solutions
题目本质上是询问区间逆序对数。
考虑到如果用树状数组维护了区间[L,R]内的数值的前缀和，就能在$\log a$时间内转移到曼哈顿距离为1的区间。因此直接跑莫队算法可以得到$O(N \sqrt N \log N)$做法，此处重点讲下$O(N \sqrt N)$做法。
在开始之前，先定义一些表示方法。用$A,B,C$表示一个序列，用$c(A)$表示$A$序列所产生的逆序对数，用$A+B$表示$A$序列与$B$序列的合并。
现对序列分块。对于每个询问，能够将该询问划分成两个非完整块与一个完整的块。若定义这些块序列从左到右分别为$A,B,C$，那么询问的答案实质上是$c(A+B+C)$。转换下得到答案为$c(A)+c(B)+c(C)+c(A+B)+c(A+C)+c(B+C)$。
因为答案是需要求出$c(A),c(B),c(C)$的，因此对于$c(A+B),c(A+C),c(B+C)$而言，只需要得知两个序列合并时增加的逆序对数。
现考虑下每个部分要如何求。
$c(A+B),c(B+C)$：由于非完整块的大小受到限制，因此求出在任意块区间内的数值的前缀和即可。
$c(A+C)$：如果两个序列分别有序的话，则能在线性时间内归并求得逆序对数，因此只需要提前对每个块排序即可。
$c(A),c(C)$：由于是非完整块，因此能够保证有一个区间端点是固定的。基于这一点，只需要预处理出每个位置到块首/块尾的逆序对数即可。
$c(B)$：需要处理出任意块区间的逆序对数。用处理$c(A+B)$的方法处理转移，则能够保证时间复杂度。
至此所有部分就处理完了。通过简单分析得知，块大小为$\sqrt N$时最优，此时时间复杂度为$O(N \sqrt N)$。
P.S. 由于$O(N \sqrt N)$做法常数极大，因此实测与莫队算法效率差不多…
CODE
CODE(莫队算法) - Click Here
CODE($N \sqrt N$分块做法) - Click Here