range updates and replace doubt

mail@pastecode.io avatar
unknown
c_cpp
2 years ago
11 kB
6
Indexable
Never
/*Its foolish to fear what we have yet to see and know*/

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; 
// find_by_order(k)  returns iterator to kth element starting from 0;
// order_of_key(k) returns count of elements strictly smaller than k;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define count_1(n)   __builtin_popcountll(n)
#define pb push_back
#define fr(a,b) for(int i =a ;i <b ;i++)
#define all(x) (x).begin(), (x).end()
#define vint vector<int>
typedef long long ll;
typedef long double ld;
const int N = 1e9 + 7 ;
#define inf (1LL<<62)
template <typename T>istream &operator>>(istream &istream, vector<T> &vec){for (auto &a : vec)cin >> a;return istream;}     
template <typename T>ostream &operator<<(ostream &ostream, const vector<T> &vec){for (auto &a : vec)cout << a << " ";return ostream;}
long long binpow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
//#define int long long
vint dx = {0,+1,0,-1} ;
vint dy = {1,0,-1,0} ;
int msb(int value){
    if(value==0) return 0;
    int count=0;
    while(value>>count){
        count++;
    }
    return count;
}
ll nCr(int n, int r){ ll p = 1, k = 1;if (n - r < r) {r = n - r;}
    if (r != 0) {while (r) {p *= n;k *= r; ll m = __gcd(p, k);p /= m;k /= m;n--;r--;}}
    else {p = 1;} return p;}
struct segmenttree {
	int n;
	vector<int> st;
	vector<pair<int,int>> lazy ;
	//{add itna , replace each by itna}
 
	void init(int _n) {
		this->n = _n;
		st.resize(4 * n, 0);
		lazy.resize(4 * n, {0,0});
	}
 
	void build(int start, int ending, int node, vector<int> &v) {
		// leaf node base case
		if (start == ending) {
			st[node] = v[start];
			return;
		}
 
		int mid = (start + ending) / 2;
 
		// left subtree is (start,mid)
		build(start, mid, 2 * node + 1, v);
 
		// right subtree is (mid+1,ending)
		build(mid + 1, ending, 2 * node + 2, v);
 
		st[node] = st[node * 2 + 1] + st[node * 2 + 2];
	}
 
	int query(int start, int ending, int l, int r, int node) {
		// non overlapping case
		if (start > r || ending < l) {
			return 0;
		}
 
		// lazy propagation / clear the lazy update
	  	if (lazy[node].first != 0 || lazy[node].second != 0) {
			// pending updates
			// update the segment tree node
			//if(a range has to be replaced by a certain value )
			if(lazy[node].second != 0)st[node] = lazy[node].second* (ending - start + 1) ;
			st[node] += lazy[node].first * (ending - start + 1);
			if (start != ending) {
				// propagate the updated value
				if(lazy[node].second == 0){
				lazy[2 * node + 1].first += lazy[node].first;
				lazy[2 * node + 2].first += lazy[node].first;
				}else{
				lazy[2 * node + 1].second = lazy[node].second ;
				lazy[2 * node + 2].second = lazy[node].second ;
				lazy[2 * node + 1].first = lazy[node].first;
				lazy[2 * node + 2].first = lazy[node].first;
				}
			}
			lazy[node] = {0,0};
		}
 
		// complete overlap
		if (start >= l && ending <= r) {
			return st[node];
		}
 
		// partial case
		int mid = (start + ending) / 2;
 
		int q1 = query(start, mid, l, r, 2 * node + 1);
		int q2 = query(mid + 1, ending, l, r, 2 * node + 2);
 
		return q1 + q2;
	}
 
