fork(1) download
copy 
  1. import java.io.*;
  2. import java.util.Arrays;
  3. import java.util.StringTokenizer;
  4. public class Main {
  5.     private int[] array;
  6.     private NodeI[] heap;
  7.     int size;
  8.  
  9.     public static void main(String args[]) throws IOException {
  10.         MyScanner sc = new MyScanner();
  11.         out = new PrintWriter(new BufferedOutputStream(System.out), true);
  12.  
  13.         int i = 0, N, Q, l, r;
  14.         long answer;
  15.         N = sc.nextInt();
  16.         int[] array = new int[N];
  17.         while (i < N) {
  18.             array[i++] = sc.nextInt();
  19.         }
  20.         Main gss1 = new Main(array);
  21.         Q = sc.nextInt();
  22.         i = 0;
  23.         while (i++ < Q) {
  24.             l = sc.nextInt();
  25.             r = sc.nextInt();
  26.             answer = gss1.query(1, l - 1, r - 1).getMS();
  27.             out.println(answer + "\n");
  28.         }
  29.  
  30.     }
  31.     public static PrintWriter out;
  32.     public static class MyScanner {
  33.         BufferedReader br;
  34.         StringTokenizer st;
  35.  
  36.         public MyScanner() {
  37.             br = new BufferedReader(new InputStreamReader(System.in));
  38.         }
  39.  
  40.         String next() {
  41.             while (st == null || !st.hasMoreElements()) {
  42.                 try {
  43.                     st = new StringTokenizer(br.readLine());
  44.                 } catch (IOException e) {
  45.                     e.printStackTrace();
  46.                 }
  47.             }
  48.             return st.nextToken();
  49.         }
  50.  
  51.         int nextInt() { return Integer.parseInt(next()); }
  52.     }
  53.  
  54.     class NodeI {
  55.         int from, to, len;
  56.         long pre, suf, sum, mS;
  57.  
  58.         public NodeI() {
  59.         }
  60.  
  61.         NodeI(int from, int to, int len) {
  62.             this.from = from;
  63.             this.to = to;
  64.             this.len = len;
  65.         }
  66.  
  67.         NodeI(NodeI node) {
  68.             this.from = node.from;
  69.             this.to = node.to;
  70.             this.len = node.len;
  71.             this.pre = node.pre;
  72.             this.suf = node.suf;
  73.             this.sum = node.sum;
  74.             this.mS = node.mS;
  75.         }
  76.  
  77.         long getMS() { return mS; }
  78.  
  79.         void setMS(long mS) { this.mS = mS; }
  80.  
  81.         long getSum() {
  82.             return sum;
  83.         }
  84.  
  85.         void setSum(long sum) {
  86.             this.sum = sum;
  87.         }
  88.  
  89.         long getSuf() {
  90.             return suf;
  91.         }
  92.  
  93.         void setSuf(long suf) {
  94.             this.suf = suf;
  95.         }
  96.  
  97.         void setPre(long pre) {
  98.             this.pre = pre;
  99.         }
  100.     }
  101.  
  102.     void initLeaf(int n, Integer integer) {
  103.         NodeI node = heap[n];
  104.         int index = node.from;
  105.         int value = array[index];
  106.         node.setPre(value);
  107.         node.setSuf(value);
  108.         node.setSum(value);
  109.         node.setMS(value);
  110.     }
  111.     NodeI balance(NodeI node, NodeI lft, NodeI ryt) {
  112.         node.setPre(Math.max(lft.pre, lft.getSum() + ryt.pre));
  113.         node.setSuf(Math.max(ryt.getSuf(), ryt.getSum() + lft.getSuf()));
  114.         node.setMS(Math.max(Math.max(lft.getMS(), ryt.getMS()), lft.getSuf() + ryt.pre));
  115.         node.setSum(lft.getSum() + ryt.getSum());
  116.         return node;
  117.     }
  118.     Main(int[] array) {
  119.         this.array = Arrays.copyOf(array, array.length);
  120.         this.size = ((int)Math.pow(2.0,Math.floor((Math.log((double)array.length)/Math.log(2.0))+1))<<1);
  121.         this.heap = new NodeI[this.size];
  122.         build(1, 0, array.length);
  123.     }
  124.     void build(int n, int from, int size) {
  125.         heap[n] = new NodeI(from, from + size - 1, size);
  126.         if (size == 1) {
  127.             this.initLeaf(n, array[from]);
  128.         } else {
  129.             build(n<<1, from, size >> 1);
  130.             build((n<<1)+1, from + (size >> 1), size - (size >> 1));
  131.             blnce(n);
  132.         }
  133.     }
  134.     protected NodeI blnce(int n) {
  135.         NodeI node = heap[n];
  136.         if (node.from == node.to) {
  137.             return node;
  138.         }
  139.         NodeI lft = heap[n << 1];
  140.         NodeI ryt = heap[(n<<1) + 1];
  141.         return balance(node, lft, ryt);
  142.     }
  143.     NodeI query(int n, int l, int r) {
  144.         if (l == heap[n].from && r == heap[n].to) {
  145.             return heap[n];
  146.         }
  147.         int rcFrom = heap[n].from + (heap[n].len >> 1);
  148.         if (r < rcFrom) {
  149.             return query(n << 1, l, r);
  150.         }
  151.         if (l >= rcFrom) {
  152.             return query((n << 1) + 1, l, r);
  153.         }
  154.         NodeI ln = query(n << 1, l, rcFrom - 1);
  155.         NodeI rn = query( (n << 1) + 1, rcFrom, r);
  156.         NodeI copyNode = new NodeI();
  157.         return balance(copyNode, ln, rn);
  158.     }
  159. }
  160.  
  161.  
  162.  
Success #stdin #stdout 0.05s 4575232KB
comments (?)
stdin
copy 
3 
-1 2 3
1
1 2
stdout
copy 
2
https://ideone.com/BN5ecX
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!