CFR 547 C. Mike and Foam ( Mobius Inversion )

Problem - 547C - Codeforces

題意：
給 N 個數字的數列 A。接著 Q 筆操作，每次將 A[ idx ] 取出 / 放入一個櫃子。求每次操作完，櫃子裡有多少無序對，其最大公因數為 1。

資料規模：
N, Q ≤ 2e5
max{ A } ≤ 5e5
TL: 2000 ms

解法：
令 p 序列為當前櫃子裡的值，N 為 p 序列的大小：




在給定的數據範圍內，每次操作至多只會更改 2^6 個 bai 值，因此暴力維護 bai 值和答案即可。

時間 / 空間複雜度：
O( MAXA lg MAXA + Q * 2^6 ) / O( MAXA )

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

const int MAXN = ( int ) 2e5;
const int MAXA = ( int ) 5e5;

int N, Q;
int A[ MAXN ];
int mu[ MAXA + 1 ];
int in_shelf[ MAXN ];
int np[ MAXA + 1 ];
vector< int > pf[ MAXA + 1 ];
int bai_cnt[ MAXA + 1 ];

signed main(){
  { // preprocess mu
    mu[ 1 ] = 1;
    for( int i = 1; i < MAXA; ++i ){
      for( int j = i + i; j <= MAXA; j += i ){
        mu[ j ] -= mu[ i ];
      }
    }
  }
  { // preprocess prime factors
    for( int i = 2; i < MAXA; ++i ){
      if( np[ i ] ) continue;
      pf[ i ].emplace_back( i );
      for( int j = i + i; j <= MAXA; j += i ){
        np[ j ] = 1;
        pf[ j ].emplace_back( i );
      }
    }
  }
  ios::sync_with_stdio( 0 );
  cin >> N >> Q;
  for( int i = 0; i < N; ++i ){
    cin >> A[ i ];
  }
  long long ans = 0;
  for( int qi = 0; qi < Q; ++qi ){
    int idx; cin >> idx; --idx;
    int sign = in_shelf[ idx ] ? -1 : 1;
    ans -= 1LL * mu[ 1 ] * bai_cnt[ 1 ] * ( bai_cnt[ 1 ] - 1 ) / 2;
    bai_cnt[ 1 ] += sign;
    ans += 1LL * mu[ 1 ] * bai_cnt[ 1 ] * ( bai_cnt[ 1 ] - 1 ) / 2;
    if( A[ idx ] > 1 ){
      queue< tuple< int, int > > que;
      que.emplace( 1, 0 );
      while( not que.empty() ){
        int v, t; tie( v, t ) = que.front(); que.pop();
        if( A[ idx ] % ( 1LL * v * pf[ A[ idx ] ][ t ] ) == 0 ){
          int nv = v * pf[ A[ idx ] ][ t ];
          ans -= 1LL * mu[ nv ] * bai_cnt[ nv ] * ( bai_cnt[ nv ] - 1 ) / 2;
          bai_cnt[ nv ] += sign;
          ans += 1LL * mu[ nv ] * bai_cnt[ nv ] * ( bai_cnt[ nv ] - 1 ) / 2;
          que.emplace( nv, t );
        }
        if( t + 1 < pf[ A[ idx ] ].size() ){
          que.emplace( v, t + 1 );
        }
      }
    }
    in_shelf[ idx ] ^= 1;
    cout << ans << "\n";
  }
  return 0;
}