fork download
copy 
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.StringTokenizer;
  5.  
  6. class FastReader {
  7.     BufferedReader br;
  8.     StringTokenizer st;
  9.  
  10.     public FastReader() {
  11.         br = new BufferedReader(new InputStreamReader(System.in));
  12.     }
  13.  
  14.     String next() throws IOException {
  15.         while (st == null || !st.hasMoreElements()) {
  16.             st = new StringTokenizer(br.readLine());
  17.         }
  18.         return st.nextToken();
  19.     }
  20.  
  21.     int nextInt() throws IOException {
  22.         return Integer.parseInt(next());
  23.     }
  24.  
  25.     long nextLong() throws IOException {
  26.         return Long.parseLong(next());
  27.     }
  28.  
  29.     double nextDouble() throws IOException {
  30.         return Double.parseDouble(next());
  31.     }
  32.  
  33.     String nextLine() throws IOException{
  34.         return br.readLine();
  35.     }
  36. }
  37.  
  38. class Main{
  39.  
  40.     static class pair{
  41.         long val;
  42.         long type;
  43.         pair(long val, long type){
  44.             this.val = val;
  45.             this.type = type;
  46.         }
  47.     }
  48.     static long[][] segmentArray;
  49.     static pair[] lazyArray;
  50.     static int[] ar;
  51.  
  52.     public static void build(int ind, int l, int r){
  53.         if( l == r){
  54.             segmentArray[ind][0] = (long) ar[l] * ar[l];
  55.             segmentArray[ind][1] = ar[l];
  56.             return;
  57.         }
  58.         int mid = (l+r)/2;
  59.         build(2*ind+1, l, mid);
  60.         build(2*ind+2, mid+1, r);
  61.  
  62.         segmentArray[ind][0] = segmentArray[2*ind+1][0] + segmentArray[2*ind+2][0];
  63.         segmentArray[ind][1] = segmentArray[2*ind+1][1] + segmentArray[2*ind+2][1];
  64.     }
  65.  
  66.     public static long find(int ind, long l, long r, int lr, int rr){
  67.  
  68.         if( lazyArray[ind] != null ){
  69.             pair temp = lazyArray[ind];
  70.             if( temp.type == 1){
  71.                 segmentArray[ind][0] += (r-l+1) * temp.val * temp.val + 2 * temp.val * segmentArray[ind][1];
  72.                 segmentArray[ind][1] += (r - l + 1) * temp.val;
  73.             }
  74.             else{
  75.                 segmentArray[ind][0] = (r-l+1) * temp.val * temp.val;
  76.                 segmentArray[ind][1] = (r - l + 1) * temp.val;
  77.             }
  78.             if( l != r){
  79.                 helper(2*ind+1, temp.val, temp.type);
  80.                 helper(2*ind+2, temp.val, temp.type);
  81.             }
  82.             lazyArray[ind] = null;
  83.         }
  84.  
  85.         if( r < lr || rr < l || l > r)
  86.             return 0;
  87.  
  88.         if( l >= lr && r <= rr)
  89.             return segmentArray[ind][0];
  90.  
  91.         long mid = (r+l)/2;
  92.         return find(2*ind+1, l, mid, lr, rr ) + find(2*ind+2, mid+1, r, lr, rr);
  93.     }
  94.  
  95.     private static void update(int ind, long l, long r, int u, int v, int val, int type) {
  96.  
  97.         if( lazyArray[ind] != null ){
  98.             pair temp = lazyArray[ind];
  99.             if( temp.type == 1){
  100.                 segmentArray[ind][0] += (r - l + 1) * temp.val* temp.val + 2 * temp.val * segmentArray[ind][1];
  101.                 segmentArray[ind][1] += (r - l + 1) * temp.val;
  102.             }
  103.             else{
  104.                 segmentArray[ind][0] = (r - l + 1) * temp.val* temp.val;
  105.                 segmentArray[ind][1] = (r - l + 1) * temp.val;
  106.             }
  107.             if( l != r){
  108.                 helper(2*ind+1, temp.val, temp.type);
  109.                 helper(2*ind+2, temp.val, temp.type);
  110.             }
  111.             lazyArray[ind] = null;
  112.         }
  113.  
  114.         if( l >= u && r <= v){
  115.             if( type == 1){
  116.                 segmentArray[ind][0] += (r - l + 1) * val * val + 2 * val * segmentArray[ind][1];
  117.                 segmentArray[ind][1] += (r - l + 1) * val;
  118.             }
  119.             else{
  120.                 segmentArray[ind][0] = (r - l + 1) * val * val;
  121.                 segmentArray[ind][1] = (r - l + 1) * val;
  122.             }
  123.             if( l != r){
  124.                 helper(2*ind+1, val, type);
  125.                 helper(2*ind+2, val, type);
  126.             }
  127.             return;
  128.         }
  129.  
  130.         if( r < u || v < l || l > r)
  131.             return;
  132.  
  133.         long mid = (r+l)/2;
  134.         update(2*ind+1, l, mid, u, v, val, type);
  135.         update(2*ind+2, mid+1, r, u, v, val, type);
  136.  
  137.         segmentArray[ind][0] = segmentArray[2*ind+1][0] + segmentArray[2*ind+2][0];
  138.         segmentArray[ind][1] = segmentArray[2*ind+1][1] + segmentArray[2*ind+2][1];
  139.     }
  140.  
  141.     public static void helper(int i, long pre_val, long pre_type) {
  142.         if( lazyArray[i] == null){
  143.             lazyArray[i] = new pair(pre_val, pre_type);
  144.         }
  145.         else {
  146.             pair next = lazyArray[i];
  147.             if (pre_type == 1 && (next.type == 1 || next.type == 0)) {
  148.                 next.val = pre_val + next.val;
  149.             } else {
  150.                 next.type = 0;
  151.                 next.val = pre_val;
  152.             }
  153.         }
  154.     }
  155.  
  156.     public static void main(String[] args) throws IOException {
  157.         FastReader ff = new FastReader();
  158.         int t = ff.nextInt();
  159.         for(int x =1; x <= t; x++) {
  160.             System.out.println("Case " +x + ":");
  161.             int n = ff.nextInt();
  162.             int q = ff.nextInt();
  163.             segmentArray = new long[4 * n + 5][2];
  164.             lazyArray = new pair[4 * n + 5];
  165.             ar = new int[n];
  166.  
  167.             for(int i =0; i < n; i++){
  168.                 ar[i] = ff.nextInt();
  169.             }
  170.  
  171.             build(0, 0, n - 1);
  172.             while(q-- > 0) {
  173.                 int op = ff.nextInt();
  174.                 int u = ff.nextInt()-1;
  175.                 int v = ff.nextInt()-1;
  176.                 if (op == 2) {
  177.                     System.out.println((int) find(0, 0, n - 1, u, v));
  178.                 }
  179.                 else {
  180.                     int val = ff.nextInt();
  181.                     update(0, 0, n - 1, u, v, val, op);
  182.                 }
  183.             }
  184.         }
  185.     }
  186. }
Success #stdin #stdout 0.1s 50588KB
comments (?)
stdin
copy 
2
4 5
1 2 3 4
2 1 4
0 3 4 1
2 1 4
1 3 4 1
2 1 4
1 1
1
2 1 1
stdout
copy 
Case 1:
30
7
13
Case 2:
1
https://ideone.com/xsxZSw
problem SEGSQRSS, based on SPOJ submission 28088046 (JAVA), 2021-06-21 08:26:11
language:
Java (HotSpot 12)
created:
2 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!