fork download
copy 
  1. import java.io.BufferedReader; 
  2. import java.io.IOException; 
  3. import java.io.InputStreamReader; 
  4. import java.util.Scanner; 
  5. import java.util.StringTokenizer;
  6. import java.util.*;
  7. class KGSS{
  8.    static class FastReader 
  9.     { 
  10.         BufferedReader br; 
  11.         StringTokenizer st; 
  12.  
  13.         public FastReader() 
  14.         { 
  15.             br = new BufferedReader(new
  16.                      InputStreamReader(System.in)); 
  17.         } 
  18.  
  19.         String next() 
  20.         { 
  21.             while (st == null || !st.hasMoreElements()) 
  22.             { 
  23.                 try
  24.                 { 
  25.                     st = new StringTokenizer(br.readLine()); 
  26.                 } 
  27.                 catch (IOException  e) 
  28.                 { 
  29.                     e.printStackTrace(); 
  30.                 } 
  31.             } 
  32.             return st.nextToken(); 
  33.         } 
  34.  
  35.         int nextInt() 
  36.         { 
  37.             return Integer.parseInt(next()); 
  38.         } 
  39.  
  40.         long nextLong() 
  41.         { 
  42.             return Long.parseLong(next()); 
  43.         } 
  44.  
  45.         double nextDouble() 
  46.         { 
  47.             return Double.parseDouble(next()); 
  48.         } 
  49.  
  50.         String nextLine() 
  51.         { 
  52.             String str = ""; 
  53.             try
  54.             { 
  55.                 str = br.readLine(); 
  56.             } 
  57.             catch (IOException e) 
  58.             { 
  59.                 e.printStackTrace(); 
  60.             } 
  61.             return str; 
  62.         } 
  63.     } 
  64.     public static void main(String args[]){
  65.         FastReader sc=new FastReader(); 
  66.         int n=sc.nextInt();
  67.         int a[]=new int[n+1];
  68.         int tree[]=new int[4*n+1];
  69.         int asli_tree[]=new int[4*n+1];
  70.  
  71.         for(int i=1;i<n+1;i++)
  72.         {a[i]=sc.nextInt();}
  73.          builtTree(1,n,a,tree,asli_tree,1);
  74.  
  75.         int q=sc.nextInt();
  76.         while(q-->0){
  77.  
  78.         String z=sc.next();
  79.         int x=sc.nextInt();
  80.         int y=sc.nextInt();
  81.         if(z.equals("Q"))
  82.         {System.out.println(query(x,y,1,n,tree,asli_tree,1,1));}
  83.         if(z.equals("U"))
  84.         {update(y,x,0,n,tree,asli_tree,1);}
  85.     }
  86.    }
  87.    public static void builtTree(int s,int e,int a[],int tree[],int asli_tree[],int index){
  88.       if(s>e)
  89.       {return;}
  90.       if(s==e)
  91.       {tree[index]=a[s];
  92.         asli_tree[index]=a[s];
  93.     return;}
  94.  
  95.       builtTree(s,(s+e)/2,a,tree,asli_tree,index*2);
  96.       builtTree((s+e)/2+1,e,a,tree,asli_tree,index*2+1);
  97.  
  98.       tree[index]=Math.max(tree[2*index],tree[2*index+1]);
  99.       asli_tree[index]=Math.max(tree[2*index]+tree[2*index+1],Math.max(asli_tree[2*index],asli_tree[2*index+1]));
  100.  
  101.     }
  102.    public static int query(int qs,int qe,int s,int e,int tree[],int asli_tree[],int index,int i){
  103.       if(qs>e || qe<s)
  104.       {return 0;}
  105.       if(qs<=s && qe>=e && i==0) 
  106.       {return tree[index];}
  107.       if(qs<=s && qe>=e && i==1) 
  108.       {return asli_tree[index];}
  109.       int left=query(qs,qe,s,(s+e)/2,tree,asli_tree,index*2,0);//tree
  110.       int left1=query(qs,qe,s,(s+e)/2,tree,asli_tree,index*2,1);//asli_tree
  111.       int right=query(qs,qe,(s+e)/2+1,e,tree,asli_tree,index*2+1,0);
  112.       int right1=query(qs,qe,(s+e)/2+1,e,tree,asli_tree,index*2+1,1);
  113.  
  114.       if(index!=1 && i==0)
  115.       {return Math.max(left,right);}
  116.       if(index!=1 && i==1)
  117.       {return Math.max(left+right,Math.max(left1,right1));}
  118.       return Math.max(left+right,Math.max(left1,right1));
  119.     } 
  120.    public static void update(int value,int i,int s,int e,int tree[],int asli_tree[],int index){
  121.       if(i<s || i>e)
  122.       {return;}
  123.       if(s==e)
  124.       {tree[index]=value;
  125.         asli_tree[index]=value;
  126.     return;}
  127.       update(value,i,s,(s+e)/2,tree,asli_tree,index*2);
  128.       update(value,i,(s+e)/2+1,e,tree,asli_tree,index*2+1);
  129.       tree[index]=Math.max(tree[2*index],tree[2*index+1]);
  130.       asli_tree[index]=Math.max(tree[2*index]+tree[2*index+1],Math.max(asli_tree[2*index],asli_tree[2*index+1]));
  131.     }
  132. }
Success #stdin #stdout 0.1s 32740KB
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/RYB3HY
problem KGSS, based on SPOJ submission 26302863 (JAVA), 2020-07-19 14:58:48
language:
Java (HotSpot 12)
created:
3 years ago
visibility:
secret

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!