我用的线段树写的。

num数组表示已插入的数值的个数。

由于a[i]数值很大，但是n不是很大，所以要离散化处理

9 1 0 5 4

离散化后

4 1 0 3 2

这样保证最大值不会超过n

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define lson l, m, rt<<1#define rson m+1, r, rt<<1|1using namespace std;typedef long long ll;const int MAXN = 543210;int a[MAXN], mp[MAXN], num[MAXN<<2];void push_up(int rt){    num[rt] = num[rt<<1] + num[rt<<1|1];}void update(int p, int l, int r, int rt){    if(l == r)    {        num[rt]++;        return;    }    int m = (l + r) >> 1;    if(p <= m) update(p, lson);    else update(p, rson);    push_up(rt);}int query(int L, int R, int l, int r, int rt){    if(L <= l && r <= R) return num[rt];    int m = (l + r) >> 1;    int ret = 0;    if(L <= m) ret += query(L, R, lson);    if(R > m) ret += query(L, R, rson);    return ret;}bool cmp(int A, int B){    return a[A] < a[B];}int main(){//    freopen("in.txt", "r" ,stdin);    int n;    while(~scanf("%d", &n) && n)    {        for(int i=0; i