Untitled
unknown
c_cpp
2 years ago
2.7 kB
13
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...