CFR 803 G. Periodic RMQ Problem ( Discretization, Segment Tree )

Problem - G - Codeforces

題意：
給一個長度為 n 的 B 數列。現在將 B 數列黏貼 k 次變成一個新的數列。有 Q 筆詢問：
op = 1:
__將 [ l, r ] 中的元素全部更改為 x
op = 2:
__詢問 [ l, r ] 中的最小值

制約：
The first line contains two integers n and k (1 ≤ n ≤ 1e5, 1 ≤ k ≤ 1e4).
The second line contains n integers — elements of the array b (1 ≤ bi ≤ 1e9).
The third line contains one integer q (1 ≤ q ≤ 1e5).
Then q lines follow, each representing a query. Each query is given either as 1 l r x — set all elements in the segment from l till r (including borders) to x (1 ≤ l ≤ r ≤ n·k, 1 ≤ x ≤ 1e9) or as 2 l r — find the minimum among all elements in the segment from l till r (1 ≤ l ≤ r ≤ n·k).

解法：
關鍵在於真正在意的資訊可以壓縮。
首先預讀所有詢問，對左右界進行離散化。舉例來說，離散化後如果對詢問中出現的某個左界或右界 a 有對應 st，比 st 大的左界或右界中最小的值 b 對應到 st + 1，那麼讓線段樹中下標為 st 的節點紀錄 [ a, b ) 的最小值。

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

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

const int MAXN = int( 1e5 );
const int MAXK = int( 1e4 );
const int MAXB = int( 1e9 );
const int MAXQ = int( 1e5 );

int N, K;
int B[ MAXN * 2 ]; // circular
int Q;
vector< tuple< int, int, int, int > > qry;

vector< int > unq;
unordered_map< int, int > dmp;

struct itvt {
  int minv[ MAXQ << 3 ];
  int tag[ MAXQ << 3 ];
  void init() {
    memset( minv, 0x3f3f3f3f, sizeof( minv ) );
    memset( tag, 0x3f3f3f3f, sizeof( tag ) );
  }
  void pull( int t ) {
    minv[ t ] = min( minv[ t << 1 ], minv[ t << 1 | 1 ] );
  }
  void push( int t ) {
    if( tag[ t ] != 0x3f3f3f3f ) {
      minv[ t << 1 ] = tag[ t ];
      tag[ t << 1 ] = tag[ t ];
      minv[ t << 1 | 1 ] = tag[ t ];
      tag[ t << 1 | 1 ] = tag[ t ];
      tag[ t ] = 0x3f3f3f3f;
    }
  }
  void build( int t, int lb, int rb, int *arr ) {
    tag[ t ] = 0x3f3f3f3f;
    if( lb + 1 == rb ) {
      minv[ t ] = arr[ lb ];
      return;
    }
    int mid = lb + rb >> 1;
    build( t << 1, lb, mid, arr );
    build( t << 1 | 1, mid, rb, arr );
    pull( t );
  }
  void update( int t, int lb, int rb, int ql, int qr, int v ) {
    if( qr <= lb or rb <= ql ) return;
    if( ql <= lb and rb <= qr ) {
      minv[ t ] = v;
      tag[ t ] = v;
      return;
    }
    int mid = lb + rb >> 1;
    push( t );
    update( t << 1, lb, mid, ql, qr, v );
    update( t << 1 | 1, mid, rb, ql, qr, v );
    pull( t );
  }
  int query( int t, int lb, int rb, int ql, int qr ) {
    if( qr <= lb or rb <= ql ) return 0x3f3f3f3f;
    if( ql <= lb and rb <= qr ) return minv[ t ];
    int mid = lb + rb >> 1;
    push( t );
    int res = min( query( t << 1, lb, mid, ql, qr ), query( t << 1 | 1, mid, rb, ql, qr ) );
    pull( t );
    return res;
  }
} root, sup;

signed main() {
  ios::sync_with_stdio( 0 );
  cin >> N >> K;
  for( int i = 0; i < N; ++i ) {
    cin >> B[ i ];
    B[ N + i ] = B[ i ];
  }
  sup.build( 1, 0, 2 * N, B );
  cin >> Q;
  for( int i = 0; i < Q; ++i ) {
    int op;
    cin >> op;
    if( op == 1 ) {
      int l, r, x;
      cin >> l >> r >> x;
      --l;
      qry.emplace_back( op, l, r, x ); // 0 base [ l, r )
      unq.emplace_back( l );
      unq.emplace_back( r );
    } else {
      int l, r;
      cin >> l >> r;
      --l;
      qry.emplace_back( op, l, r, -1 );
      unq.emplace_back( l );
      unq.emplace_back( r );
    }
  }
  sort( unq.begin(), unq.end() );
  unq.resize( unique( unq.begin(), unq.end() ) - unq.begin() );
  for( int i = 0; i < unq.size(); ++i ) {
    dmp[ unq[ i ] ] = i;
  }
  root.init();
  for( int i = 0; i + 1 < unq.size(); ++i ) {
    if( unq[ i + 1 ] - unq[ i ] >= N ) {
      root.update( 1, 0, unq.size(), i, i + 1, sup.minv[ 1 ] );
    } else {
      root.update( 1, 0, unq.size(), i, i + 1, sup.query( 1, 0, 2 * N, unq[ i ] % N, unq[ i ] % N + unq[ i + 1 ] - unq[ i ] ) );
    }
  }
  for( int i = 0; i < Q; ++i ) {
    int op, ql, qr, x;
    tie( op, ql, qr, x ) = qry[ i ];
    if( op == 1 ) {
      root.update( 1, 0, unq.size(), dmp[ ql ], dmp[ qr ], x );
    } else {
      cout << root.query( 1, 0, unq.size(), dmp[ ql ], dmp[ qr ] ) << "\n";
    }
  }
  return 0;
}