社区讨论

萌新刚学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 条回复,欢迎继续交流。

正在加载回复...