51nod1174--区间中最大的数--线段树
这题看着像是线段树 然而暴力也可以
而且并没有快多少 交了一发线段树 87ms 暴力125ms。。。。。
线段树 区间查询最大值
https://blog.****.net/holly_Z_P_F/article/details/81395652
暴力代码以及线段树代码
#include <iostream>
#include <cstring>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <algorithm>
#define pi 3.1415926535898
#define e 2.718281828459
using namespace std;
typedef long long ll;
int main()
{
int n;
cin>>n;
ll a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
int q;
cin>>q;
while(q--)
{
int i,j,max=0;
cin>>i>>j;
for(int ii=i;ii<=j;ii++)
{
if(max<=a[ii])
max=a[ii];
}
cout<<max<<endl;
max=0;
}
return 0;
}
线段树代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e5+7;
struct node{
int val,l,r;
}tree[maxn<<2];
int fa[maxn<<2];
int n,m,x,y,date;
void BuildTree(int i,int left,int right){
tree[i].l=left;
tree[i].r=right;
tree[i].val=0;
if(left==right){
fa[left]=i;return;
}
BuildTree(i<<1,left,(left+right)/2);
BuildTree(i<<1|1,(left+right)/2+1,right);
}
void UpdateTree(int ri){
if(ri==1) return ;
int fi=ri/2;
int a=tree[fi<<1].val;
int b=tree[(fi<<1)+1].val;
tree[fi].val=a>b?a:b;
UpdateTree(ri/2);
}
int Max;
void Query(int i,int l,int r){
if(tree[i].l==l&&tree[i].r==r){
Max=max(Max,tree[i].val);return ;
}
i=i<<1;
if(l<=tree[i].r){
if(r<=tree[i].r) Query(i,l,r);
else Query(i,l,tree[i].r);
}
i++;
if(r>=tree[i].l){
if(l>=tree[i].l) Query(i,l,r);
else Query(i,tree[i].l,r);
}
}
int main(){
scanf("%d",&n);
BuildTree(1,1,n);
for(int i=1;i<=n;i++){
scanf("%d",&date);
tree[fa[i]].val=date;
UpdateTree(fa[i]);
}
scanf("%d",&m);
while(m--){
scanf("%d%d",&x,&y);
Max=0;
Query(1,x+1,y+1);
printf("%d\n",Max);
}
return 0;
}