CFR 806 E. Blog Post Rating ( Segment Tree, Fenwick Tree )

Problem - E - Codeforces
りんごさんの提出見て回答。

題意：
有 N 個人，編號 1 到 N 要投票。投票可以使得當前的票數 +1 / +0 / -1 其中一個。每個人心目中都有一個期望票數，輪到他的時候他會依據當前的票數，操作使得接近他的期望票數。求對於所有 x，編號 [ 1, x ] 的人任意排序並投票後，最大可能的票數。初始時的票數為 0。

制約：
The first line contains a single integer n (1 ≤ n ≤ 5e5) — the number of Codeforces users.
The second line contains n integers a1, a2, ..., an ( - 5e5 ≤ ai ≤ 5e5) — estimated blog post ratings for users in order from 1 to n.

解法：
考慮在線處理，由 x = 1 至 x = N。
如果要暴力做，顯然是由小到大排序。先排大的再排小的一定不會比較好。
基於這點，我們可以二分搜尋 -1 會發生幾次，確切的說，所有 -1 結束之後會在什麼位置。
這部分用樹狀數組就能搞定，一個人加入時，在樹狀數組上對應的下標 +1，二分搜尋的時候，範圍是 [ -MAXA, 0 ]，判斷的是一個期望票值以前的人數是否為該票值和 0 的距離。找到一個滿足這個條件的最左下標，那麼該下標以右的人都不是扣分的。
雖然知道不扣分，但不知道是不做事還是加分，所以不是到這裡就結束。
會不做事的原因是塞車，換句話說有太多人跟他投的是一樣的票，卻早就已經達到這個票數。
結論是，維護一棵 min 線段樹，初始時一個下標保有的值是下標本身的數值。每有一個期望票數 x 的人加入，就對 [ -MAXA, x ) 進行區間加一。
可以發現，答案是線段樹上的 min( [ 二分搜的下標, MAXA ] )。
在實作上，將 [ - MAXA, MAXA ] 映射到 [ 0, MAXA * 2 ]。

時間 / 空間複雜度：
O( N lg A ) / O( N )

#include <bits/stdc++.h>
using namespace std;

const int MAXN = int( 5e5 );
const int MAXA = int( 5e5 ); // abs

int N;
int A[ MAXN ];

int ftree[ MAXA * 2 + 1 + 1 ];
void add( int x, int v ) {
  for( int i = x; i < MAXA * 2 + 1 + 1; i += i & -i ) {
    ftree[ i ] += v;
  }
}
int sum( int x ) {
  int res = 0;
  for( int i = x; i; i -= i & -i ) {
    res += ftree[ i ];
  }
  return res;
}

struct segt {
  int minv[ MAXA * 2 + 1 << 2 ];
  int tag[ MAXA * 2 + 1 << 2 ];
  void push( int t ) {
    minv[ t << 1 ] += tag[ t ];
    tag[ t << 1 ] += tag[ t ];
    minv[ t << 1 | 1 ] += tag[ t ];
    tag[ t << 1 | 1 ] += tag[ t ];
    tag[ t ] = 0;
  }
  void pull( int t ) {
    minv[ t ] = min( minv[ t << 1 ], minv[ t << 1 | 1 ] );
  }
  void add( int ql, int qr, int v, int lb = 0, int rb = MAXA * 2 + 1, int t = 1 ) {
    if( qr <= lb or rb <= ql ) return;
    if( ql <= lb and rb <= qr ) {
      minv[ t ] += v;
      tag[ t ] += v;
      return;
    }
    push( t );
    int mid = lb + rb >> 1;
    add( ql, qr, v, lb, mid, t << 1 );
    add( ql, qr, v, mid, rb, t << 1 | 1 );
    pull( t );
  }
  int qmin( int ql, int qr, int lb = 0, int rb = MAXA * 2 + 1, int t = 1 ) {
    if( qr <= lb or rb <= ql ) return 0x3f3f3f3f;
    if( ql <= lb and rb <= qr ) return minv[ t ];
    push( t );
    int mid = lb + rb >> 1;
    int res = min( qmin( ql, qr, lb, mid, t << 1 ), qmin( ql, qr, mid, rb, t << 1 | 1 ) );
    pull( t );
    return res;
  }
} root;

signed main() {
  ios::sync_with_stdio( 0 );
  cin >> N;
  for( int i = 0; i < N; ++i ) {
    cin >> A[ i ];
    A[ i ] += MAXA; // [ - MAXA, MAXA ] -> [ 0, MAXA * 2 ]
  }
  for( int i = 0; i <= MAXA * 2; ++i ) {
    root.add( i, i + 1, i );
  }
  for( int i = 0; i < N; ++i ) {
    add( A[ i ] + 1, 1 ); // -> [ 1, MAXA * 2 + 1 ]
    root.add( 0, A[ i ], 1 );
    int lb = 0, ub = MAXA;
    int x = MAXA;
    while( lb <= ub ) {
      int mid = lb + ub >> 1;
      if( sum( mid + 1 ) >= MAXA - mid ) {
        x = mid;
        ub = mid - 1;
      } else {
        lb = mid + 1;
      }
    }
    cout << root.qmin( x, MAXA * 2 + 1 ) - MAXA << "\n";
  }
  return 0;
}