Warning: input could be > 10000...

Solution by segment tree:

struct Node{    Node(int s, int e) : start(s), end(e), cnt(0), left(nullptr), right(nullptr)    {};    int start;    int end;    int cnt;    //    Node *left;    Node *right;};class Solution {    Node *pRoot;    void update(int v)    {        Node *p = pRoot;        while(p)        {            p->cnt ++;            if(p->start == p->end) break;            int mid = (p->start + p->end) / 2;            if(v <= mid)            {                if(!p->left)                {                    p->left = new Node(p->start, mid);                }                p = p->left;            }            else            {                if(!p->right)                {                    p->right = new Node(mid + 1, p->end);                }                p = p->right;            }        }    }    int query(Node *p, int v)    {        if(!p) return 0;        int mid = (p->start + p->end) / 2;        if(v < mid)        {            return query(p->left, v);        }        else if(v == mid)        {            return p->left ? p->left->cnt : 0;        }        // v > mid        return (p->left ? p->left->cnt : 0) + query(p->right, v);    }public:   /**     * @param A: An integer array     * @return: Count the number of element before this element 'ai' is     *          smaller than it and return count number array     */    vector
      
        countOfSmallerNumberII(vector
       
         &A) {        pRoot = new Node(0, 20000);        vector
        
          ret;        for(auto v : A)        {            ret.push_back(query(pRoot, v - 1));            update(v);        }        return ret;    }};