<span>HDU5775 Bubble Sort（树状数组求逆序数）</span>
题意：
给你一段序列（排列）和排序方式
让你求出每个数在排序过程中移动的范围
思路：
序列排序结束是升序的，能移动到的最左端就是min(i,a[i])
如果a[i]比较大，他就不会向左移，就是a[i]，如果比较小就最多移动到i的位置
能移动到的最右端就是当前的i加上从右向左比他小的数的个数
因为这些数要优先移动到他的左端，
这个个数可以用树状数组求
/* *********************************************** Author :devil ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <stdlib.h> using namespace std; typedef long long LL; const int inf=0x3f3f3f3f; const int mod=1e9+7; const int N=1e5+10; int a[N],c[N],l[N],r[N],n; int lowbit(int x) { return x&(-x); } void update(int x,int num) { while(x<=n) { c[x]+=num; x+=lowbit(x); } } int getsum(int x) { int s=0; while(x>0) { s+=c[x]; x-=lowbit(x); } return s; } int main() { //freopen("in.txt","r",stdin); int t,cas=0; scanf("%d",&t); while(t--) { printf("Case #%d:",++cas); scanf("%d",&n); memset(c,0,sizeof(c)); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=n;i>=1;i--) { l[a[i]]=min(a[i],i); r[a[i]]=i+getsum(a[i]); update(a[i],1); } for(int i=1;i<=n;i++) printf(" %d",r[i]-l[i]); printf("\n"); } return 0; }
