help in cses problem : range update and sums

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

need help in this question. question ask you to implement two types of lazy trees one for update and one for sum. I did all I could but i am unable to find the bug. please help me .

my code


#include <bits/stdc++.h>
using namespace std;


 
#define int         long long
#define double      long double
#define pb          push_back
#define pf          push_front
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define all(a)      (a).begin(),(a).end()
#define rall(a)     (a).rbegin(),(a).rend()
#define x           first
#define y           second
#define endl        '\n'
#define sz(x)     (int)(x).size()

#define fo(i,l,u)   for(i=l;i<u;i++)
#define rfo(i,l,u)  for(i=l;i>=u;i--)
#define allfo(s)    for(auto it=(s).begin();it!=(s).end();it++)


struct segtree{
  vi tree,laz,laz1,change1,change;
  int n,base;
  void began(int z){
      int x,i;
      n=z;
      //initialise everythin with zero
      fo(i,0,2*n+5){
          tree.pb(0);
          laz.pb(0);
          laz1.pb(0);
          change1.pb(0);
          change.pb(0);
      }
    
  }
  //laz is for increment query
  //laz1 is for update query

  void lazy_up(int p,int l,int r){
      if(l>r)return ;
       if(change[p]!=0){
      
          tree[p]+=laz[p]*(r-l+1);
          if(l!=r){
          
              laz[2*p]+=laz[p];
              laz[2*p+1]+=laz[p];
              laz1[2*p]=0;
              laz1[2*p+1]=0;
              change[2*p]=1;
              change[2*p+1]=1;
              change1[2*p]=0;
              change1[2*p+1]=0;
          }
            laz[p]=0;
            laz1[p]=0;
            change[p]=0;
            change1[p]=0;

      }
  }

  void lazy_up1(int p,int l,int r){
      if(l>r)return ;
       if(change1[p]!=0){
         
          tree[p]=laz1[p]*(r-l+1);
          if(l!=r){

              laz1[2*p]=laz1[p];
              laz1[2*p+1]=laz1[p];
              laz[2*p]=0;
              laz[2*p+1]=0;
              change[2*p]=0;
              change[2*p+1]=0;
              change1[2*p]=1;
              change1[2*p+1]=1;
                 
          }
            laz[p]=0;
            laz1[p]=0;
            change[p]=0;
            change1[p]=0;
       
      }
  }


  int query(int p,int l,int r,int a,int b){
     if(l>r)return 0;
     lazy_up1(p , l , r );
       lazy_up(p , l , r );
      
      if(l>=a && r<=b){

          return tree[p];
        }
      else if(r<a || l>b)return 0;
      int mid=(l+r)/2;
      int a1,b1;

      a1=query(2*p ,l , mid , a , b);
      b1=query(2*p+1 , mid+1 , r , a , b);

      tree[p]=(tree[2*p]+tree[2*p+1]);
      return a1+b1;
      
  }
  
  void update1(int p,int l,int r,int a,int b,int val){
       lazy_up1(p , l , r );
       lazy_up(p , l , r );
       

        
        if(l>=a && r<=b){
            tree[p]=val*(r-l+1);
        

           
            if(l!=r){
                laz1[2*p]=val;
                laz1[2*p+1]=val;
                laz[2*p]=0;
                laz[2*p+1]=0;
              change[2*p]=0;
              change[2*p+1]=0;
              change1[2*p]=1;
              change1[2*p+1]=1;
            }
            
        }
        else if(r<a||l>b){
            return ;
        }
        else{
            int mid=(l+r)/2;
         int a1,b1;

         update1(2*p , l , mid , a , b , val);
         update1(2*p+1 , mid+1 , r , a , b , val);
         tree[p]=(tree[2*p]+tree[2*p+1]);

           return ;
        }
        
      }


      void update(int p,int l,int r,int a,int b,int val){
       lazy_up1(p , l , r );
       lazy_up(p , l , r );

        
        if(l>=a && r<=b){
            tree[p]+=val*(r-l+1);
        

            if(l!=r){
                laz[2*p]+=val;
                laz[2*p+1]+=val;
                laz1[2*p]=0;
                laz1[2*p+1]=0;
                change[2*p]=1;
              change[2*p+1]=1;
              change1[2*p]=0;
              change1[2*p+1]=0;
            }
            
        }
        else if(r<a || l>b){
            return ;
        }
        else{
            int mid=(l+r)/2;
         int a1,b1;

         update(2*p , l , mid , a , b , val);
         update(2*p+1 , mid+1 , r , a , b , val);
         tree[p]=(tree[2*p]+tree[2*p+1]);

           return ;
        }
        
      }
      
  
  
