fork(1) download
copy 
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<vector>
  4. #include<algorithm>
  5.  
  6. using namespace std;
  7.  
  8. #define FOR(i,n) for(long i=0;i<n;i++)
  9. #define FORE(i,a,b) for(long i=a;i<b;i++)
  10. typedef long long ll;
  11. #define N 100001
  12.  
  13. void initialise(long b,long e,long node);
  14. long query(long b,long e,long i,long j,long node);
  15. void update(long b,long e,long x,long node);
  16.  
  17. ll arr[N],mat[5*N+1]; //mat contains the array position of maximum value in the node
  18.  
  19. void initialise(long b,long e,long node)
  20. {
  21.     if(b==e)
  22.         mat[node]=b;
  23.     else{
  24.         initialise(b,(b+e)/2,2*node);
  25.         initialise((b+e)/2+1,e,2*node+1);
  26.         if(arr[mat[2*node]]>=arr[mat[2*node+1]])
  27.             mat[node]=mat[2*node];
  28.         else
  29.             mat[node]=mat[2*node+1];
  30.     }
  31.     return;
  32. }
  33.  
  34. long query(long b,long e,long i,long j,long node)
  35. {
  36.     long p1,p2;
  37.     if(i>e || j<b)
  38.         return -1;
  39.     else{
  40.         if(i<=b && j>=e)
  41.             return mat[node];
  42.         p1=query(b,(b+e)/2,i,j,2*node);
  43.         p2=query((b+e)/2+1,e,i,j,2*node+1);
  44.         if(p1==-1)
  45.             return p2;
  46.         else if(p2==-1)
  47.             return p1;
  48.         else if(arr[p1]>=arr[p2])
  49.             return p1;//mat[node]=p1;
  50.         else
  51.             return p2;//mat[node]=p2;
  52.  
  53.     }
  54. }
  55.  
  56. void update(long b,long e,long x,long node)
  57. {
  58.     if(x>e || x<b)
  59.         return;
  60.     // if(arr[mat[node]] < arr[x])
  61.       //      mat[node]=x;
  62.     else if(b!=e){
  63.         if(arr[mat[node]] < arr[x])
  64.             mat[node]=x;
  65.         update(b,(b+e)/2,x,2*node);
  66.         update((b+e)/2+1,e,x,2*node+1);
  67.         //return;
  68.     }
  69.     //return;
  70. }
  71.  
  72. int main()
  73. {
  74.     long n,q,i,j,p1,p2,l,m,temp;
  75.     char ch;
  76.     scanf("%ld",&n);
  77.     FORE(i,1,n+1)
  78.         scanf("%lld",arr+i);
  79.     arr[0]=0;
  80.     scanf("%ld",&q);
  81.     FOR(i,5*N)
  82.         mat[i]=-1;
  83.     initialise(1,n,1);
  84.     while(q--)
  85.     {
  86.         cin>>ch>>i>>j;
  87.         if(ch=='U')
  88.         {
  89.             arr[i]=j;
  90.             update(1,n,i,1);
  91.         }
  92.         else if(ch=='Q')
  93.         {
  94.             if(i>j)
  95.             {
  96.                 temp=i;
  97.                 i=j;
  98.                 j=temp;
  99.             }
  100.             p1=query(1,n,i,j,1);
  101.             if(p1==i)
  102.             {
  103.                 p2=query(1,n,i+1,j,1);
  104.             }
  105.             else if(p1==j)
  106.             {
  107.                 p2=query(1,n,i,j-1,1);
  108.             }
  109.             else{
  110.                l=query(1,n,i,p1-1,1);
  111.                m=query(1,n,p1+1,j,1);
  112.                if(arr[l]>=arr[m])
  113.                     p2=l;
  114.                else
  115.                 p2=m;
  116.             }
  117.             printf("%lld\n",arr[p1]+arr[p2]);
  118.         }
  119.     }
  120.     return 0;
  121. }
  122.  
Success #stdin #stdout 0s 7376KB
comments (?)
stdin
copy 
5
1 2 3 4 5
6
Q 2 4
Q 2 5
U 1 6
Q 1 5
U 1 7
Q 1 5
stdout
copy 
7
9
11
12
https://ideone.com/wvoF5a
language:
C++ 4.3.2 (gcc-4.3.2)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!