Advertisement
Guest User

Untitled

a guest
Jun 18th, 2019
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.15 KB | None | 0 0
  1. ```java
  2. public class CSESRangeQuery {
  3.     int[] facts, logic; int n, m; int[] a;
  4.     public void solve(int testNumber, FastScanner br, PrintWriter pw) {
  5.         n = br.nextInt(); m = br.nextInt(); a = br.nextIntArray(n);
  6.         facts = new int[4*n]; logic = new int[4*n]; //logic is lazy
  7.         build(0,0,n-1);
  8.         for(int i = 0; i < m; i++){
  9.             int qt = br.nextInt();
  10.             if(qt == 1){
  11.                 int ql = br.nextInt(); int qr = br.nextInt(); int qv = br.nextInt();
  12.                 update(0,0,n-1,ql,qr,qv);
  13.             }
  14.             else{
  15.                 int ind = br.nextInt();
  16.                 pw.println(query(0,0,n-1,ind));
  17.             }
  18.         }
  19.         pw.close();
  20.     }
  21.     public void build(int v, int l, int r){
  22.         if(l == r){
  23.             facts[v] = a[l];
  24.         }
  25.         else{
  26.             int m = (l+r)/2;
  27.             build(2*v+1, l, m);
  28.             build(2*v+2, m+1, r);
  29.             facts[v] = facts[2*v+1] + facts[2*v+2];
  30.         }
  31.     }
  32.     public int query(int v, int l, int r, int qi){
  33.         if(l > qi || r < qi){
  34.             return 0;
  35.         }
  36.         if(logic[v] != 0){
  37.             facts[v] += logic[v];
  38.             if(l != r){
  39.                 logic[2*v+1] += ((r - l + 1) * logic[v]);
  40.                 logic[2*v+2] += ((r - l +1) * logic[v]);
  41.             }
  42.             logic[v] = 0;
  43.         }
  44.         if(l == r){
  45.             return facts[v];
  46.         }
  47.         int m = (l+r)/2;
  48.         int a = query(2*v+1, l, m, qi);
  49.         int b = query(2*v+1, m+1, r, qi);
  50.         return a + b;
  51.     }
  52.  
  53.     public void update(int v, int l, int r, int ql, int qr, int x){
  54.         if(logic[v] != 0){
  55.             facts[v] += ((r - l + 1) * logic[v]);
  56.             if(l != r){
  57.                 logic[2*v+1] += logic[v];
  58.                 logic[2*v+2] += logic[v];
  59.             }
  60.             logic[v] = 0;
  61.         }
  62.         if(l > qr || r < ql){
  63.             return;
  64.         }
  65.         if(l >= ql && r <= qr){
  66.             facts[v] += ((r - l + 1) * x);
  67.             if(l != r){
  68.                 logic[2*v+1] += x;
  69.                 logic[2*v+2] += x;
  70.             }
  71.             return;
  72.         }
  73.     }
  74. ```
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement