[14428] 수열과 쿼리 16

[14428] 수열과 쿼리 16

#include < stdio.h >

#include < vector >

#include < limits.h >

#include < algorithm >

using namespace std ;

typedef long long ll;

vector < ll > num;

vector < ll > segTree;

int n, m;

ll minIdx(ll x, ll y) {

if (x = = - 1 ) return y;

if (y = = - 1 ) return x;

if (num[x] = = num[y]) return x < y ? x : y;

return num[x] < num[y] ? x : y;

}

ll makeSegTree( int node, int start, int end ) {

if (start = = end ) return segTree[node] = start;

int mid = (start + end ) / 2 ;

return segTree[node] = minIdx(makeSegTree(node * 2 , start, mid), makeSegTree(node * 2 + 1 , mid + 1 , end ));

}

ll updateSegTree( int node, int start, int end , int idx) {

if (idx < start | | idx > end ) return segTree[node];

if (start = = end ) {

return segTree[node];

}

int mid = (start + end ) / 2 ;

return segTree[node] = minIdx(updateSegTree(node * 2 , start, mid, idx),

updateSegTree(node * 2 + 1 , mid + 1 , end , idx));

}

ll query( int node, int start, int end , int left, int right) {

if (left > end | | right < start) return - 1 ;

if (left < = start & & end < = right) return segTree[node];

int mid = (start + end ) / 2 ;

return minIdx(query(node * 2 , start, mid, left, right), query(node * 2 + 1 , mid + 1 , end , left, right));

}

int main( void ) {

int i;

scanf ( "%d" , & n);

num.resize(n + 3 );

segTree.resize( 4 * n);

for (i = 1 ; i < = n; i + + )

scanf ( "%lld" , & num[i]);

makeSegTree( 1 , 1 , n);

scanf ( "%d" , & m);

for (i = 0 ; i < m; i + + ) {

int a;

scanf ( "%d" , & a);

if (a = = 1 ) {

int idx;

ll value;

scanf ( "%d %lld" , & idx, & value);

num[idx] = value;

updateSegTree( 1 , 1 , n, idx);

}

else if (a = = 2 ) {

int s, e;

scanf ( "%d %d" , & s, & e);

printf ( "%lld

" , query( 1 , 1 , n, s, e));

}

}

return 0 ;

}

from http://dizlet.tistory.com/23 by ccl(A) rewrite - 2021-08-30 23:00:25