fork download
copy 
  1. import java.util.*;
  2. import java.io.*; 
  3. import java.text.*;
  4.  
  5. public class Main{
  6.     //SOLUTION BEGIN
  7.     void solve(int TC) throws Exception{
  8.         int n = ni(), q = ni();
  9.         long[] a = new long[n], b = new long[n];
  10.         for(int i = 0; i< n; i++)a[i] = nl();
  11.         for(int i = 0; i< n; i++)b[i] = nl();
  12.         int B = 200;
  13.         int C = (n+B-1)/B;
  14.         Block[] bucket = new Block[C];//Square root Decomposition
  15.         for(int i = 0; i< C; i++){
  16.             bucket[i] = new Block(B);
  17.             for(int j = i*B; j< Math.min(n, (i+1)*B); j++)
  18.                 bucket[i].add(new Line(b[j], a[j], j));//Adding lines with slope b[j] and constant a[j] to ith bucket
  19.             bucket[i].build();//explained below
  20.         }
  21.         for(int qq = 0; qq<q; qq++){
  22.             int t = ni(), l = ni()-1, r = ni()-1;
  23.             int sb = l/B, eb = r/B;
  24.             if(t==1){
  25.                 long ans;
  26.                 if(sb==eb)ans = bucket[sb].getMax(l, r);//Since l and r are in same block, it is calculated in O(B).
  27.                 else{
  28.                     ans = Math.max(bucket[sb].getMax(l, sb*B+B-1), bucket[eb].getMax(eb*B, r));//Queried border blocks.
  29.                     for(int i = sb+1;i<eb; i++)ans = Math.max(ans, bucket[i].getMax());//Queried intermediate blocks.
  30.                 }
  31.                 pn(ans);
  32.             }else if(t==2){
  33.                 if(sb==eb)bucket[sb].incrementAB(l,r);//Since it affects a part of one block only.
  34.                 else{
  35.                     //Updating border blocks
  36.                     bucket[sb].incrementAB(l,sb*B+B-1);
  37.                     bucket[eb].incrementAB(eb*B, r);
  38.                     for(int i = sb+1; i< eb; i++)//Updating intermediate blocks
  39.                         bucket[i].incrementAB();
  40.                 }
  41.             }else if(t==4){
  42.                 long x = nl();
  43.                 if(sb==eb)bucket[sb].incrementA(l,r,x);//Since it affects a part of one block only.
  44.                 else{
  45.                     //Updating border blocks
  46.                     bucket[sb].incrementA(l,sb*B+B-1,x);
  47.                     bucket[eb].incrementA(eb*B,r,x);
  48.                     for(int i = sb+1; i< eb; i++)//Updating intermediate blocks
  49.                         bucket[i].incrementA(x);
  50.                 }
  51.             }else if(t==3){
  52.                 long x = nl();
  53.                 if(sb==eb)bucket[sb].incrementB(l,r,x);//Since it affects a part of one block only.
  54.                 else{
  55.                     //Updating border blocks
  56.                     bucket[sb].incrementB(l,sb*B+B-1,x);
  57.                     bucket[eb].incrementB(eb*B,r,x);
  58.                     for(int i = sb+1; i< eb; i++)//Updating intermediate blocks
  59.                         bucket[i].incrementB(x);
  60.                 }
  61.             }
  62.         }
  63.     }
  64.     //Class line represent a position p as line with slope b[p] and coefficent a[i]
  65.     class Line implements Comparable<Line>{
  66.         long m, c;
  67.         int pos;
  68.         public Line(long M, long C, int ind){m = M;c = C;pos = ind;}
  69.         long eval(long x){return m*x+c;}
  70.         public int compareTo(Line l){
  71.             //Sorting blocks in increasing order of slopes
  72.             if(m!=l.m)return Long.compare(m, l.m);
  73.             return Long.compare(c, l.c);//If slopes equal, sorted in order of coefficients.
  74.         }
  75.     }
  76.     //Calculates intersection point of two lines, rounded to the next integet value.
  77.     //This intersection function works only if l1.compareTo(l2) <= 0 as per above method.
  78.     long intersection(Line l1, Line l2){
  79.         if(l1.m==l2.m && l1.c<l2.c)return IINF+1;//Never intersect
  80.         if(l1.c>=l2.c)return 0;//because these lines will never intersect, according to our sorting
  81.         long a = l2.c-l1.c, b = l1.m-l2.m;
  82.         return (a+b-1)/b;//Rounded up
  83.     }
  84.  
  85.     class Block{
  86.         //q_cnt - Number of times B was added to A after last updateBlock. cur_max - our index of the line having maximum value at value q_cnt.
  87.         int q_cnt, cur_max;
  88.         //coefAdd - Sum of all increments by query type 4 to array A, since last update
  89.         //slopeAdd - Sum of all increments by query of type 3 to array B, since last update
  90.         //slopeEffect, Sum of combined effect of type 2 operation on array A, since last update.
  91.         long coefAdd, slopeAdd, slopeEffect;
  92.         int lsize = 0, hsize = 0, isize = 0;//Sizes of following arrays
  93.         Line[] lines, hull;
  94. //        ArrayList<Line> lines, hull;
  95.         long[] intersections;
  96. //        ArrayList<Long> intersections;
  97.         public Block(int SIZE){
  98.             lines = new Line[SIZE];hull = new Line[SIZE];
  99.             intersections = new long[SIZE];
  100. //            lines = new ArrayList<>();hull = new ArrayList<>();
  101. //            intersections = new ArrayList<>();
  102.             q_cnt = cur_max = 0;
  103.             coefAdd = slopeAdd = slopeEffect = 0;
  104.         }
  105.         //Adds line to block, used during preprocessing only
  106.         void add(Line l){lines[lsize++] = l;}
  107.         //Initialisation function, Sort the lines for hull and create initial convex hull
  108.         void build(){
  109.             Arrays.sort(lines, 0, lsize);
  110.             convexhull();
  111.         }
  112.         //Build can be used, but will add a factor of log(blocksize) to complexity.
  113.         //This is called, when slopes of segment [l,r] are increased by X.ie Increment on B is done on [l,r]. It preserves the sorting order of lines, required for Convex hull.
  114.         //Since Hull is required to be rebuilt after this sorting, it is always called whenever updateBlockBySlope is called.
  115.         void updateBlockBySlope(int l, int r){
  116.             ArrayList<Line> v1 = new ArrayList<>(), v2 = new ArrayList<>();
  117.             for(int i = 0; i< lsize; i++){
  118.                 if(lines[i].pos>=l && lines[i].pos<=r)v1.add(lines[i]);
  119.                 else v2.add(lines[i]);
  120.             }
  121.             int b = lsize;
  122.             lsize = 0;
  123.             for(int i1 = 0, i2 = 0; i1+i2<b;){
  124.                 if(i1==v1.size())lines[lsize++] = v2.get(i2++);
  125.                 else if(i2==v2.size())lines[lsize++] = v1.get(i1++);
  126.                 else{
  127.                     boolean f = true;
  128.                     if(v1.get(i1).m>v2.get(i2).m || (v1.get(i1)==v2.get(i2) && v1.get(i1).c>v2.get(i2).c))f = false;
  129.                     if(f)lines[lsize++] = v1.get(i1++);
  130.                     else lines[lsize++] = v2.get(i2++);
  131.                 }
  132.             }
  133.         }
  134.         //Updates the lines in whole block
  135.         void updateBlock(){
  136.             for(int i = 0; i< lsize; i++){
  137.                 lines[i].c += coefAdd + lines[i].m*q_cnt+slopeEffect;//Added effect of b[i]* number of times operation 2 performed
  138.                 //plus added combined effect of operation 3 for every increare in array B before every operation 2 since last update
  139.                 lines[i].m+=slopeAdd;//Simply added effect of type 3 operation to slope
  140.             }
  141.             //Resetting
  142.             q_cnt = 0;
  143.             coefAdd = 0;slopeAdd = 0;slopeEffect = 0;
  144.         }
  145.         //Makes convex hull from lines. Simple variant convex hull is used as lines have slopes sorted.
  146.         //Refer Wiki page mentioned in editorial for details.
  147.         void convexhull(){
  148.             isize = 0;hsize = 0;
  149.             cur_max = 0;//Current best pointer is reset, since hull is being rebuild. 
  150.             for(int i = 0; i< lsize; i++){
  151.                 while(hsize>=2 && intersection(lines[i], hull[hsize-1]) <= intersections[isize-1]){
  152.                     hsize--;
  153.                     isize--;
  154.                 }
  155.                 boolean add = true;
  156.                 if(hsize>0)
  157.                     if(intersection(lines[i], hull[hsize-1])>IINF)
  158.                         add = false;
  159.                 if(add){
  160.                     if(hsize>0)
  161.                         intersections[isize++] = intersection(lines[i], hull[hsize-1]);
  162.                     hull[hsize++] = lines[i];
  163.                 }
  164.             }
  165.         }
  166.         //Range l to r has been modified. O(B) complexity.
  167.         //If slopes are changed, UpdateBlockBySlope is needed.
  168.         //else just rebuilding convex hull is sufficient
  169.         void update(int l, int r, boolean reorder){
  170.             if(reorder)updateBlockBySlope(l,r);//Ensures sorted order of lines, for convex hull
  171.             convexhull();//Rebuilding convex hull
  172.         }
  173.         //Returns maximum value in block
  174.         long getMax(){
  175.             //If only one line is always max in whole block.
  176.             if(isize == 0)return hull[0].eval(q_cnt)+coefAdd+slopeEffect;
  177.             //Moving our current pointer to best line, the line having maximum value at q_cnt
  178.             while(cur_max<isize && q_cnt>=intersections[cur_max])
  179.                 cur_max++;
  180.             return hull[cur_max].eval(q_cnt)+coefAdd+slopeEffect;
  181.         }
  182.         //Returns max in range
  183.         long getMax(int l, int r){
  184.             long ans = -IINF;
  185.             for(int i = 0; i< lsize; i++)
  186.                 if(lines[i].pos>=l && lines[i].pos<=r)
  187.                     ans = Math.max(ans, lines[i].eval(q_cnt)+coefAdd+slopeEffect);
  188.             return ans;
  189.         }
  190.         void incrementAB(){
  191.             //The array B is added to array A, so increased query point by 1.
  192.             //So, suppose q_cnt was 0. For any line, query(0) would return line.c which is a[i].
  193.             //Now, after increasing q_cnt by 1, we make call to query(1), which returns m+c, ie b[i]+a[i], Thus, performing 2nd operation on whole block.
  194.             q_cnt++;
  195.             //The increase in B made since last update, will be added to A,
  196.             //So, we add the increase in B to slopeEffect
  197.             slopeEffect+=slopeAdd;
  198.         }
  199.         //Manual 2nd operation in range [l,r]
  200.         void incrementAB(int l, int r){
  201.             updateBlock();//All lines are updated
  202.             for(int i = 0; i< lsize; i++)
  203.                 if(lines[i].pos>=l && lines[i].pos<=r)
  204.                     lines[i].c+=lines[i].m;
  205.             update(l, r, false);//Convex hull is required to be built again after change.
  206.         }
  207.         //Operation 4 on whole block.
  208.         void incrementA(long val){
  209.             coefAdd+=val;
  210.         }
  211.         //OPeration 4 in range [l,r]
  212.         void incrementA(int l, int r, long val){
  213.             updateBlock();
  214.             for(int i = 0; i< lsize; i++)
  215.                 if(lines[i].pos>=l && lines[i].pos<=r)
  216.                     lines[i].c+=val;
  217.             update(l,r,false);
  218.         }
  219.         //Operation 3 on whole block
  220.         void incrementB(long val){
  221.             slopeAdd+=val;
  222.         }
  223.         //Operation 3 in range[l,r]
  224.         void incrementB(int l, int r, long val){
  225.             updateBlock();
  226.             for(int i = 0; i< lsize; i++)
  227.                 if(lines[i].pos>=l && lines[i].pos<=r)
  228.                     lines[i].m+=val;
  229.             update(l,r,true);
  230.         }
  231.     }
  232.     //SOLUTION ENDS
  233.     long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
  234.     int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
  235.     int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
  236.     void p(Object o){out.print(o);}
  237.     void pn(Object o){out.println(o);}
  238.     void pni(Object o){out.println(o);out.flush();}
  239.     String n(){return in.next();}
  240.     String nln(){return in.nextLine();}
  241.     int ni(){return Integer.parseInt(in.next());}
  242.     long nl(){return Long.parseLong(in.next());}
  243.     double nd(){return Double.parseDouble(in.next());}
  244.  
  245.     class FastReader{
  246.         BufferedReader br;
  247.         StringTokenizer st;
  248.         public FastReader(){
  249.             br = new BufferedReader(new InputStreamReader(System.in));
  250.         }
  251.  
  252.         public FastReader(String s) throws Exception{
  253.             br = new BufferedReader(new FileReader(s));
  254.         }
  255.  
  256.         String next(){
  257.             while (st == null || !st.hasMoreElements()){
  258.                 try{
  259.                     st = new StringTokenizer(br.readLine());
  260.                 }catch (IOException  e){
  261.                     e.printStackTrace();
  262.                 }
  263.             }
  264.             return st.nextToken();
  265.         }
  266.  
  267.         String nextLine(){
  268.             String str = "";
  269.             try{    
  270.                 str = br.readLine();
  271.             }catch (IOException e){
  272.                 e.printStackTrace();
  273.             }   
  274.             return str;
  275.         }
  276.     }
  277.     long mod = (int)1e9+7, IINF = (long)1e18;
  278.     final int MAX = (int)1e4+1, INF = (int)1e9, root = 3;
  279.     DecimalFormat df = new DecimalFormat("0.00000000");
  280.     double PI = 3.141592653589793238462643383279502884197169399375105820974944;
  281.     static boolean multipleTC = false, memory = true;
  282.     FastReader in;PrintWriter out;
  283.     public static void main(String[] args) throws Exception{
  284.         if(memory)new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
  285.         else new Main().run();
  286.     }
  287.     void run() throws Exception{
  288.         in = new FastReader();
  289.         out = new PrintWriter(System.out);
  290.         for(int i = 1, T= (multipleTC)?ni():1; i<= T; i++)solve(i);
  291.         out.flush();
  292.         out.close();
  293.     }
  294. }
Success #stdin #stdout 0.11s 29344KB
comments ()
stdin
copy 
3 6
1 4 2
3 1 2
1 1 3
2 1 3
3 1 1 -2
2 1 3
4 1 2 3
1 1 2
stdout
copy 
4
9
https://ideone.com/wAtSf8
language:
Java (HotSpot 12)
created:
6 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!