1785C - Monsters (hard version) - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
 
#define _ << ' ' <<
#define pb push_back
#define eb emplace_back
#define all(x) begin(x), end(x)
#define mp make_pair
#define f first
#define s second
#define sz(x) int((x).size())
#define each(x,A) for(auto &x: A)
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
 
using ll = long long;
using db = long double;
using pl = pair<ll,ll>;
using pi = pair<int,int>;
//using cd = complex<db>;
using vi = vector<int>;
using vd = vector<db>;
using vl = vector <ll>;
using str = string;
template<class T> using V = vector<T>; 
 
//const int MOD = 1e9+7;
 
template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template<typename T, size_t size> ostream& operator<<(ostream &os, const array<T, size> &arr) { os << '{'; string sep; for (const auto &x : arr) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
 
mt19937_64 mt_rand(chrono::high_resolution_clock::now().time_since_epoch().count());
uniform_int_distribution<long long> rg(1,1e18);

struct item {
    ll key, prior;
    ll n, v;
    ll mnv;
    ll sum;
    ll ex;
    item * l, * r;
    item(): sum(0), n(0){}
    item (ll key, ll v) : key(key), prior(rg(mt_rand)), sum(1ll*key), n(1), ex(0), v(v), mnv(v), l(NULL), r(NULL) { }
};
typedef item * pitem;

void push(pitem p){
  if(!p) return;
  p->mnv+=p->ex;
  p->v+=p->ex;
  p->sum += (p->n)*(p->ex);
  if(p->l) p->l->ex += p->ex;
  if(p->r) p->r->ex += p->ex;
  p->ex = 0;
}

ll takesum(pitem p){
  if(!p) return 0;
  push(p);
  return p->sum;
}

ll taken(pitem p){
  if(!p) return 0;
  push(p);
  return p->n;
}

ll takemnv(pitem p){
  if(!p) return 1e9;
  push(p);
  return p->mnv;
}


void att(pitem p){
  if(!p) return;
  push(p);
  p->n = 1 + taken(p->l) + taken(p->r);
  p->sum = p->v + takesum(p->l) + takesum(p->r);
  p->mnv = min(p->v, takemnv(p->l));
  p->mnv = min(p->mnv, takemnv(p->r));
}


void add(pitem p, ll v){
  if(!p) return;
  p->ex += v;
  push(p);
}

void split (pitem t, int key, pitem & l, pitem & r){
    push(t);
    if (!t)
        l = r = NULL;
    else if (key < t->key){
      split (t->l, key, l, t->l);
      r = t;
      att(l); att(r);
    }
    else{
      split (t->r, key, t->r, r);
      l = t;
      att(l); att(r);
    }
}

void split2(pitem t, pitem &l, pitem &r){
  push(t);
  if(!t){
    l = r = nullptr;
    return;
  }
  if(!takemnv(t->l)){
    split2(t->l, l, t->l);
    r = t;
    att(l); att(r);
    return;
  }
  if(!(t->v)){
    l = t->l;
    t->l = nullptr;
    r = t;
    att(l); att(r);
    return;
  }
  split2(t->r, t->r, r);
  l = t;
  att(l); att(r);

}

void insert (pitem & t, pitem it) {
    push(t);
    if (!t){
      t = it;
    }
    else if (it->prior > t->prior)
        split (t, it->key, it->l, it->r),  t = it;
    else{
        insert (it->key < t->key ? t->l : t->r, it);
    }
    att(t);
}

void merge (pitem & t, pitem l, pitem r) {
    push(l); push(r);
    if (!l || !r)
        t = l ? l : r;
    else if (l->prior > r->prior)
        merge (l->r, l->r, r),  t = l;
    else
        merge (r->l, l, r->l),  t = r;
    att(t);
}


void print(pitem T){
  if(!T) return;
  push(T);
  if(T->l) print(T->l);
  cout << '{' << T->v <<',' << T->key << '}' << ' ';
  if(T->r) print(T->r);
}

ll maxv(pitem T){
  if(!T) return 0;
  push(T);
  if(T->r) return maxv(T->r);
  return T->key - T->v;
}

void rmv(pitem &T){
  if(!T) return;
  pitem L,R;
  split2(T,L,R);
  add(L,-1);
  merge(T,L,R);
}

void solve(){
  int n; cin >> n;
  vi a(n); each(x,a) cin >> x;
  pitem T = nullptr;

  for(int i=0; i<n; i++){
    pitem L,R;
    split(T,a[i]-1,L,R);
    ll nv = maxv(L);
    pitem E = new item(a[i], a[i]-nv-1);
    rmv(R);
    merge(L,L,E);
    merge(T,L,R);
    cout << takesum(T) << ' ';
  }
  cout << endl;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t;
  cin >> t;
  while(t--) solve();
}