Atcoder.abc127_f Absolute Minima

1.Problem
https://atcoder.jp/contests/abc127/submissions/5607909

2.Idea
Using BIT to find and calc the median value.
Credit

3.Source

 const int N = 200005;  
 //////////////////////////////  
 template<typename T>  
 struct BIT {  
      int n;  
      vector<T> dat;  
      BIT(int n = 0) {  
           initialize(n);  
      }  
      void initialize(int nin) {  
           n = nin;  
           dat.resize(n);  
           for (int i = 0; i<n; i++) dat[i] = 0;  
      }  
      T sum(int i) {  
           T s = 0;  
           while (i >= 0) {  
                s += dat[i];  
                i = (i & (i + 1)) - 1;  
           }  
           return s;  
      }  
      T sum_between(int i, int j) {  
           if (i > j) return 0;  
           return sum(j) - sum(i - 1);  
      }  
      void plus(int i, T x) {  
           while (i < n) {  
                dat[i] += x;  
                i |= i + 1;  
           }  
      }  
      // a[0]+...+a[ret] >= x  
      int lower_bound(T x) {  
           int ret = -1;  
           int k = 1;  
           while (2 * k <= n) k <<= 1;  
           for (; k>0; k >>= 1) {  
                if (ret + k < n && dat[ret + k] < x) {  
                     x -= dat[ret + k];  
                     ret += k;  
                }  
           }  
           return ret + 1;  
      }  
 };  
 Int T[N], A[N], B[N];  
 void solve()  
 {  
      int q;  
      cin >> q;  
      vector<int> as;  
      REP(i, q) {  
           cin >> T[i];  
           if (T[i] == 1) {  
                cin >> A[i] >> B[i];  
                as.push_back(A[i]);  
           }  
      }  
      sort(as.begin(), as.end());  
      as.erase(unique(as.begin(), as.end()), as.end());  
      map<int, int> mp;  
      int sz = as.size();  
      REP(i, sz) mp[as[i]] = i;  
      BIT<Int> bitnum(sz);  
      BIT<Int> bitsum(sz);  
      Int fix = 0;  
      int all = 0;  
      REP(i, q) {  
           if (T[i] == 1) {  
                int a = mp[A[i]];  
                bitsum.plus(a, A[i]);  
                bitnum.plus(a, 1);  
                fix += B[i];  
                all++;  
           }  
           else {  
                Int ans = fix;  
                int idx = bitnum.lower_bound((all + 1) / 2);  
                ans += bitsum.sum_between(idx + 1, sz - 1);  
                ans -= as[idx] * bitnum.sum_between(idx + 1, sz - 1);  
                ans -= bitsum.sum_between(0, idx - 1);  
                ans += as[idx] * bitnum.sum_between(0, idx - 1);  
                cout << as[idx] << " " << ans << endl;  
           }  
      }  
 }