You are given the following queries over n elements:

Query No.1: Increase elements between a and b with value c (it's possible that c is negative).

Query No.2: Get maximal value of all elements (e.g. max(a[i]) 1<=i<=n)

#include<bits/stdc++.h>
using namespace std;
int lazy[1000],mx[1000],idx[1000];
struct node{
   int ll,rr,id;
   node(int L,int R,int X){
      ll=L;
      rr=R;
      id=X;
      lazy_update();
   }
   node left(){
      return node(ll,(ll+rr)/2,id*2);
   }
   node right(){
      return node((ll+rr)/2+1,rr,id*2+1);
   }
   void lazy_update(){
      if(lazy[id]==0)return;
      mx[id]+=lazy[id];
      if(ll!=rr){
         lazy[id*2]+=lazy[id];
         lazy[id*2+1]+=lazy[id];
      }
      lazy[id]=0;
   }
   void assign_range(int l,int r,int x){
      lazy_update();
      if(ll>r||l>rr)return;
      if(ll==rr){
         idx[id]=ll;
      }
      if(l<=ll&&rr<=r){
         lazy[id]+=x;
         lazy_update();
         return;
      }
      left().assign_range(l,r,x);
      right().assign_range(l,r,x);
      if(mx[id*2]>mx[id*2+1]){
         mx[id]=mx[id*2];
         idx[id]=idx[id*2];
      }
      else{
         mx[id]=mx[id*2+1];
         idx[id]=idx[id*2+1];
      }
   }
   int max_range(int l,int r){
      if(ll>r||l>rr)return -1e9;
      lazy_update();
      if(l<=ll&&rr<=r){
         return mx[id];
      }
      int mx1=left().max_range(l,r);
      int mx2=right().max_range(l,r);
      return max(mx1,mx2);
   }
};
int main(){
   node root(1,6,1);
   int m;
   cin>>m;
   for(int i=1;i<=m;i++){
      int a,b,c;
      cin>>a>>b>>c;
      root.assign_range(a,b,c);
      cout<<root.max_range(1,6)<<"\n";
   }
}

I managed to make a solution with segment trees using kien_coi_1997 style, but it doesn't work properly. My idea is the following: when a interval (ll,rr) fits in the query interval, increase the maximum with c and update all nodes of the tree up to the root. I'm not sure when I need to put lazy_update and therefore i got WA on the following test case. In the code above after each query of the first type I output the maximal among all elements.

12

1 1 1

2 2 2

3 3 3

4 4 4

5 5 5

6 6 6

1 3 4

3 6 -2

1 2 -2

3 3 -2

2 5 3

2 4 -2

If you write on a sheet of paper the above test, you will see that after the last query my program outputs 5 but the answer is 6. Any help will be highly appreciated :").

P.S. If you are wondering why my code looks a bit "strange", that's because it's a part of the following task. It is really interesting and I could explain a solution to everyone who wants to hear it.

UPD. The task was solved. The code above was updated.

Here you are a task. Given set of N points in a plane. You have M queries: given a point P (x,y), which is the closest point of the given one.

I heard that could be done by Voronoi Diagrams. Is it true? Could you provide me some source about solving this task via using this kind of structure, because all I found on the was related to visualiaton?

P.S. Is there another structure that could be used for this task.

THANKS A LOT

Hi. We all know algorithms that find maximal flow, but is there an algorithm that finds minimum flow? For example let's take the following task: Given N workers and N jobs. Each worker takes different amount of money for doing each job and each job can be done by only one worker. Assign the workers to the jobs, so as to the sum of money is minimum. P. S. Apart from using Hungarian algorithm, is there another way?

Can you tell me how to find LIS in O(nlogn) time using Binary Indexed Trees? What about using Interval trees?

I want to officialy say a big "THANK YOU" for everyone who has helped me. +1 for everybody :)

Hi again! I recently solved problem C from round 195, but when I got AC I realised that i havent check whether the numbers in the output are different. Can you explain why this is happening?

My solution

Hi. I recently heard about Rabin- Karp algorithm and I know that it works in O(n+k) time, if we have n- sized text and k patterns to search for. The problem is the following- I don't know the algo, but I know hashing. Can you tell it to me? Can you give a source for example? Thank you for your attention!!!

Does anybody know if there will be a tutorial for abbyy finals? If there is not going to be a tutorial soon, please give me some hints for tasks A,B,C. THANKS A LOT!!!

I know that I'm as greedy as a pig, but could you tell me the ideas for tasks B and C from Yandex round 1. If you think you could provide me source code for them, I will really apreciate it.

Recently I attended YANDEX qualification round and i solved 2 problems. When the solution came out, i realized that there is no tutorial, so i didn't manage to understand problem C by just viewing the source. Can you explain this task particularly and probebly some other too? A LOT OF THANKS!!!

UPD. What about the rest of the tasks. Can you give any hints?

I am wondering about how to find the k-th biggest number in an array with less complexity than O(nlogn). Any ideas?

Program source is not available!!! When I try to view a solution to task D, it gives me Program source is not available. Do you have the same problem? Is there any solution to the problem? Thanks for your attention.

Hi again! I just learned Catalan's numbers and I am searching for CF's tasks, which use this kind of numbers. I will be glad if you could tell me. Thank you very much!!!

Hi, please tell me some nice and difficult tasks from CodeForces thar use either Binary Index Trees or Segment trees. Thanks very much!