0w1

CFR 567 D. One-Dimensional Battle Ships ( Sqrt Decomposition )

Problem - 567D - Codeforces

題意:
有 1 * N 的棋盤,K 艘長度為 A 的船,不接觸且不重疊地擺放在其中。你接著對 M 個相異位子依序開槍,但你的朋友每一次都說你撲空。求第幾次開槍後是可以確定你的朋友說謊。若無解輸出 -1。

資料規模:
N ≤ 2e5
M ≤ 2e5

解法:
考慮一個長度 n 的空地,是可以合法地放恰好 ( n + 1 ) / ( A + 1 ) 艘船的。每次開槍等於是設置了一個新的牆壁。
貌似基於這個就可以寫二分搜,好像比分塊寫一點。
這份代碼用分塊,因為每次只會將某個連通分量一分為二 ( 可能會分出空分量但不要緊 ),因此只要減去這一大塊的貢獻,再加回新的兩塊的貢獻就能順利更新。需要用於計算貢獻的是一個支持詢問左方最靠右的牆位子和右方最靠左的牆位子的結構。可以用分塊做,頗快的。

時間 / 空間複雜度:
O( N ^ 1.5 ) / O( N )

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

const int MAXN = ( int ) 2e5;
const int BS = 500;

int N, K, A;
int blk_l[ BS ], blk_r[ BS ];
int mark[ MAXN ];

signed main(){
  ios::sync_with_stdio( 0 );
  cin >> N >> K >> A;
  int M; cin >> M;
  int sum = ( N + 1 ) / ( A + 1 );
  if( sum < K ){
    cout << -1 << endl;
    exit( 0 );
  }
  for( int i = 0; i < BS; ++i ){
    blk_l[ i ] = -1;
    blk_r[ i ] = N;
  }
  for( int qi = 0; qi < M; ++qi ){
    int u; cin >> u; --u;
    int L = -1, R = N; // [ L, R ]
    for( int i = u - 1; ( i + BS ) % BS != BS - 1; --i ){
      if( mark[ i ] ){
        L = i;
        break;
      }
    }
    for( int i = u / BS - 1; L == -1 and i >= 0; --i ){
      L = blk_l[ i ];
    }
    for( int i = u + 1; i % BS != 0; ++i ){
      if( mark[ i ] ){
        R = i;
        break;
      }
    }
    for( int i = u / BS + 1; R == N and i < BS; ++i ){
      R = blk_r[ i ];
    }
    sum = sum - ( R - L ) / ( A + 1 ) + ( u - L ) / ( A + 1 ) + ( R - u ) / ( A + 1 );
    mark[ u ] = 1;
    blk_l[ u / BS ] = max( blk_l[ u / BS ], u );
    blk_r[ u / BS ] = min( blk_r[ u / BS ], u );
    if( sum < K ){
      cout << qi + 1 << endl;
      exit( 0 );
    }
  }
  cout << -1 << endl;
  return 0;
}