	void update(int start, int ending, int node, int l, int r, int additta , int replaceitta) {
		// non overlapping case
		if (start > r || ending < l) {
			return ;
		}
 
		// lazy propagation / clear the lazy update
		if (lazy[node].first != 0 || lazy[node].second  !=0 ) {
			// pending updates
			// update the segment tree node
			//if(a range has to be replaced by a certain value )
			if(lazy[node].second != 0)st[node] = lazy[node].second* (ending - start + 1) ;
			st[node] += lazy[node].first * (ending - start + 1);
			if (start != ending) {
				// propagate the updated value
				if(lazy[node].second == 0){
				lazy[2 * node + 1].first += lazy[node].first;
				lazy[2 * node + 2].first += lazy[node].first;
				}else{
				lazy[2 * node + 1].second = lazy[node].second ;
				lazy[2 * node + 2].second = lazy[node].second ;
				lazy[2 * node + 1].first = lazy[node].first;
				lazy[2 * node + 2].first = lazy[node].first;
				}
			}
			lazy[node] = {0,0};
		}
 
		// complete overlap
		if (start >= l && ending <= r) {
		    if(additta == 0){
		        lazy[node].first = 0 ;
		        lazy[node].second  = replaceitta ;
		    }else{
		        lazy[node].first += additta ;
		        //lazy[node].second  = 0 ;
		    }
		if (start != ending) {
				// propagate the updated value

				if(lazy[node].second == 0){
				lazy[2 * node + 1].first += lazy[node].first;
				lazy[2 * node + 2].first += lazy[node].first;
				}else{
				lazy[2 * node + 1].second = lazy[node].second ;
				lazy[2 * node + 2].second = lazy[node].second ;
				lazy[2 * node + 1].first = lazy[node].first;
				lazy[2 * node + 2].first = lazy[node].first;	
				}
			}
			return;
		}
 
		// partial case
		int mid = (start + ending) / 2;
 
		update(start, mid, 2 * node + 1, l, r, additta , replaceitta);
 
		update(mid + 1, ending, 2 * node + 2, l, r, additta , replaceitta);
 
		st[node] = st[node * 2 + 1] + st[node * 2 + 2];
 
		return;
	}
 
	void build(vector<int> &v) {
		build(0, n - 1, 0, v);
	}
 
	int query(int l, int r) {
		return query(0, n - 1, l, r,0);
	}
 
