Advertisement
ismaeil

C. Circular RMQ

Mar 6th, 2020
209
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.20 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define OO 1e9
  3.  
  4. using namespace std;
  5.  
  6. const int N = 1e6 + 500;
  7. int a[N] ,Seg[N*5] ,Lazy[N*6] ,n ,m;
  8.  
  9. void build(int p=1 , int L=0 ,int R=n-1){
  10.     if( L == R ){
  11.         Seg[p] = a[L];
  12.         return;
  13.     }
  14.     int Mid = (L + R) >> 1;
  15.     build(p*2 , L , Mid);
  16.     build(p*2+1 , Mid+1 , R);
  17.  
  18.     Seg[p] = min( Seg[p*2] , Seg[p*2+1] );
  19. }
  20.  
  21. void pushLazy(int p){
  22.     if(!Lazy[p]) return;
  23.     Seg[p] += Lazy[p];
  24.     Lazy[p*2] += Lazy[p];
  25.     Lazy[p*2+1] += Lazy[p];
  26.     Lazy[p] = 0;
  27. }
  28.  
  29. void lazyUpdate(int i , int j ,int val , int L=0 , int R=n-1 , int p=1){
  30.     pushLazy(p);
  31.     if( R < i || L > j ) return;
  32.  
  33.     if( R <= j && L >= i){
  34.         Lazy[p] += val;
  35.         pushLazy(p);
  36.         return;
  37.     }
  38.     int Mid = (L + R) >> 1;
  39.     lazyUpdate(i,j,val,L,Mid,p*2);
  40.     lazyUpdate(i,j,val,Mid+1,R,p*2+1);
  41. }
  42.  
  43. int rmq(int i , int j , int L=0 , int R=n-1 ,int p=1){
  44.     pushLazy(p);
  45.     if( R < i || L > j ) return +OO;
  46.     if( L >= i && R <= j) return Seg[p];
  47.  
  48.     int Mid = (L + R) >> 1;
  49.     int c1 = rmq(i ,j ,L ,Mid ,p*2);
  50.     int c2 = rmq(i ,j ,Mid+1 ,R ,p*2+1);
  51.  
  52.     return min(c1,c2);
  53. }
  54.  
  55. int main()
  56. {
  57.     fstream f;
  58.     cin >> n;
  59.     for(int i=0 ; i<n ; i++) cin >> a[i];
  60.     build();
  61.  
  62.     cin >> m;
  63.     f.open("in.txt" , ios::out);
  64.     while(m--){
  65.         int c=0;
  66.         char ch[100] = "";
  67.         fflush(stdin);gets(ch);
  68.         for(int i=0 ; i<strlen(ch) ; i++)
  69.             if(ch[i] == ' ') c++;
  70.         f << c <<   ' ' <<ch << "\n";
  71.     }f.close();
  72.  
  73.     f.open("in.txt" , ios::in);
  74.     int c;
  75.     while(f >> c){
  76.         int l1 ,l2 ,r1 ,r2 ,x;
  77.         if(c == 1){
  78.             f >> l1 >> r1;
  79.             if(l1 < r1){
  80.                 cout << rmq(l1,r1) << endl;
  81.             }else{
  82.                 l2 = 0;
  83.                 r2 = n-1;
  84.                 cout << min( rmq(l2 ,r1) , rmq(l1 ,r2) )<< endl;
  85.             }
  86.         }else if(c == 2){
  87.             f >> l1 >> r1 >> x;
  88.             if(l1 < r1){
  89.                 lazyUpdate(l1,r1,x);
  90.             }else{
  91.                 l2 = 0;
  92.                 r2 = n-1;
  93.                 lazyUpdate(l2,r1,x);
  94.                 lazyUpdate(l1,r2,x);
  95.             }
  96.         }
  97.     }f.close();
  98.     return 0;
  99. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement