线段树记录区间[a,b]里面出现了多少个数字，查询时只要查询区间[x,n-1]有多少个数出现过，就知道前面有多少个数比x大，也就知道x有多少逆序数。

把一个序列最前面的数字x移到最后就会产生n-1-x-x个逆序：

x在最前时它后面有x个数(0到x-1)比x小，所以把x移到最后以后逆序数要减x个;

x在最前时它后面有n-1-x个数(x+1到n-1)比x大，所以把x移到最后以后逆序数增加n-1-x个;

所以，最前面的数字x移到最后就会新产生n-2*x-1个逆序

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define lson l,mid,i<<1 5 #define rson mid+1,r,i<<1|1 6 using namespace std; 7 int n; 8 int sum[5010*3]; 9 int query(int ql,int qr=n-1,int l=0,int r=n-1,int i=1)10 {11     if(ql<=l&&r<=qr) return sum[i];12     int ret=0,mid;13     mid=(l+r)>>1;14     if(ql <= mid) ret+=query(ql,qr,lson);15     if(qr > mid) ret+=query(ql,qr,rson);16     return ret;17 }18 void update(int ql,int l=0,int r=n-1,int i=1)19 {20     if(l==r) {sum[i]++;return;}21     int mid=(l+r)>>1;22     if(ql<=mid) update(ql,lson);23     else update(ql,rson);24     sum[i]=sum[i<<1]+sum[i<<1|1];25 }26 int x[5000];27 int main()28 {29     while(cin>>n)30     {31         int ret=0;32         memset(sum,0,sizeof(sum));//这里相当于建树33         for(int i=0;i