### de_dust2's blog

By de_dust2, history, 3 weeks ago,

Question 1 : Given an array of N elements handle below two type of range queries :

1. Update L R v : Replace each element in range [L, R] to v
2. Query X : Get value at position X


Question 2 : Given an array of N elements handle below two type of range queries :

1. Update L R v : Replace each element in range [L, R] to v
2. Query L R : Get max(or min/sum) of values in range [L, R]


Can someone kindly help me with the approach for above problems?

• -18

 » 3 weeks ago, # |   +3 I have a solution for both the problems if the constraints are lower like $10$$5$. We can use sqrt decomposition with some kind of lazy propagation. Use simple sqrt decomp. Now coming to the update query, 1) if a block lies partially in the range $l$ to $r$ then linearly traverse and update. 2) Let's say we have two arrays 1) lazy a boolean array 2) val array to hold corresponding value to be put in case of lazy propagation. now if the block lies completely then do lazy propagation. set $lazy[curblock]$ = true and $val[curblock]$ = $v$. So in this way you won't need to traverse the block and this will make the complexity of every query O(sqrt($N$)). Now rest is same as we do in lazy propagation in segment tree. You can calculate range min/max also using the same idea.
 » 3 weeks ago, # |   +11 Segment Tree with Lazy Propagation, I think this might help https://usaco.guide/plat/RURQ
•  » » 3 weeks ago, # ^ |   0 Thank you. But what should be the combine function of segment tree in case of question 1? Could be any dummy function, is it?
•  » » » 3 weeks ago, # ^ |   +6 Sure, you could use a sum function or whateverHere's my code if it helps Code#include using namespace std; const int MAXN = 1e5 + 5; int N, a[MAXN], Q, ST[4 * MAXN], lazy[4 * MAXN]; //depends on operation int DEFAULT = 0; //sum //int DEFAULT = INT_MIN; //max //int DEFAULT = INT_MAX; //min int combine(int x, int y) { return x + y; //sum //return max(x, y); //max //return min(x, y); //min } void build(int node = 0, int l = 0, int r = N - 1) { lazy[node] = -1; if(l == r) { ST[node] = a[l]; return; } int mid = (l+r)/2, lchild = 2*node + 1, rchild = 2*node + 2; build(lchild, l, mid); build(rchild, mid + 1, r); ST[node] = combine(ST[lchild], ST[rchild]); } void propagate(int node, int l, int r) { if(lazy[node] == -1) return; //depends on operation ST[node] = lazy[node] * (r - l + 1); //sum //ST[node] = lazy[node]; //max or min if(l != r) { int lchild = 2*node + 1, rchild = 2*node + 2; lazy[lchild] = lazy[node]; lazy[rchild] = lazy[node]; } lazy[node] = -1; } void upd(int v, int L, int R, int node = 0, int l = 0, int r = N - 1) { propagate(node, l, r); if(r < L || R < l) return; if(L <= l && r <= R) { lazy[node] = v; propagate(node, l, r); return; } int mid = (l+r)/2, lchild = 2*node + 1, rchild = 2*node + 2; upd(v, L, R, lchild, l, mid); upd(v, L, R, rchild, mid + 1, r); ST[node] = combine(ST[lchild], ST[rchild]); } int qry(int L, int R, int node = 0, int l = 0, int r = N - 1) { propagate(node, l, r); if(r < L || R < l) return DEFAULT; if(L <= l && r <= R) return ST[node]; int mid = (l+r)/2, lchild = 2*node + 1, rchild = 2*node + 2; return combine(qry(L, R, lchild, l, mid), qry(L, R, rchild, mid + 1, r)); } int main () { cin >> N; for(int i = 0; i < N; i++) cin >> a[i]; build(); cin >> Q; for(int i = 0; i < Q; i++) { int type; cin >> type; if(type == 1) { int v, L, R; cin >> v >> L >> R; upd(v, L, R); } else if(type == 2) { int L, R; cin >> L >> R; cout << qry(L, R) << "\n"; } } return 0; } 
•  » » » » 3 weeks ago, # ^ |   0 Thanks! Very clean implementation.