Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #define MAXN 500000
- using namespace std;
- struct Node{
- int l, r;
- int min, max;
- Node *left, *right;
- };
- Node tree[MAXN<<1];
- int num[MAXN];
- int nNodeCnt = 0;
- void build(Node *rt, int l, int r){
- rt->l = l;
- rt->r = r;
- if(l == r){
- rt->min = rt->max = num[l];
- return ;
- }
- nNodeCnt++;
- rt->left = tree + nNodeCnt;
- nNodeCnt++;
- rt->right = tree + nNodeCnt;
- int m = (l + r) >> 1;
- build(rt->left, l, m);
- build(rt->right, m + 1, r);
- rt->max = max(rt->left->max, rt->right->max);
- rt->min = min(rt->left->min, rt->right->min);
- }
- void update(Node *rt, int x, int v){
- if(rt->l == rt->r ){
- rt->max+=v;
- rt->min=rt->max;
- return ;
- }
- int m = (rt->l + rt->r) >> 1;
- if(x <= m){
- update(rt->left, x, v);
- }else{
- update(rt->right, x, v);
- }
- rt->max = max(rt->left->max, rt->right->max);
- rt->min = min(rt->left->min, rt->right->min);
- }
- int ans_max , ans_min;
- void query(Node *rt, int l, int r){
- if(rt->l == l && rt->r == r){
- ans_max = ans_max > rt->max ? ans_max : rt->max;
- ans_min = ans_min < rt->min ? ans_min : rt->min;
- return ;
- }
- int m = (rt->l + rt->r) >> 1;
- if(r <= m){
- query(rt->left, l, r);
- }else if(l > m){
- query(rt->right, l, r);
- }else{
- query(rt->left, l, m);
- query(rt->right, m + 1, r);
- }
- }
- int main(){
- int n;
- cin>>n;
- for(int i=0;i<n;i++){
- cin>>num[i];
- }
- build(tree,0,n-1);
- cin>>a>>b;
- query(tree,a-1,b-1);
- }
- //Segment Tree Template(For RMQ Problems)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement