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];
  8.         for(int i=0;i<n;i++){
  9.             arr[i]=s.nextInt();
  10.         }
  11.         int[] tree=new int[4*n+1];
  12.         buildTree(arr,0,n-1,tree,1);
  13.  
  14.         while(q-->0){
  15.             int what=s.nextInt();
  16.             if(what==1){
  17.                 int l=s.nextInt();
  18.                 int r=s.nextInt();
  19.                 int min=query(arr,0,n-1,l,r,tree,1);
  20.                 System.out.println(min);
  21.             }else{
  22.                 int x=s.nextInt();
  23.                 int y=s.nextInt();
  24.                 updateNode(tree,0,n-1,x,y,1);
  25.             }
  26.         }
  27.  
  28.  
  29.     }
  30.  
  31.     public static void buildTree(int[] arr,int s,int e,int[] tree,int index){
  32.         if(s==e){
  33.             tree[index]=arr[s];
  34.             return;
  35.         }
  36.         int mid=(s+e)/2;
  37.         buildTree(arr,s,mid,tree,2*index);
  38.         buildTree(arr,mid+1,e,tree,2*index+1);
  39.         tree[index]=Math.min(tree[2*index],tree[2*index+1]);
  40.         return;
  41.     }
  42.  
  43.     public static int query(int[] arr,int ss,int se,int qs,int qe,int[] tree,int index){
  44.         //complete
  45.         if(qs<=ss && qe>=se){
  46.             return tree[index];
  47.         }
  48. //no overlap
  49. if(ss>qe || se<qs)
  50. return Integer.MAX_VALUE;
  51. //partial
  52. int mid=(ss+se)/2;
  53. int left=query(arr,ss,mid,qs,qe,tree,2*index);
  54. int right=query(arr,mid+1,se,qs,qe,tree,2*index+1);
  55. return Math.min(left,right);
  56.     }
  57.     public static void updateNode(int[] tree,int ss,int se,int i,int increment,int index){
  58. //no overlap
  59. if(i<ss || i>se)
  60. return;
  61. //complete
  62. if(ss==se){
  63. tree[index]+=increment;
  64. return;
  65. }
  66. //partial
  67. int mid=(ss+se)/2;
  68. updateNode(tree,ss,mid,i,increment,2*index);
  69. updateNode(tree,mid+1,se,i,increment,2*index+1);
  70.  tree[index]=Math.min(tree[2*index],tree[2*index+1]);
  71.  return;
  72.     }
  73. }
Runtime error #stdin #stdout #stderr 0.11s 35292KB
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/N2KPSP
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!