CFR 788 E. New task ( Segment Tree, Fenwick Tree )

Problem - 788E - Codeforces

題意：
給長度 N 的數列 A[]。
這個數列代表士兵們，他們的強度。初始時所有士兵都是活著的。一個隊伍是合法的，如果他有 5 個人，令下標為 a < b < c < d < e，那麼 b, c, d 必須是活的，並且滿足 A[ a ] ≤ A[ b ] = A[ c ] = A[ d ] ≥ A[ e ]。
有 M 筆詢問，分為兩種：
1 x：反轉 x 號士兵的狀態 ( 保證活 -> 死 )
2 x：反轉 x 號士兵的狀態 ( 保證死 -> 活 )
每次詢問完後，要輸出可行的隊伍數量，對 1e9 + 7 取模。

制約：
N, M ≤ 1e5
A[ i ] ≤ 1e9

解法：
先用樹狀數組預處理每個下標 i 作為 b 時，有多少 a，以及作為 d 時，有多少 e。
接著對每個不同的 A[ i ] 維護一顆動態開點的線段樹，用來維護對應的區間內活著的強度為 A[ i ] 的士兵數量。
( 不會 MLE，因為一個士兵至多只能造成 lg N 個新增節點 )
開一堆標記，pull 維護就能得到答案，具體見代碼。
l1 代表滿足的 ( a, b ) 數量，l2 代表滿足的 ( a, b, c ) 數量，r1, r2 同理。
用這幾個值，就可以計算出答案。

複雜度：
O( N lg N )

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

const int MOD = int( 1e9 ) + 7;

const int MAXN = 1 << 17;

int N;
int A[ MAXN ];
vector< int > da; // uniqued A
map< int, int > vcnt; // count of values
int rnk[ MAXN ]; // number of A[ i ] before i

int fngr[ MAXN + 1 ], fnls[ MAXN + 1 ];
int ngr[ MAXN ], nls[ MAXN ];

void fadd( int *ftree, int k, int v ) { // map to [ 1,
  for( int i = k; i <= da.size(); i += i & -i ) {
    ftree[ i ] += v;
  }
}

int fsum( int *ftree, int k ) {
  int res = 0;
  for( int i = k; i; i -= i & -i ) {
    res += ftree[ i ];
  }
  return res;
}

struct segt {
  int l1, l2, r1, r2, ans;
  int cnt; // count of active players
  segt *lc, *rc;
  segt() {
    lc = rc = NULL;
    cnt = 0;
  }
  void update( int lb, int rb, int k, int p ) {
    if( lb + 1 == rb ) {
      cnt ^= 1;
      l1 = cnt * ngr[ p ];
      r1 = cnt * nls[ p ];
      ans = l2 = r2 = 0;
      return;
    }
    int mid = lb + rb >> 1;
    if( k < mid ) {
      lc->update( lb, mid, k, p );
    } else {
      rc->update( mid, rb, k, p );
    }
    l1 = ( lc->l1 + rc->l1 ) % MOD;
    r1 = ( lc->r1 + rc->r1 ) % MOD;
    l2 = ( 1LL * lc->l1 * rc->cnt + lc->l2 + rc->l2 ) % MOD;
    r2 = ( 1LL * lc->cnt * rc->r1 + lc->r2 + rc->r2 ) % MOD;
    ans = ( 1LL * lc->l2 * rc->r1 + 1LL * lc->l1 * rc->r2 + lc->ans + rc->ans ) % MOD;
    cnt = lc->cnt + rc->cnt;
  }
} *root[ MAXN + 1 ]; // root by unique values of A

segt* build( int lb, int rb ) {
  segt *t = new segt();
  if( lb + 1 == rb ) return t;
  t->lc = build( lb, lb + rb >> 1 );
  t->rc = build( lb + rb >> 1, rb );
  return t;
}
signed main() {
  ios::sync_with_stdio( 0 );
  cin >> N;
  for( int i = 0; i < N; ++i ) {
    cin >> A[ i ];
  }
  { // discretize
    for( int i = 0; i < N; ++i ) {
      da.emplace_back( A[ i ] );
    }
    sort( da.begin(), da.end() );
    da.erase( unique( da.begin(), da.end() ), da.end() );
    map< int, int > mp;
    for( int i = 0; i < da.size(); ++i ) {
      mp[ da[ i ] ] = i + 1;
    }
    for( int i = 0; i < N; ++i ) {
      A[ i ] = mp[ A[ i ] ];
    }
    for( int i = 0; i < N; ++i ) {
      rnk[ i ] = vcnt[ A[ i ] ]++;
    }
  }
  for( int i = 0; i < N; ++i ) {
    ngr[ i ] = fsum( fngr, A[ i ] );
    fadd( fngr, A[ i ], 1 );
    nls[ N - 1 - i ] = fsum( fnls, A[ N - 1 - i ] );
    fadd( fnls, A[ N - 1 - i ], 1 );
  }
  for( int i = 0; i < N; ++i ) {
    if( root[ A[ i ] ] == NULL ) root[ A[ i ] ] = build( 0, vcnt[ A[ i ] ] );
    root[ A[ i ] ]->update( 0, vcnt[ A[ i ] ], rnk[ i ], i );
  }
  int ans = 0;
  for( int i = 1; i <= da.size(); ++i ) {
    ( ans += root[ i ]->ans ) %= MOD;
  }
  int M;
  cin >> M;
  for( int qi = 0; qi < M; ++qi ) {
    int t, x;
    cin >> t >> x;
    --x;
    ( ans -= root[ A[ x ] ]->ans ) %= MOD;
    root[ A[ x ] ]->update( 0, vcnt[ A[ x ] ], rnk[ x ], x );
    ( ans += root[ A[ x ] ]->ans ) %= MOD;
    if( ans < 0 ) ans += MOD;
    cout << ans << "\n";
  }
  return 0;
}