POI 18 Stage 3 Meteors ( Parallel Binary Search, Fenwick Tree )

http://main.edu.pl/en/archive/oi/18/met

題意：
有 M 個環狀的地，每個地屬於一個人。有 K 次隕石事件，每次會在某一連續區間 [ L[ i ], R[ i ] ] 每個地分別降下有 W[ i ] 單位的隕石。有 N 個人，每個人有最少需要收集的隕石量 P[ i ]。要求分別輸出每個人在第幾次隕石事件會達到目標，或是不可達成。

資料規模：
N, M, K ≤ 3e5
MAXP, MAXA ≤ 1e9
TL: 10000 ms
ML: 64 MB

解法：
很直觀的做法是開一個持久化線段樹，維護每一次操作後的隕石狀態，這麼一來可以對所有人分別對答案做二分搜，檢查只需要 O( lg M ) 時間，因此時間複雜度會是 O( ( N + M ) * lg M * lg K )，但空間複雜度會是 O( ( M + K ) lg M )，超過限制。
考慮離線算法，做整體二分。每層重新在資料結構上更新該層左半的貢獻，就能在和一個人的土地數量乘上 lg M 的複雜度內判斷一個人的答案在左半，或是右半，達到二分的效果。注意任一層都只有 N 人，擁有的總土地數量是 M。由於已到右半的所有人，左半的貢獻是確定發生的，所以在往右分之前就可以先分別減去，如此一來就能在遞迴前將左半的貢獻清空，每次就可以以乾淨的資料結構開始。
實作上要注意的是，這個資料結構雖然用線段樹是最直觀合理的，但會因為過慢只能拿到 50 分。
這裡有一個技巧，就是 Fenwick Tree 可以做到 O( lg M ) 的區間修改和單點詢問，具體做法是，和平常直接儲存元素不同，而是儲存該元素和前一元素的差。在所有差分之前補 0，顯然長度為 k 的前綴和就是第 k 個元素的值。

時間 / 空間複雜度：
O( ( N + M ) * lg K * lg M ) / O( N + M )

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

const int MAXN = ( int ) 3e5;
const int MAXM = ( int ) 3e5;
const int MAXK = ( int ) 3e5;

int N, M;
int O[ MAXM ]; // owner of field
vector< int > rO[ MAXN ]; // owner to field
int P[ MAXN ]; // goal
int K;
int L[ MAXK ], R[ MAXK ], W[ MAXK ]; // [ L, R ], might be cirucular

int ans[ MAXN ];

struct Fenwick_Tree{
  long long sum[ MAXM + 10 ]; // sum[ 1 ] = A[ 0 ], sum[ 1 ] + sum[ 2 ] = A[ 1 ]
  void add( int ql, int qr, int v ){ // [ ql, qr ) - 0 base
    ++ql, ++qr;
    for( int i = ql; i < M + 5; i += i & -i ){
      sum[ i ] += v;
    }
    for( int i = qr; i < M + 5; i += i & -i ){
      sum[ i ] -= v;
    }
  }
  long long gs( int x ){ // A[ x ] = S[ 1, x + 1 ]
    ++x;
    long long res = 0LL;
    for( int i = x; i; i -= i & -i ){
      res += sum[ i ];
    }
    return res;
  }
} ftree;

void parallel_bs( int lb, int rb, vector< int > &nation ){
  if( lb + 1 == rb ){
    for( int i = 0; i < nation.size(); ++i ){
      int owner = nation[ i ];
      for( int j = 0; j < rO[ owner ].size(); ++j ){
        if( L[ lb ] <= R[ lb ] ){
          if( L[ lb ] <= rO[ owner ][ j ] and rO[ owner ][ j ] <= R[ lb ] ){
            P[ owner ] -= W[ lb ];
          }
        } else{
          if( rO[ owner ][ j ] <= R[ lb ] or L[ lb ] <= rO[ owner ][ j ] ){
            P[ owner ] -= W[ lb ];
          }
        }
        if( P[ owner ] <= 0 ) break;
      }
      if( P[ owner ] <= 0 ){
        ans[ owner ] = rb;
      } else{
        ans[ owner ] = -1;
      }
    }
    return;
  }
  int mid = lb + rb >> 1;
  { // update contribution of [ lb, mid ) to ftree
    for( int i = lb; i < mid; ++i ){
      if( L[ i ] <= R[ i ] ){
        ftree.add( L[ i ], R[ i ] + 1, W[ i ] );
      } else{
        ftree.add( 0, R[ i ] + 1, W[ i ] );
        ftree.add( L[ i ], M, W[ i ] );
      }
    }
  }
  vector< int > ll, rr;
  { // split nation
    static long long taken[ MAXN ];
    for( int i = 0; i < nation.size(); ++i ){
      int owner = nation[ i ];
      taken[ owner ] = 0LL;
      for( int j = 0; j < rO[ owner ].size(); ++j ){
        int field = rO[ owner ][ j ];
        taken[ owner ] += ftree.gs( field );
        if( taken[ owner ] >= P[ owner ] ) break;
      }
      if( taken[ owner ] >= P[ owner ] ){
        ll.push_back( owner );
      } else{
        P[ owner ] -= taken[ owner ]; // cancel contribution of [ lb, mid ) from P
        rr.push_back( owner );
      }
    }
  }
  { // cancel contribution of [ lb, mid ) from ftree
    for( int i = lb; i < mid; ++i ){
      if( L[ i ] <= R[ i ] ){
        ftree.add( L[ i ], R[ i ] + 1, - W[ i ] );
      } else{
        ftree.add( 0, R[ i ] + 1, - W[ i ] );
        ftree.add( L[ i ], M, - W[ i ] );
      }
    }
  }
  parallel_bs( lb, mid, ll );
  parallel_bs( mid, rb, rr );
}

signed main(){
  ios::sync_with_stdio( 0 );
  {
    cin >> N >> M;
    for( int i = 0; i < M; ++i ){
      cin >> O[ i ]; --O[ i ];
      rO[ O[ i ] ].push_back( i );
    }
    for( int i = 0; i < N; ++i ){
      cin >> P[ i ];
    }
    cin >> K;
    for( int i = 0; i < K; ++i ){
      cin >> L[ i ] >> R[ i ] >> W[ i ];
      --L[ i ], --R[ i ];
    }
  }
  {
    vector< int > nation( N );
    for( int i = 0; i < N; ++i ){
      nation[ i ] = i;
    }
    parallel_bs( 0, K, nation );
  }
  {
    for( int i = 0; i < N; ++i ){
      if( ans[ i ] == -1 ){
        cout << "NIE\n";
      } else{
        cout << ans[ i ] << "\n";
      }
    }
  }
  return 0;
}