  int query(int l,int r){

     return query(1 , 1 , n , l , r);
  }
  
  void update(int a,int b,int val){

      update(1 , 1 , n , a , b , val);
  }
  void update1(int a,int b,int val){
     update1(1 , 1 , n , a, b ,  val);
  }
    
};



 
signed main()
{
      ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
     int i,j,x,n,m;
     cin>>n>>m;
     segtree tree;
     tree.began(n);
     fo(i,1,n+1){
      cin>>x;
      tree.update(i , i , x );
     }
     int type,a,b,c;
     fo(i,0,m){
        cin>>type;
        if(type==1){
          cin>>a>>b>>c;
          tree.update(a , b , c);
        }
        else if(type==2){
          cin>>a>>b>>c;
          tree.update1(a , b , c);
        }
        else {
          cin>>a>>b;
          cout<<tree.query(a , b)<<endl;
        }
     }
     
     
     
   
   
    return 0;
}

test case


100 14
7 6 4 6 2 9 4 8 10 4 10 3 7 10 2 9 4 1 7 4 5 9 9 7 9 6 5 10 8 4 7 10 5 3 3 1 6 7 6 1 5 7 7 7 7 2 3 5 10 8 4 8 7 5 8 6 8 6 7 9 3 10 6 6 8 1 5 8 5 9 9 5 8 8 4 6 6 3 1 2 1 2 9 2 10 9 9 6 5 7 9 10 5 8 2 7 4 1 4 7
2 72 77 5
2 56 63 8
3 40 51
2 42 51 5
3 33 35
2 31 97 6
3 88 90
2 38 78 2
3 77 82
1 70 80 9
1 53 81 4
1 86 93 4
2 12 33 1
3 22 64

required ans

my answer

it would also be help full if you know some blog or toutorial to solve similar problem. thanks in advance guys for helping.

#include<bits/stdc++.h> using namespace std; const int maxn = 1<<18; using ll = long long; struct ctx {//store info about lazy updates //0 - no update //1 - set update //2 - add update int upd_type = 0; ll val = 0; }; ctx merge(ctx a, ctx b) {//we assume b happened after a and we're stacking b on top of a if(b.upd_type == 2)//in case b is add update we stack it on the previous update keeping it's type or setting it to 2 if it was 0 return {a.upd_type ? a.upd_type : 2, a.val + b.val}; return b.upd_type ? b : a;//if b is 0 we keep a, if b is 1 we overwrite the previous updates } struct node {//stores sum and lazy info ll val = 0; ctx lazy; }; node merge(node a, node b) {//empty lazy and sum = sum of children a.val += b.val; a.lazy = ctx(); return a; } node tree[4 * maxn]; void push(int v, int l, int r) { if(tree[v].lazy.upd_type == 2)//the lazy is an add update tree[v].val += tree[v].lazy.val * (r - l + 1); if(tree[v].lazy.upd_type == 1)//the lazy is a set update tree[v].val = tree[v].lazy.val * (r - l + 1); if(l != r) {//if the node has children we propagate the lazy for(auto ch : {2*v, 2*v + 1}) tree[ch].lazy = merge(tree[ch].lazy, tree[v].lazy); } tree[v].lazy = ctx();//reset the lazy } void update(int v, int l, int r, int ql, int qr, ctx u) { push(v, l, r);//pushing everywehere if(qr < l || ql > r) return;//out of range => exit if(ql <= l && r <= qr) {//completely in range put lazy tag and immediately push it so that we can update the parent tree[v].lazy = merge(tree[v].lazy, u); push(v, l, r); return; } int mid = (l + r)/2;//going further update(2*v, l, mid, ql, qr, u); update(2*v + 1, mid + 1, r, ql, qr, u); tree[v] = merge(tree[2*v], tree[2*v + 1]);//updating this node's value children are up to date because we always push } node get(int v, int l, int r, int ql, int qr) {//I find node corresponding to range instead of sum, it's more practical and is useful in harder problmes push(v, l, r);//pushing everywehere if(qr < l || ql > r) return node();//out of range return 0 sum if(ql <= l && r <= qr) return tree[v];//completely in range return this node int mid = (l + r)/2; return merge(get(2*v, l, mid, ql, qr), get(2*v + 1, mid + 1, r, ql, qr));//merge something from the left child and something from the right child } int main() { cin.tie(0)->sync_with_stdio(0); int n, q; cin >> n >> q; for(int t, i = 1; i <= n; i++) { cin >> t;//2 - update type, t - value update(1, 1, n, i, i, {2, t});//To not implement build function I interpret initial values as add updates //since we have everything set to 0 we can act like segtree is initialized with them } for(int t, l, r, x; q--;) { cin >> t; if(t < 3) { cin >> l >> r >> x;//t^3 - update type, x - value update(1, 1, n, l, r, {t^3, x});//^3 turns 2 to 1 and 1 to 2 because I use different labels for update types in my ctx class } else { cin >> l >> r; cout << get(1, 1, n, l, r).val << '\n'; } } return 0; }

