fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Tree
  9. {
  10. 	long left;
  11. 	long right;
  12. 	long sum;
  13. 	long max;
  14.  
  15. 	public Tree()
  16. 	{
  17. 		this.left=this.right=this.sum=this.max=Integer.MIN_VALUE;
  18. 	}	
  19. 	public Tree(long val)
  20. 	{
  21. 		this.left=this.right=this.sum=this.max=val;
  22. 	}	
  23. 	public void setval(long val)
  24. 	{
  25. 		this.left=this.right=this.sum=this.max=val;
  26. 	}
  27. 	public void merge(Tree left,Tree right)
  28. 	{
  29. 		this.sum=left.sum+ right.sum;
  30. 		this.right=Math.max(right.right, right.sum+left.right);
  31. 		this.left=Math.max(left.left, left.sum+right.left);
  32. 		this.max=Math.max(Math.max(left.max, right.max),
  33. 				left.right+right.left);
  34.  
  35. 	}	
  36. }
  37.  
  38. class Ideone
  39. {
  40.     static long a[];
  41.     static Tree[] tree;    
  42.     static PrintWriter out;
  43.  
  44.  
  45.    public static void build(int node,int start,int end)
  46.    {
  47. 	   int mid=(start+end)>>1;
  48.  
  49. 	   if(start==end)
  50. 	   {
  51. 		   tree[node]=new Tree(a[start]);
  52. 		   return;
  53. 	   }
  54.  
  55. 	   build(node<<1,start,mid);
  56. 	   build(node<<1 + 1,mid+1,end);
  57.  
  58. 	   tree[node]=new Tree();
  59. 	   tree[node].merge(tree[node<<1], tree[node<<1 + 1]);
  60.    }
  61.  
  62.    public static Tree query(int node,int start,int end,int l ,int r)
  63.    {
  64. 	   int mid=(start+end)>>1;
  65.  
  66. 	   if(start >=l && end<=r) return tree[node];
  67. 	   else if(start > r || end<l) return null;
  68.  
  69. 	   Tree left=null, right=null;
  70.  
  71. 	   if(l<=mid) 
  72. 		   left=query(node<<1,start,mid,l,r);
  73. 	   if(r>mid)
  74. 		   right=query(node<<1 + 1,mid+1,end,l,r);
  75.  
  76. 	   if(left==null) return right;
  77. 	   if(right==null) return left;
  78.  
  79. 	   Tree t=new Tree();
  80. 	   t.merge(left, right);
  81.  
  82. 	   return t;
  83.    }
  84.  
  85.    public static void update(int node,int start,int end, int index,int val)
  86.    {
  87. 	   int mid=(start+end)>>1;
  88.  
  89. 	   if(start==end) {tree[node].setval(val); return;}
  90.  
  91. 	   if(index>=start && index<=mid) update(node<<1,start,mid,index,val);
  92. 	   if(index > mid && index<=end) update(node<<1 + 1,mid+1,end,index,val);
  93.  
  94. 	   tree[node].merge(tree[node<<1],tree[node<<1 + 1]);
  95.    }
  96.  
  97.    public static void main(String[] args) throws java.lang.Exception
  98.    {	  	         
  99.        InputStream inputStream = System.in;
  100.        OutputStream outputStream = System.out;
  101.        InputReader s = new InputReader(inputStream);
  102.  
  103.        int n=s.nextInt(); 
  104.        a=new long[n+1];
  105.  
  106.        tree= new Tree[10000000];
  107.  
  108.        for(int i=1;i<=n;i++)
  109.             a[i]=s.nextLong();
  110.  
  111.        build(1,1,n);
  112.  
  113.        int q=s.nextInt();
  114.        while(q!=0)
  115.        {
  116.     	    int w=s.nextInt();
  117.     	    if(w==1)
  118.     	    {
  119.  
  120.   	    int l=s.nextInt();    	    
  121.     	    int r=s.nextInt();
  122.     	    Tree x=query(1,1,n,l,r); 	    
  123.     	    System.out.println(x.max);
  124.  
  125.     	    }
  126.     	    else
  127.     	    {
  128.     	    	int index=s.nextInt();
  129.     	    	int val=s.nextInt();
  130.     	    	update(1,1,n,index,val);
  131.     	    }
  132.     	    q--;
  133.        }      	 
  134.        }
  135.  
  136.    static class InputReader {
  137.        public BufferedReader reader;
  138.        public StringTokenizer tokenizer;
  139.  
  140.        public InputReader(InputStream stream) {
  141.            reader = new BufferedReader(new InputStreamReader(stream), 32768);
  142.            tokenizer = null;
  143.        }
  144.  
  145.        public String next() {
  146.            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  147.                try {
  148.                    tokenizer = new StringTokenizer(reader.readLine());
  149.                } catch (IOException e) {
  150.                    throw new RuntimeException(e);
  151.                }
  152.            }
  153.            return tokenizer.nextToken();
  154.        }
  155.  
  156.        public int nextInt() {
  157.            return Integer.parseInt(next());
  158.        }
  159.  
  160.        public long nextLong() {
  161.            return Long.parseLong(next());
  162.        }
  163.    }
  164. }
  165.  
Success #stdin #stdout 0.11s 66820KB
comments (?)
stdin
copy 
10 
-200 -3 -4 -200 6 2 4 -200 5 6 
1 
1 1 10
stdout
copy 
12
https://ideone.com/lFTHXl
language:
Java (HotSpot 12)
created:
6 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!