社区讨论
萌新刚学OI,不是女生,求助QAQ
P1816忠诚参与者 11已保存回复 12
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 12 条
- 当前快照
- 1 份
- 快照标识符
- @mi860otf
- 此快照首次捕获于
- 2025/11/21 09:12 4 个月前
- 此快照最后确认于
- 2025/11/21 09:48 4 个月前
RT,不知道哪里错了QAQ,求助大佬
CPP#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define MAXN 500010
#define ll long long
using namespace std;
int a[ MAXN ] , n , m , cnt;
struct Node {
int l , r , MIN;
Node * left , * right;
}pool[ 2 * MAXN ];
inline int read()
{
int x=0,f=1;char c=getchar();
while( c > '9' || c < '0' ){if( c == '-' )f = -1;c = getchar();}
while( c <='9' && c >= '0' ){x = (x<<3) + (x<<1) + c - '0';c = getchar();}
return x * f;
}
void build ( int l, int r , Node * ro )
{
ro -> l = l;
ro -> r = r;
if( l == r )
{
ro -> MIN = a[ l ];
return;
}
int mid = ( l + r ) / 2;
Node * lson = &pool[ ++ cnt ];
Node * rson = &pool[ ++ cnt ];
ro -> left = lson;
ro -> right = rson;
build( l , mid , lson );
build( mid + 1 , r , rson );
ro -> MIN = min( ro -> left -> MIN , ro -> right -> MIN );
}
int find( int l , int r , Node * cur )
{
if( l == cur -> l && r == cur -> r ) return cur -> MIN;
int mid = ( cur -> l + cur -> r ) / 2;
if( l > mid ) return find( l , r , cur -> right );
if( mid >= r ) return find( l , r , cur -> left );
return min( find( l , mid , cur -> left ) , find( mid + 1 , r , cur -> right) );
}
int main()
{
n = read() , m = read();
for (int i = 1 ; i <= n ;i ++) a[i] = read();
build( 1 , n , pool );
while( m-- )
{
int l = read() , r = read();
printf( "%d \n" , find( l , r , pool ) );
}
return 0;
}
/*
10 3
1 2 3 4 5 6 7 8 9 10
2 7
3 9
1 10
*/
回复
共 12 条回复,欢迎继续交流。
正在加载回复...