#include<bits/stdc++.h> #define inp 200005 #define check exit(0) #define nl cout<<endl; #define mod 1000000007 #define ll long long int #define trace(x) cerr<<#x<<" : "<<x<<endl; #define jaldi ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); #define deb(v) for(int i=0;i<v.size();i++) {cout<<v[i]; (i==v.size()-1) ? cout<<"\n":cout<<" "; } using namespace std; // Pick yourself up, 'cause... int n; vector<int> v(inp); ll l,r,t,change; vector<ll> st(inp<<2,0); vector<pair<int,ll>> lazy(inp<<2); void build(int si=1,int ss=1,int se=n) { if(ss==se) { st[si]=v[ss]; return; } int mid=(ss+se)/2; build(si*2,ss,mid); build(si*2+1,mid+1,se); st[si]=st[2*si]+st[2*si+1]; } void propogate(int si,int ss,int se) { int tot=se-ss+1; auto p = lazy[si]; lazy[si]={0,0}; if(p.first == 1) { st[si]+=tot*p.second; } else { st[si]=tot*p.second; } if(ss==se) return; if(p.first == 1) { int lc=si*2,rc=si*2+1; if(lazy[lc].first!=0) { lazy[lc]={lazy[lc].first , lazy[lc].second + p.second}; } else { lazy[lc] = p; } if(lazy[rc].first!=0) { lazy[rc]={lazy[rc].first , lazy[rc].second + p.second}; } else { lazy[rc] = p; } } else { int lc=si*2,rc=si*2+1; lazy[lc] = p; lazy[rc] = p; } } void update(int si=1,int ss=1,int se=n) { if( lazy[si].first!=0 ) { propogate(si,ss,se); } if(ss>r || se<l) return; if(ss>=l && se<=r) { if(t==1) { lazy[si]={1,change}; } else { lazy[si]={2,change}; } propogate(si,ss,se); return; } int mid=(ss+se)/2; update(si*2,ss,mid); update(si*2+1,mid+1,se); st[si]=st[2*si]+st[2*si+1]; } ll query(int si=1,int ss=1,int se=n) { if (lazy[si].first != 0 ) { propogate(si,ss,se); } if(ss>r || se<l) return 0; if(ss>=l && se<=r) return st[si]; int mid=(ss+se)/2; return ( query(si*2,ss,mid) + query(si*2+1,mid+1,se) ); } int main() { jaldi int q; cin>>n>>q; for(int i=1;i<=n;i++) { cin>>v[i]; } build(); while(q--) { cin>>t; if(t==1 || t==2) { cin>>l>>r>>change; update(); } else { cin>>l>>r; cout<<query() << "\n"; } } return 0; }

