SHARE
TWEET

Circular RMQ

Maruf_Hasan Feb 19th, 2019 64 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define M 200100
  4. int arr[M];
  5. //int tree[4*M];
  6. int tree2[4*M];
  7. int lazy[4*M];
  8.  
  9. void init(int node,int b,int e)
  10. {
  11.     if(b==e)
  12.     {
  13.       //  tree[node]=arr[b];
  14.         tree2[node]=arr[b];
  15.         return;
  16.     }
  17.     int left=node*2;
  18.     int right=left+1;
  19.     int mid=(b+e)/2;
  20.     init(left,b,mid);
  21.     init(right,mid+1,e);
  22.     //tree[node]=tree[left]+tree[right];
  23.     tree2[node]=min(tree2[left],tree2[right]);
  24. }
  25.  
  26. void update(int node,int b,int e,int i,int j,int val)
  27. {
  28.     if(lazy[node])
  29.     {
  30.         //tree[node]+=(e-b+1)*lazy[node];
  31.         tree2[node]+=lazy[node];
  32.         if(b!=e)
  33.         {
  34.             lazy[node*2]+=lazy[node];
  35.             lazy[node*2+1]+=lazy[node];
  36.         }
  37.         lazy[node]=0;
  38.     }
  39.     if(e<i || b>j)
  40.         return;
  41.     if(b>=i && e<=j)
  42.     {
  43.         //tree[node]+=(e-b+1)*lazy[node];
  44.         tree2[node]+=val;
  45.         if(b!=e)
  46.         {
  47.             lazy[node*2]+=val;
  48.             lazy[node*2+1]+=val;
  49.         }
  50.     return;
  51.     }
  52.     int mid=(b+e)/2;
  53.     int left=node<<1;
  54.     int right=left+1;
  55.     update(left,b,mid,i,j,val);
  56.     update(right,mid+1,e,i,j,val);
  57.     //tree[node]=tree[left]+tree[right];
  58.     tree2[node]=min(tree2[left],tree2[right]);
  59. }
  60. int query(int node,int b,int e,int i,int j)
  61. {
  62.     if(b>j || e<i)
  63.         return M;
  64.     if(lazy[node])
  65.     {
  66.         tree2[node]+=lazy[node];
  67.         if(b!=e)
  68.         {
  69.             lazy[node*2]+=lazy[node];
  70.             lazy[node*2+1]+=lazy[node];
  71.         }
  72.         lazy[node]=0;
  73.     }
  74.     if(b>=i && e<=j)
  75.     {
  76.         return tree2[node];
  77.     }
  78.     int mid=(b+e)/2;
  79.     int left=node<<1;
  80.     int right=left+1;
  81.     int p1=query(left,b,mid,i,j);
  82.     int p2=query(right,mid+1,e,i,j);
  83.     return min(p1,p2);
  84. }
  85.  
  86. int main()
  87. {
  88.     int n,i;
  89.     cin>>n;
  90.     for(i=1;i<=n;i++)
  91.     {
  92.         cin>>arr[i];
  93.     }
  94.     //for(i=1;i<=n;i++)
  95.       //1  cout<<arr[i]<<" ";
  96.     init(1,1,n);
  97.     int qq;
  98.     scanf("%d ",&qq);
  99.     string a;
  100.     //getchar();
  101.     while(qq--)
  102.     {
  103.  
  104.     getline(cin, a);
  105.     vector<int>v;
  106.     stringstream ss(a);
  107.     int num;
  108.     while(ss >> num)
  109.     {
  110.         v.push_back(num);
  111.     }
  112.  
  113.     //for(i=0;i<v.size();i++)
  114.       //  cout<<v[i]<<endl;
  115.  
  116.  
  117.     if(v.size()==2)
  118.     {
  119.         int ans;
  120.         int p=v[0]+1,q=v[1]+1;
  121.         if(p<=q)
  122.         {
  123.  
  124.         ans=query(1,1,n,p,q);
  125.         }
  126.         else
  127.         {
  128.             int a1=query(1,1,n,p,n);
  129.             int a2=query(1,1,n,1,q);
  130.             ans=min(a1,a2);
  131.         }
  132.         cout<<ans<<endl;
  133.     }
  134.     else
  135.     {
  136.     int p=v[0]+1;
  137.     int q=v[1]+1;
  138.     if(p<=q)
  139.     {
  140.         update(1,1,n,p,q,v[2]);
  141.     }
  142.     else
  143.     {
  144.         //int p=v[0]+1;
  145.         //int q=v[1]+1;
  146.         update(1,1,n,p,n,v[2]);
  147.         update(1,1,n,1,q,v[2]);
  148.     }
  149.     }
  150.     }
  151.     return 0;
  152. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top