Блог пользователя HekpoMaH

Автор HekpoMaH, 10 лет назад, По-английски

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.

  • Проголосовать: нравится
  • -14
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

what's kien_coi_1997 style ?