#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cmath> #include <vector> #include <set> #include <map> #include <unordered_set> #include <unordered_map> #include <queue> #include <ctime> #include <cassert> #include <complex> #include <string> #include <cstring> #include <chrono> #include <random> #include <queue> #include <bitset> using namespace std; typedef long long ll; typedef long long unsigned int llui; typedef pair<int,int> ii; typedef pair<ll,ll> pll; typedef vector<ii> vii; typedef vector<int> vi; typedef vector<ll> vl; typedef vector< vector<int> > vvi; typedef vector< vector<ll> > vvl; typedef set<int> si; typedef map<string, int> msi; typedef map<int, int> mii; #define INF 1000000000 #define MOD 1000000007 #define EPS 1e-9 #define ALL(x) (x).begin(), (x).end() #define RALL(x) (x).rbegin(), (x).rend() #define SORT(x) sort((x).begin(),(x).end()) #define UNIQUE(x) SORT(x),(x).erase(unique((x).begin(),(x).end()),(x).end()) #define F first #define S second #define MP make_pair #define PB push_back #define EB emplace_back #define LB lower_bound #define UB upper_bound #define SZ(a) int((a).size()) #define CLR(a) memset(a,0,sizeof(a)) #define SET(a,b) memset(a,b,sizeof(a)) #define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) #define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) #define FOR(i,a,b) for (int i = int(a); i < int(b); i++) #define FORD(i,a,b) for(int i=int(b)-1; i>=int(a); i--) #define REP(i, n) for (int i = 0; i < int(n); i++) #define REP1(i,n) for (int i = 1; i <= int(n); i++) #define REV(i, n) for (int i = int(n)-1; i >=0 ; i--) #define sd(n) scanf("%d",&n) #define dsd(n) int n; scanf("%d",&n) #define sd2(a,b) scanf("%d%d",&a,&b) #define dsd2(a,b) int a,b; scanf("%d%d",&a,&b) #define sd3(a,b,c) scanf("%d%d%d",&a,&b,&c) #define dsd3(a,b,c) int a,b,c; scanf("%d%d%d",&a,&b,&c) #define pd(n) printf("%d\n",n) #define pds(n) printf("%d ",n) #define sl(n) scanf("%lld",&n) #define dsl(n) ll n; scanf("%lld",&n) #define sl2(a,b) scanf("%lld%lld",&a,&b) #define dsl2(a,b) ll a,b; scanf("%lld%lld",&a,&b) #define sl3(a,b,c) scanf("%lld%lld%lld",&a,&b,&c) #define dsl3(a,b,c) ll a,b,c; scanf("%lld%lld%lld",&a,&b,&c) #define pl(n) printf("%lld\n",n) #define pls(n) printf("%lld ",n) #define PR(a,n) { REP(_,n) cout<<a[_]<<' '; cout<<"\n"; } #define PR1(a,n) { REP1(_,n) cout<<a[_]<<' '; cout<<"\n"; } #define trace(x) cerr << " [" << #x << ": " << x << "]\n" #define sim template < class c #define ris return * this #define dor > debug & operator << #define eni(x) sim > typename \ enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) { sim > struct rge { c b, e; }; sim > rge<c> range(c i, c j) { return rge<c>{i, j}; } sim > auto dud(c* x) -> decltype(cerr << *x, 0); sim > char dud(...); struct debug { #ifdef LOCAL ~debug() { cerr << endl; } eni(!=) cerr << boolalpha << i; ris; } eni(==) ris << range(begin(i), end(i)); } sim, class b dor(pair < b, c > d) { ris << "(" << d.first << ", " << d.second << ")"; } sim dor(rge<c> d) { *this << "["; for (auto it = d.b; it != d.e; ++it) *this << ", " + 2 * (it == d.b) << *it; ris << "]"; } #else sim dor(const c&) { ris; } #endif }; #define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] " inline int two(int n) { return 1 << n; } inline int test(int n, int b) { return (n>>b)&1; } inline void set_bit(int & n, int b) { n |= two(b); } inline void unset_bit(int & n, int b) { n &= ~two(b); } inline int last_bit(int n) { return n & (-n); } inline int ones(int n) { int res = 0; while(n && ++res) n-=n&(-n); return res; } #define LSOne(S) (S&(-S)) const double pi = acos(-1); //const int oo = 0x3f3f3f3f; int cmp(double x, double y = 0, double tol = EPS) { return (x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1; } template<class T> bool uin(T &a,T b) {return a > b ? (a=b, true):false;} template<class T> bool uax(T &a,T b) {return a < b ? (a=b, true):false;} ///////////////////////////////////////////////////////////////////// const int nax = 2e5+10; ll t[4*nax]; ll l1[4*nax]; // increase each value by x ll l2[4*nax]; ll a[nax]; int n, q; void build(int v=1, int tl=0, int tr=n-1){ if (tl == tr) t[v] = a[tl]; else { int tm = (tl + tr) / 2; build(v * 2, tl, tm); build(v * 2 + 1, tm + 1, tr); t[v] = t[v * 2] + t[v * 2 + 1]; } } void push(int v, int tl, int tr){ if(l2[v]){ t[v] = (tr-tl+1)*l2[v]; if(tl!=tr){ l2[2*v] = l2[v]; l1[2*v] = 0; l2[2*v+1] = l2[v]; l1[2*v+1] = 0; } l2[v] = 0; } if(l1[v]){ t[v] += (tr-tl+1)*l1[v]; if(tl!=tr){ l1[2*v] += l1[v]; l1[2*v+1] += l1[v]; } l1[v] = 0; } } void update(int v, int tl, int tr, int l, int r, int value, int type){ push(v, tl, tr); // if you put this after (l>r) return statement, you'll get WA if(l>r) return; if(l==tl && tr==r){ if(type==1){ l1[v] += value; }else{ l2[v] = value; l1[v] = 0; } push(v, tl, tr); }else{ int tm = (tl+tr)/2; update(2*v, tl, tm, l, min(r, tm), value, type); update(2*v+1, tm+1, tr, max(l, tm+1), r, value, type); t[v] = t[2*v] + t[2*v+1]; } } ll sum(int v, int tl, int tr, int l, int r) { if (l > r) return 0; push(v, tl, tr); if (l == tl && r == tr) { return t[v]; } int tm = (tl + tr) / 2; return sum(v * 2, tl, tm, l, min(r, tm)) + sum(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r); } int main() { sd2(n,q); REP(i,n) sl(a[i]); build(); REP(i,q){ dsd(type); if(type==1){ dsd3(A,B,X); update(1, 0, n-1, A-1, B-1, X, 1); }else if(type==2){ dsd3(A,B,X); update(1, 0, n-1, A-1, B-1, X, 2); }else{ dsd2(A,B); pl(sum(1, 0, n-1, A-1, B-1)); } } return 0; }

