传送门:【CodeForces】52C Circular RMQ
题目分析:线段树水题。
代码如下:
#include <cmath> #include <cstdio> #include <cstring> #include <algorithm> using namespace std ; #define REP( i , a , b ) for ( int i = ( a ) ; i < ( b ) ; ++ i ) #define FOR( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i ) #define REV( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i ) #define CLR( a , x ) memset ( a , x , sizeof a ) #define ls ( o << 1 ) #define rs ( o << 1 | 1 ) #define lson ls , l , m #define rson rs , m + 1 , r #define root 1 , 1 , n #define rt o , l , r #define mid ( ( l + r ) >> 1 ) typedef long long LL ; const int MAXN = 200005 ; LL addv[MAXN << 2] , minv[MAXN << 2] ; int n , q ; char s[MAXN] ; void pushup ( int o ) { minv[o] = min ( minv[ls] , minv[rs] ) ; } void fun ( int o , int v ) { addv[o] += v ; minv[o] += v ; } void pushdown ( int o ) { if ( !addv[o] ) return ; fun ( ls , addv[o] ) ; fun ( rs , addv[o] ) ; addv[o] = 0 ; } void build ( int o , int l , int r ) { addv[o] = 0 ; if ( l == r ) { scanf ( "%I64d" , &minv[o] ) ; return ; } int m = mid ; build ( lson ) ; build ( rson ) ; pushup ( o ) ; } void update ( int L , int R , int v , int o , int l , int r ) { if ( L <= l && r <= R ) { fun ( o , v ) ; return ; } pushdown ( o ) ; int m = mid ; if ( L <= m ) update ( L , R , v , lson ) ; if ( m < R ) update ( L , R , v , rson ) ; pushup ( o ) ; } LL query ( int L , int R , int o , int l , int r ) { if ( L <= l && r <= R ) return minv[o] ; pushdown ( o ) ; int m = mid ; if ( R <= m ) return query ( L , R , lson ) ; if ( m < L ) return query ( L , R , rson ) ; return min ( query ( L , R , lson ) , query ( L , R , rson ) ) ; } void solve () { build ( root ) ; scanf ( "%d " , &q ) ; while ( q -- ) { fgets ( s , MAXN , stdin ) ; int cnt = 0 , v , l , r ; for ( int i = 0 ; s[i] ; ++ i ) if ( s[i] == ' ' ) ++ cnt ; if ( cnt == 1 ) { sscanf ( s , "%d%d" , &l , &r ) ; ++ l , ++ r ; if ( l <= r ) printf ( "%I64d\n" , query ( l , r , root ) ) ; else printf ( "%I64d\n" , min ( query ( l , n , root ) , query ( 1 , r , root ) ) ) ; } else { sscanf ( s , "%d%d%d" , &l , &r , &v ) ; ++ l , ++ r ; if ( l <= r ) update ( l , r , v , root ) ; else update ( l , n , v , root ) , update ( 1 , r , v , root ) ; } } } int main () { while ( ~scanf ( "%d" , &n ) ) solve () ; return 0 ; }