Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- ```java
- public class CSESRangeQuery {
- int[] facts, logic; int n, m; int[] a;
- public void solve(int testNumber, FastScanner br, PrintWriter pw) {
- n = br.nextInt(); m = br.nextInt(); a = br.nextIntArray(n);
- facts = new int[4*n]; logic = new int[4*n]; //logic is lazy
- build(0,0,n-1);
- for(int i = 0; i < m; i++){
- int qt = br.nextInt();
- if(qt == 1){
- int ql = br.nextInt(); int qr = br.nextInt(); int qv = br.nextInt();
- update(0,0,n-1,ql,qr,qv);
- }
- else{
- int ind = br.nextInt();
- pw.println(query(0,0,n-1,ind));
- }
- }
- pw.close();
- }
- public void build(int v, int l, int r){
- if(l == r){
- facts[v] = a[l];
- }
- else{
- int m = (l+r)/2;
- build(2*v+1, l, m);
- build(2*v+2, m+1, r);
- facts[v] = facts[2*v+1] + facts[2*v+2];
- }
- }
- public int query(int v, int l, int r, int qi){
- if(l > qi || r < qi){
- return 0;
- }
- if(logic[v] != 0){
- facts[v] += logic[v];
- if(l != r){
- logic[2*v+1] += ((r - l + 1) * logic[v]);
- logic[2*v+2] += ((r - l +1) * logic[v]);
- }
- logic[v] = 0;
- }
- if(l == r){
- return facts[v];
- }
- int m = (l+r)/2;
- int a = query(2*v+1, l, m, qi);
- int b = query(2*v+1, m+1, r, qi);
- return a + b;
- }
- public void update(int v, int l, int r, int ql, int qr, int x){
- if(logic[v] != 0){
- facts[v] += ((r - l + 1) * logic[v]);
- if(l != r){
- logic[2*v+1] += logic[v];
- logic[2*v+2] += logic[v];
- }
- logic[v] = 0;
- }
- if(l > qr || r < ql){
- return;
- }
- if(l >= ql && r <= qr){
- facts[v] += ((r - l + 1) * x);
- if(l != r){
- logic[2*v+1] += x;
- logic[2*v+2] += x;
- }
- return;
- }
- }
- ```
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement