Ladies_Man

MaxEl of seq. (TREE) максимал.эл.последовательности

Dec 17th, 2013
217
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 2.01 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. int *tree_data = 0;
  6.  
  7. #define min(x,y) (x<y?x:y)
  8. #define max(x,y) (x>y?x:y)
  9.  
  10. #define TREE_FUNCT(x,y) (max(x,y))
  11.  
  12. void build (int a[], int v, int tl, int tr) {
  13.         if (tl == tr)
  14.         tree_data[v] = a[tl];
  15.     else {
  16.         int tm = (tl + tr) / 2;
  17.         build (a, v*2, tl, tm);
  18.         build (a, v*2+1, tm+1, tr);
  19.         tree_data[v] = TREE_FUNCT(tree_data[v*2],tree_data[v*2+1]);
  20.     }
  21. }
  22.  
  23.  
  24. int compute (int v, int tl, int tr, int l, int r, int* value) {
  25.     int tm;
  26.     int lvalue,rvalue;
  27.     int lresult,rresult;
  28.  
  29.     if (l > r)
  30.         return 0;
  31.     if (l == tl && r == tr){
  32.         *value = tree_data[v];
  33.         return 1;
  34.     }
  35.        
  36.     tm = (tl + tr) / 2;
  37.  
  38.     lresult = compute (v*2, tl, tm, l, min(r,tm),&lvalue);
  39.     rresult = compute (v*2+1, tm+1, tr, max(l,tm+1), r,&rvalue);
  40.  
  41.     if ((lresult>0)&&(rresult>0)){
  42.         *value = TREE_FUNCT(lvalue,rvalue);
  43.     } else{
  44.         if (lresult)
  45.             *value = lvalue;
  46.         if (rresult)
  47.             *value = rvalue;
  48.     }
  49.  
  50.    
  51.  
  52.     return 1;
  53. }
  54.  
  55. void update (int v, int tl, int tr, int pos, int new_val) {
  56.     if (tl == tr)
  57.         tree_data[v] = new_val;
  58.     else {
  59.         int tm = (tl + tr) / 2;
  60.         if (pos <= tm)
  61.             update (v*2, tl, tm, pos, new_val);
  62.         else
  63.             update (v*2+1, tm+1, tr, pos, new_val);
  64.         tree_data[v] = TREE_FUNCT(tree_data[v*2],tree_data[v*2+1]);
  65.     }
  66. }
  67.  
  68. int main(int argc,char** argv){
  69.     int* data = 0;
  70.     int i,N;
  71.     int ops_count;
  72.  
  73.     scanf("%d",&N);
  74.  
  75.     data = (int*)malloc(sizeof(int) * N);
  76.     tree_data = (int*)malloc(N * 4 * sizeof(int));
  77.  
  78.  
  79.     for (i=0;i!=N;i++)
  80.         scanf("%d",&(data[i]));
  81.  
  82.     build(data,1,0,N-1);
  83.  
  84.  
  85.  
  86.     scanf("%d",&ops_count);
  87.     while(ops_count){
  88.         char command[255];
  89.         int l1,l2;
  90.  
  91.         memset(command,0,255);
  92.         scanf("%s",command);
  93.         scanf("%d",&l1);
  94.         scanf("%d",&l2);
  95.        
  96.         if (command[0]=='M'){
  97.            
  98.             if (l2 <= N-1){
  99.                 int result;
  100.                 compute(1,0,N-1,l1,l2,&result);
  101.                 printf("%d\n",result);
  102.             }
  103.         }
  104.         if (command[0]=='U'){
  105.             if (l1 <= N-1){
  106.                 update(1,0,N-1,l1,l2);
  107.             }
  108.  
  109.         }
  110.  
  111.         ops_count--;
  112.     }
  113.  
  114.  
  115.     free(tree_data);
  116.     free(data);
  117. }
Advertisement
Add Comment
Please, Sign In to add comment