Advertisement
tiom4eg

Segtree Training

Jan 13th, 2022
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.31 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. // tiom4eg's precompiler options
  3. // POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS
  4. // IO settings
  5. #define fastIO ios_base::sync_with_stdio(false); cin.tie(0)
  6. // Quick types
  7. #define ll long long
  8. #define ld long double
  9. #define ull unsigned long long
  10. #define pii pair <int, int>
  11. #define pll pair <ll, ll>
  12. #define vi vector <int>
  13. #define mi vector <vector <int> >
  14. // Quick functions
  15. #define endl "\n"
  16. #define F first
  17. #define S second
  18. #define all(a) a.begin(), a.end()
  19. #define sz(a) a.size()
  20. #define pb push_back
  21. #define mp make_pair
  22. #define fint(n) int n; cin >> n
  23. #define fstr(s) string s; cin >> s
  24. #define farr(a, n) int a[n]; for (int pog = 0; pog < n; ++pog) cin >> a[pog]
  25. #define min(a, b) ((a < b) ? (a) : (b))
  26. #define max(a, b) ((a > b) ? (a) : (b))
  27. // Quick fors
  28. #define FOR(i, a, b) for (ll i = a; i < b; ++i)
  29. #define FOR1(s, n) for (int i = s; i < n; ++i)
  30. #define FOR2(s, n) for (int j = s; j < n; ++j)
  31. #define FOR3(s, n) for (int k = s; k < n; ++k)
  32. #define RFOR(n, s) for (int l = n; l >= s; --l)
  33. // Pragmas
  34. #pragma GCC optimize("Ofast") // let the chaos begin!
  35. #pragma GCC optimize ("unroll-loops")
  36. #pragma target("avx,fma")
  37. #pragma comment(linker, "/stack:200000000")
  38. #pragma target("tune=native")
  39. // PBDS
  40. #include <ext/pb_ds/assoc_container.hpp>
  41. #include <ext/pb_ds/tree_policy.hpp>
  42. #define ordered_set tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update>
  43. #define ook order_of_key
  44. #define fbo find_by_order
  45. // POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS
  46. using namespace std;
  47. using namespace __gnu_pbds;
  48. mt19937 rng(std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
  49.  
  50. int sz = 1;
  51.  
  52. struct segtree {
  53.     struct node {
  54.         int v = 0, d = -1;
  55.     };
  56.  
  57.     vector <node> tree;
  58.  
  59.     void build(int n) {
  60.         while (sz < n) sz <<= 1;
  61.         tree.resize(2 * sz);
  62.     }
  63.  
  64.     void push(int node) {
  65.         if (node >= sz || tree[node].d == -1) return;
  66.         tree[node * 2].d = tree[node].d;
  67.         tree[node * 2 + 1].d = tree[node].d;
  68.         tree[node * 2].v = tree[node * 2].d;
  69.         tree[node * 2 + 1].v = tree[node * 2 + 1].d;
  70.         tree[node].d = -1;
  71.     }
  72.  
  73.     void upd(int ql, int qr, int x, int node = 1, int nl = 0, int nr = sz) {
  74.         push(node);
  75.         if (nl >= qr || ql >= nr) return;
  76.         if (ql <= nl && nr <= qr) {
  77.             tree[node].d = x;
  78.             tree[node].v = x;
  79.             return;
  80.         }
  81.         int nm = (nl + nr) / 2;
  82.         upd(ql, qr, x, node * 2, nl, nm);
  83.         upd(ql, qr, x, node * 2 + 1, nm, nr);
  84.         tree[node].v = min(tree[node * 2].v, tree[node * 2 + 1].v);
  85.     }
  86.  
  87.     int get(int ql, int qr, int node = 1, int nl = 0, int nr = sz) {
  88.         push(node);
  89.         if (nl >= qr || ql >= nr) return 2e9;
  90.         if (ql <= nl && nr <= qr) return tree[node].v;
  91.         int nm = (nl + nr) / 2;
  92.         return min(get(ql, qr, node * 2, nl, nm), get(ql, qr, node * 2 + 1, nm, nr));
  93.     }
  94. };
  95.  
  96. int main() {
  97.     fastIO;
  98.     int n, m; cin >> n >> m;
  99.     segtree t;
  100.     t.build(n);
  101.     FOR1(0, m) {
  102.         int op, l, r; cin >> op >> l >> r;
  103.         if (op == 1) {
  104.             int v; cin >> v;
  105.             t.upd(l, r, v);
  106.         }
  107.         else cout << t.get(l, r) << endl;
  108.     }
  109. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement