Advertisement
Horikita_Suzune

Untitled

Nov 30th, 2019
179
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.69 KB | None | 0 0
  1. #include<iostream>
  2. #define MAXN 500000
  3. using namespace std;
  4. struct Node{
  5.     int l, r;
  6.     int min, max;
  7.     Node *left, *right;
  8. };
  9. Node tree[MAXN<<1];
  10. int num[MAXN];
  11. int nNodeCnt = 0;
  12. void build(Node *rt, int l, int r){
  13.     rt->l = l;
  14.     rt->r = r;
  15.     if(l == r){
  16.         rt->min = rt->max = num[l];
  17.         return ;
  18.     }
  19.  
  20.     nNodeCnt++;
  21.     rt->left = tree + nNodeCnt;
  22.     nNodeCnt++;
  23.     rt->right = tree + nNodeCnt;
  24.  
  25.     int m = (l + r) >> 1;
  26.     build(rt->left, l, m);
  27.     build(rt->right, m + 1, r);
  28.     rt->max = max(rt->left->max, rt->right->max);
  29.     rt->min = min(rt->left->min, rt->right->min);
  30.  
  31. }
  32. void update(Node *rt, int x, int v){
  33.     if(rt->l == rt->r ){
  34.         rt->max+=v;
  35.         rt->min=rt->max;
  36.                 return ;
  37.     }
  38.  
  39.     int m = (rt->l + rt->r) >> 1;
  40.     if(x <= m){
  41.         update(rt->left, x, v);
  42.     }else{
  43.                 update(rt->right, x, v);
  44.     }
  45.         rt->max = max(rt->left->max, rt->right->max);
  46.         rt->min = min(rt->left->min, rt->right->min);
  47. }
  48. int ans_max , ans_min;
  49. void query(Node *rt, int l, int r){
  50.     if(rt->l == l && rt->r == r){
  51.         ans_max = ans_max > rt->max ? ans_max : rt->max;
  52.         ans_min = ans_min < rt->min ? ans_min : rt->min;
  53.         return ;
  54.     }
  55.  
  56.     int m = (rt->l + rt->r) >> 1;
  57.     if(r <= m){
  58.         query(rt->left, l, r);
  59.     }else if(l > m){
  60.         query(rt->right, l, r);
  61.     }else{
  62.         query(rt->left, l, m);
  63.         query(rt->right, m + 1, r);
  64.     }
  65. }
  66. int main(){
  67.     int n;
  68.     cin>>n;
  69.     for(int i=0;i<n;i++){
  70.         cin>>num[i];
  71.     }
  72.     build(tree,0,n-1);
  73.     cin>>a>>b;
  74.     query(tree,a-1,b-1);
  75. }
  76.  
  77. //Segment Tree Template(For RMQ Problems)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement