fork download
copy 
  1. import java.util.*;
  2. public class Main {
  3.     public static void main(String args[]) {
  4.         Scanner s=new Scanner(System.in);
  5.         int n=s.nextInt();
  6.         int q=s.nextInt();
  7.         int[] arr=new int[n+1];
  8.         for(int i=1;i<=n;i++){
  9.             arr[i]=s.nextInt();
  10.         }
  11.         int[] tree=new int[4*n+1];
  12.         buildTree(arr,1,n,tree,1);
  13.         while(q-->0){
  14.             int what=s.nextInt();
  15.             if(what==1){
  16. int l=s.nextInt();
  17. int r=s.nextInt();
  18. int min=query(arr,1,n,l,r,tree,1);
  19. System.out.println(min);
  20.             }else{
  21. int x=s.nextInt();
  22. int y=s.nextInt();
  23. updateNode(tree,1,n,x,y,1);
  24.             }
  25.         }
  26.  
  27.  
  28.     }
  29.  
  30.     public static void buildTree(int[] arr,int s,int e,int[] tree,int index){
  31.         if(s==e){
  32.             tree[index]=arr[s];
  33.             return;
  34.         }
  35.         int mid=(s+e)/2;
  36.         buildTree(arr,s,mid,tree,2*index);
  37.         buildTree(arr,mid+1,e,tree,2*index+1);
  38.         tree[index]=Math.min(tree[2*index],tree[2*index+1]);
  39.         return;
  40.     }
  41.  
  42.     public static int query(int[] arr,int ss,int se,int qs,int qe,int[] tree,int index){
  43.         //complete
  44.         if(qs<=ss && qe>=se){
  45.             return tree[index];
  46.         }
  47. //no overlap
  48. if(ss>qe || se<qs)
  49. return Integer.MAX_VALUE;
  50. //partial
  51. int mid=(ss+se)/2;
  52. int left=query(arr,ss,mid,qs,qe,tree,2*index);
  53. int right=query(arr,mid+1,se,qs,qe,tree,2*index+1);
  54. return Math.min(left,right);
  55.     }
  56.     public static void updateNode(int[] tree,int ss,int se,int i,int increment,int index){
  57. //no overlap
  58. if(i<ss || i>se)
  59. return;
  60. //complete
  61. if(ss==se){
  62. tree[index]+=increment;
  63. return;
  64. }
  65. //partial
  66. int mid=(ss+se)/2;
  67. updateNode(tree,ss,mid,i,increment,2*index);
  68. updateNode(tree,mid+1,se,i,increment,2*index+1);
  69.  tree[index]=Math.min(tree[2*index],tree[2*index+1]);
  70.  return;
  71.     }
  72. }
  73.  
  74.  
  75.  
Runtime error #stdin #stdout #stderr 0.11s 35172KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Exception in thread "main" java.util.NoSuchElementException
	at java.base/java.util.Scanner.throwFor(Scanner.java:937)
	at java.base/java.util.Scanner.next(Scanner.java:1594)
	at java.base/java.util.Scanner.nextInt(Scanner.java:2258)
	at java.base/java.util.Scanner.nextInt(Scanner.java:2212)
	at Main.main(Main.java:5)
https://ideone.com/rIYEp2
language:
Java (HotSpot 12)
created:
5 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!