测例：

30 5

3 4 6 8 4 1 4 12 4 5 1234 34 54 213 12 3 6456 121 434 12 3 2 1234 234 234 45 1 34 6 234

1 3

4 8

23 29

1 25

13 29

 

#include <iostream>

#include <vector>

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <cmath>

using namespace std;

std::vector<int> v;

int len,queNum;

struct node

{

node* left;

node* right;

int value;

int rangel;

int ranger;

};

node* root;

void input(){

cin >> len >> queNum;

for (int i = 0 ; i < len; i++){

int a;

cin >> a;

v.push_back(a);

}

root = new node();

}

int initTree(int ss, int ee, node* r){

//cout << ss << ","<<ee<<endl;

r->rangel = ss;

r->ranger = ee;

int maxx;

if (ss == ee){

r->value = v[ss];

r->left = NULL;

r->right = NULL;

return r->value;

}

int middle = (r->rangel+r->ranger)/2;

node* ll = new node();

node* rr = new node();

maxx = max( initTree(ss,middle,ll) , initTree(middle+1,ee,rr) );

r->value = maxx;

r->left = ll;

r->right= rr;

return maxx;

}

int baoli(int ss, int ee){

int maxx = -1;

for (int i = ss-1; i< ee ; i++){

if (v[i] > maxx){

maxx = v[i];

}

}

return maxx;

}

int query(int ss, int ee, node* r){

if (r->rangel == ss && r->ranger == ee){

return r->value;

}

int middle = (r->rangel+r->ranger)/2;

if (ee <= middle){

return query(ss,ee,r->left);

}

if (ss > middle){

return query(ss,ee,r->right);

}

return max( query(ss,middle,r->left) , query(middle+1,ee,r->right) );

}

 

void output(){

while(queNum--){

int ss,ee;

cin >> ss >> ee;

int bb = baoli(ss,ee);

int qq = query(ss-1,ee-1,root);

if (bb != qq){

cout << "wrong! bb = "<<bb << " qq = "<<qq<<endl;

}

else{

cout << "Right res="<<qq<<endl;

}

}

}

int main(){

input();

initTree(0,len-1,root);

output();

return 0;

}