Untitled
unknown
c_cpp
2 years ago
2.7 kB
8
Indexable
#include "bits/stdc++.h" using namespace std; #ifdef LOCAL #include "debug.h" #else #define debug(x...) #endif using ll = long long; using ull = unsigned long long; using db = long double; using pii = pair<int, int>; using pll = pair<ll, ll>; using pdd = pair<db, db>; using tiii = tuple<int, int, int>; using str = string; #define vt vector #define pb push_back #define eb emplace_back #define ins insert #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define sz(x) (int)x.size() #define mp make_pair #define mt make_tuple #define fi first #define se second struct segtree { vt<int> tree; int size; int NO_OPERATION = INT_MAX; void init(int n) { size = 1; while (size < n) size *= 2; tree.assign(2 * size - 1, 0); } void propagate(int x, int lx, int rx) { // cout << x << ' ' << lx << ' ' << rx << endl; if (tree[x] == NO_OPERATION) return; if (rx == lx + 1) return; tree[2 * x + 1] = tree[x]; tree[2 * x + 2] = tree[x]; tree[x] = NO_OPERATION; return; } void modify(int l, int r, ll v, int x, int lx, int rx) { propagate(x, lx, rx); if (l >= rx || r <= lx) { return; } if (l <= lx && rx <= r) { tree[x] = v; return; } int m = (lx + rx) /2; modify(l, r, v, 2 * x + 1, lx, m); modify(l, r, v, 2 * x + 2, m, rx); } void modify(int l, int r, int v) { modify(l, r, v, 0, 0, size); } int min2(int l, int r, int x, int lx, int rx) { if (l >= rx || lx >= r) { return INT_MAX; } if (lx >= l && rx <= r) { return tree[x]; } int m = (lx + rx) / 2; int s1 = min2(l, r, 2 * x + 1, lx, m); int s2 = min2(l, r, 2 * x + 2, m, rx); return min(s1, s2); } int min2(int l, int r) { return min2(l, r, 0, 0, size); } }; void solve() { int n, m; cin >> n >> m; segtree st; st.init(n + 1); for (int i = 0; i < m; ++i) { int f; cin >> f; if (f == 1) { int l, r, v; cin >> l >> r >> v; st.modify(l, r, v); debug(st.tree) } else { int l, r; cin >> l >> r; cout << st.min2(l, r) << '\n'; } } } signed main() { ios::sync_with_stdio(false); cin.tie(NULL); // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); int tests = 1; // cin >> tests; while (tests--) { solve(); } return 0; }
Editor is loading...