原文链接https://www.cnblogs.com/zhouzhendong/p/BZOJ3289.html
给定一个序列 $a$ , 有 $n$ 个元素。
给定 $m$ 次询问，每次问一个区间内，只通过交换相邻元素，问至少交换多少次才能使得区间升序。
$n,m\leq 50000$ ， $a_i$ 需要离散化
一道不动脑子的题目。
就是询问区间逆序对数。
莫队裸题 + 树状数组。（差点忘了还有树状数组）
wa 了一波。25分钟搞定。30分钟博客也搞定了。
（我一般只有写裸题题解的时候才这么随意……）
#include <bits/stdc++.h>
using namespace std;
const int N=50005;
int n,m,hs=1,a[N],Ha[N];
int c[N];
void HASH(){
sort(Ha+1,Ha+n+1);
for (int i=2;i<=n;i++)
if (Ha[i]!=Ha[i-1])
Ha[++hs]=Ha[i];
}
struct Query{
int L,R,id,ans;
}q[N];
bool cmp(Query a,Query b){
int La=a.L>>9,Lb=b.L>>9;
if (La!=Lb)
return La<Lb;
return a.R<b.R;
}
void add(int x,int d){
for (;x<=hs;x+=x&-x)
c[x]+=d;
}
int sum(int x){
int ans=0;
for (;x>0;x-=x&-x)
ans+=c[x];
return ans;
}
bool cmpid(Query a,Query b){
return a.id<b.id;
}
int main(){
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]),Ha[i]=a[i];
HASH();
for (int i=1;i<=n;i++)
a[i]=lower_bound(Ha+1,Ha+hs+1,a[i])-Ha;
scanf("%d",&m);
for (int i=1;i<=m;i++)
scanf("%d%d",&q[i].L,&q[i].R),q[i].id=i;
sort(q+1,q+m+1,cmp);
int L=1,R=0,ans=0;
memset(c,0,sizeof c);
for (int i=1;i<=m;i++){
while (R<q[i].R)
ans+=sum(hs)-sum(a[++R]),add(a[R],1);
while (L>q[i].L)
ans+=sum(a[--L]-1),add(a[L],1);
while (L<q[i].L)
add(a[L],-1),ans-=sum(a[L++]-1);
while (R>q[i].R)
add(a[R],-1),ans-=sum(hs)-sum(a[R--]);
q[i].ans=ans;
}
sort(q+1,q+m+1,cmpid);
for (int i=1;i<=m;i++)
printf("%d\n",q[i].ans);
return 0;
}
原文：https://www.cnblogs.com/zhouzhendong/p/BZOJ3289.html