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

Problem - G - Codeforces

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).

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;
}
```