Комментарии (12)

Написать комментарий?

arham_doshi

4 года назад, # |

Auto comment: topic has been updated by arham_doshi (previous revision, new revision, compare).

→ Ответить

kostia244

+25

Your code contains a lot of hindi comments which makes it irritating to read
You use different spacing techniques (3 spaces in main, 2 spaces in segtree).
You don't add any spaces after ,,|,& et.
You have weird blank lines.
You have like a million debugging lines.
You are using weird loop defines.

...

You could have removed useless stuff and run a formatting tool on your code to make it somewhat readable. Why should total strangers help you if you can't even do that? What are you expecting by throwing this pile of ugly code at people? You even have a testcase which your code doesn't work on I think you should debug by yourself. And why is this blog at +4? I'd argue such stuff should be forbidden on cf at best.

4 года назад, # ^ |

← Rev. 2 →

really sorry about it . It is nice feedback i will see it in furture. thing about debugging myself is i tried it for 2 hrs a lot of debugging but i am not getting a tiny bug. when i print the query (in which i am getting wrong ans ) after after every operation it is giving write ans. a soon as comment it again the ans is worng . it is frustrating man and the blog is my last resort.

← Rev. 3 →

i tried it for 2 hrs

~~ Rookie numbers make that 5 times more~~

So I skimmed through your code:

Your probably should change 2*n to 4*n

You store everything as int but sum can overflow i guess

Sometimes add update can be stacked on top of set update and you are always stacking it into add updates

Your code prints one because in the second query you add 1 to sum lazy, which is in fact overwritten by set lazy(from query 1). Instead you should have added 1 to set lazy so the operation becomes "set to two".

Keeping two lazy tags can mess with order instead I suggest storing one tag, and it's type.

Here's a short implementation of this idea

I am really bored

thank you so much kostia . i it worked . i learned alot from you code. it was superb.

Kartik_Bhanderi

It's quite hard to understand your code...

So if you want then can look at my code.

My approach is quite lengthy , so unable to explain it here.

Code

thanks for the help bro . i will do it like you lets see

Glad it helped :)

RNR

In the following solution if I swap the first and second line in update() that is


    if(l>r) return;
    push(v, tl, tr); // if you put this after (l>r) return statement, you'll get WA

Can someone help me with why this order matters? Because we are anyways returning if l>r?

Solution code

Thanking you in advance.

Errichto

Don't push without later merging your two children.

Errichto Thank you very much __/\_ . If I interchange the lines, the children node is marked lazy(but t[children] is not updated) and hence it updates the parent with old value.

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