[线段树] [51nod] 1174 区间中最大的数

裸线段树

且只有查询

基础

#pragma GCC optimize(2)
#include <iostream>
#include <cmath>
#include <iomanip>

using namespace std;

const int MAXN = 1e6 + 10;

typedef long long ll;

ll arr[MAXN] = {0};

ll tree[MAXN * 4 + 10] = {0};

void buildtree(int now, int l, int r)
{
	if(l == r)
	{
		tree[now] = arr[l];
		return ;
	}

	int mid = l + (r - l) / 2;

	buildtree(now * 2, l, mid);

	buildtree(now * 2 + 1, mid + 1, r);

	tree[now] = max(tree[now * 2], tree[now * 2 + 1] );

}

ll find(int now, int l, int r, int x, int y)
{
	if(r < x || l > y)
		return -1;
	if(x <= l && y >= r)
		return tree[now];

	int mid = l + (r - l) / 2;

	ll ans = 0;

	ans = max(ans, find(now * 2, l, mid, x, y) );

	ans = max(ans, find(now * 2 + 1, mid + 1, r, x, y) );

	return ans;

}

int main()
{
	ios::sync_with_stdio(false);

	cin.tie(0);

	cout.tie(0);

    int N, T;

    cin>>N;

    for(int i = 1; i <= N; i++)
    	cin>>arr[i];

    buildtree(1, 1, N);
	
	//for(int i = 0; i < 10; i++)
		//cout<<i<<' '<<tree[i]<<endl;
		
    cin>>T;

    while(T--)
    {
    	int x, y;

    	cin>>x>>y;

    	cout<<find(1, 1, N, x + 1, y + 1)<<endl;
    }

    return 0;
}