	void update(int l, int r, int x, int y) {
		update(0, n - 1, 0, l, r, x , y);
	}
};  
int main() {
 FAST
    ll t,n,m,x,i,j,k,q ;
    t=1;
   // cin >>t ;
    while(t--){
  cin >>n  >> q ;
  vint v(n) ;
  cin >> v ;
  segmenttree ss ;
  ss.init(n) ;
  ss.build(v) ;
  fr(0,q){
      int  a , b, c ,d; 
      cin >>a  >> b >> c ;
      b-- ; c--;
      if(a==1){
          cin >>d  ;
          ss.update(b,c,d,0) ;
      }else if(a==2){
          cin >>d  ;
         ss.update(b,c,0,d) ; 
      }else{
          cout << ss.query(b,c)<<"\n" ;
      }
  }
  
    }
    return 0;
}
/*Parent info ke lie its better to have use dfs
Return in build base biro :)
10^9 is  within integer limits 
string  c1(1,s1[0]) ;
cout<<setw(2)<<setfill('0')<<a;
*/
/*    //DIJKSTRAS ;
	 vector<pair<int,int>> g[n+1] ;
	 vector<int> lev(n+1,INF) ;
	 for(int i=0;i<m;i++){
	     int x,y ;
	     cin >> x >> y ;
	     g[x].push_back({y,0}) ;
	     g[y].push_back({x,1}) ;
	 }
	 lev[1] =0 ;
	  priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q ;
	  q.push({0,1}) ;
	  while(!q.empty()){
	      int wt = q.top().first ;
	      int x = q.top().second ;
	      q.pop() ;
	      if(lev[x] < wt )continue ;
	      for(auto cur : g[x]){
	          int c=cur.first ;
	          int d=  cur.second  ;
	          if(lev[c] > wt+d){
	              lev[c] = wt+d ;
	              q.push({lev[c],c}) ;
	          }
	      }
	  }
	 
*/
/*int modInverse(int a, int m)
{
    int m0 = m;
    int y = 0, x = 1;
    if (m == 1)
        return 0;
    while (a > 1) {
        int q = a / m;
        int t = m;
        m = a % m, a = t;
        t = y;
        y = x - q * y;
        x = t;
    }
*/
/* //BL & LCA
vint adj[200005] ;
int  depth[200005] ;
int parent[30][200005] ;
void dfs(int node, int par){
    for(auto child  : adj[node]){
        if( child != par){
            parent[0][child] = node ;
              depth[child] = depth[node] +1 ;
            dfs(child , node) ;
          
        }
    }
}
int raise(int x , int y){
    int z =0  ;
    while(y > 0){
        if(y&1) x = parent[z][x] ;
        y >>= 1 ;
        z++ ;
    }
    return x ;
}
int lca(int x  , int y){
    if(depth[x] > depth[y]) swap(x,y) ;
    int z =  depth[y] - depth[x] ;
    y = raise(y,z) ;
    if(x== y) return x ;
    for(int  i =29 ;i >= 0 ;i--){
        if(parent[i][x] !=  parent[i][y]){
            x = parent[i][x] ;
            y = parent[i][y] ;
        }
    }
   return parent[0][x] ; 
    //HMMMMMMMMMMMMMMMMMMMMMMMMM
     fr(0,n-1){
         int a, b ; 
         cin >> a >> b  ;
         adj[a].pb(b) ;
         adj[b].pb(a) ;
     }
     dfs(1,0) ;
     fr(1,30){
         for(int j = 1 ; j <= n ;j++){
             parent[i][j] = parent[i-1][parent[i-1][j]] ;
         }
     }
}
*/
/*
   struct segmenttree {
	int n;
	vector<int> st;
 
	void init(int _n) {
		this->n = _n;
		st.resize(4 * n, 0);
	}
 
	void build(int start, int ending, int node, vector<int> &v) {
		// leaf node base case
		if (start == ending) {
			st[node] = v[start];
			return;
		}
 
		int mid = (start + ending) / 2;
 
		// left subtree is (start,mid)
		build(start, mid, 2 * node + 1, v);
 
		// right subtree is (mid+1,ending)
		build(mid + 1, ending, 2 * node + 2, v);
 
		st[node] = st[node * 2 + 1] ^ st[node * 2 + 2];
	}
 
	int query(int start, int ending, int l, int r, int node) {
		// non overlapping case
		if (start > r || ending < l) {
			return 0;
		}
 
		// complete overlap
		if (start >= l && ending <= r) {
			return st[node];
		}
 
		// partial case
		int mid = (start + ending) / 2;
 
		int q1 = query(start, mid, l, r, 2 * node + 1);
		int q2 = query(mid + 1, ending, l, r, 2 * node + 2);
 
		return q1 ^ q2;
	}
 
	void update(int start, int ending, int node, int index, int value) {
		// base case
		if (start == ending) {
			st[node] = value;
			return;
		}
 
		int mid = (start + ending) / 2;
		if (index <= mid) {
			// left subtree
			update(start, mid, 2 * node + 1, index, value);
		}
		else {
			// right
			update(mid + 1, ending, 2 * node + 2, index, value);
		}
 
		st[node] = st[node * 2 + 1] + st[node * 2 + 2];
 
		return;
	}
 
	void build(vector<int> &v) {
		build(0, n - 1, 0, v);
	}
 
	int query(int l, int r) {
		return query(0, n - 1, l, r, 0);
	}
 
	void update(int x, int y) {
		update(0, n - 1, 0, x, y);
	}
};
*/
/*class DSU{
public:
    vector<int>parent;
    DSU(int n) { parent.resize(n+1); for(int i=0;i<=n;i++) parent[i]=-1; }
    int find_set(int x) { return parent[x]<0?x:parent[x]=find_set(parent[x]); }
    bool union_set(int a,int b){ int pa=find_set(a); int pb=find_set(b);
        if(pa==pb) { return 0; } if(parent[pa]>parent[pb]) { swap(pa,pb); }
        parent[pa]+=parent[pb]; parent[pb]=pa; return 1; }
    bool same_set(int a,int b){ return find_set(a)==find_set(b); } };
*/
/*
  cin   >> n >> m  >> sx >> sy >> d ;
  int d1 = (max(1,sx-d)-1)&(sy-1) ;
  int d2 = (sx-1)&(max(1,sy-d)-1) ;
  int d3 = (min(n,sx+d)-n)&(sy-m) ;
  int d4 =(sx-n)&(min(m,sy+d)-m) ;
  if((d1==0 && d2==0)||(d1==0 && d3==0)||(d4==0 && d2==0)||(d3==0 && d4==0)){
      cout <<(n+m)-2 <<"\n" ;
  }else{
      cout <<"-1" <<"\n" ;
  }
  */