Mato的文件管理
两两交换最小次数即为逆序数之和，没有告诉数据范围，就排序离散化对应。
l变化时，区间左边元素，求和减去本身1为逆序数。 即本来有 sum(x) - 1个元素在我后面，现在我在第一个。
r变化时，区间右边元素，区间长度减去 前缀和。即本来我在 n - sum(x) 个元素 前面，现在我在最后一个
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
const int maxn = 500005;
struct node{int l,r,id;int ans;}q[maxn];
int s[maxn],Be[maxn];
int z[maxn],ni[maxn];
int unit,n,m,l=1,r;
int ans;
int lowbit(int x){
return x&(-x);
}
int find(int x){
int as = 0;
while(x>0){
as =z[x];
x-=lowbit(x);
}
return as;
}
int add(int x,int d){
while(x<=maxn){
z[x] =d;
x =lowbit(x);
}
}
int cmp(node a,node b){
return Be[a.l]==Be[b.l]?a.r<b.r:Be[a.l]<Be[b.l];
}
int cmp2(node a,node b){
return a.id<b.id;
}
int main()
{
scanf("%d",&n); unit = sqrt(n);
for(int i=1;i<=n;i ) scanf("%d",&s[i]),ni[i]=s[i],Be[i] = i/unit 1;
sort(ni 1,ni 1 n);
for(int i=1;i<=n;i ) s[i] = lower_bound(ni 1,ni 1 n,s[i]) - (ni);
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 1 m,cmp);
for(int i=1;i<=m;i ){
while(l<q[i].l)l ,add(s[l-1],-1),ans-=find(s[l-1]-1);
while(l>q[i].l)l--,add(s[l],1),ans =find(s[l]-1);
while(r<q[i].r)r ,add(s[r],1),ans =r-l 1-find(s[r]);
while(r>q[i].r)r--,add(s[r 1],-1),ans-=r-l 1-find(s[r 1]);
q[i].ans = ans;
}
sort(q 1,q 1 m,cmp2);
for(int i=1;i<=m;i ){
printf("%dn",q[i].ans);
}
return 0;
}
/*
6
1 4 7 5 6 3
4
1 4
2 5
4 5
4 6
*/
