Untitled
unknown
plain_text
a year ago
11 kB
1
Indexable
Never
/*Its foolish to fear what we have yet to see and know*/ #pragma GCC optimize "trapv" #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; } #define int ll 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 (r < start || 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); // st[node] = st[node * 2 + 1] + st[node * 2 + 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(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}; 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); } }; signed 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" ; } */