API tools faq
paste
tiom4eg

openol B 100

tiom4eg
Jan 16th, 2024
259
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 14.67 KB | None | 0 0
raw download clone embed print report
  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 vi vector <int>
  12. #define mi vector <vector <int>>
  13. // Quick functions
  14. #define endl "\n"
  15. #define F first
  16. #define S second
  17. #define all(a) a.begin(), a.end()
  18. #define sz(a) (int)(a.size())
  19. #define pb push_back
  20. #define mp make_pair
  21. // Quick fors
  22. #define FOR(i, a, b) for (int i = a; i < b; ++i)
  23. #define FORS(i, a, b, c) for (int i = a; i < b; i += c)
  24. #define RFOR(i, a, b) for (int i = a; i >= b; --i)
  25. #define EACH(e, a) for (auto& e : a)
  26. // Pragmas
  27. #ifndef TIOM4EG
  28. #pragma GCC optimize("O3") // let the chaos begin!
  29. #pragma GCC target("avx,avx2,tune=native")
  30. #pragma GCC comment(linker, "/stack:200000000")
  31. #endif
  32. // PBDS
  33. #include <ext/pb_ds/assoc_container.hpp>
  34. #include <ext/pb_ds/tree_policy.hpp>
  35. #define pbds tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update>
  36. using namespace __gnu_pbds;
  37. // POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS
  38. using namespace std;
  39. mt19937 rng(chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now().time_since_epoch()).count());
  40. constexpr int INF = 1e9 + 7, MD = 998244353, MAX = 200007, LG = 20, R = 1 << LG, MOD = 1000000007, MOD2 = 1e9 + 9, B = 256;
  41. const ll INFLL = 1e18 + 7;
  42.  
  43. struct IOPre {
  44.     static constexpr int TEN = 10, SZ = TEN * TEN * TEN * TEN;
  45.     std::array<char, 4 * SZ> num;
  46.     constexpr IOPre() : num{} {
  47.         for (int i = 0; i < SZ; i++) {
  48.             int n = i;
  49.             for (int j = 3; j >= 0; j--) {
  50.                 num[i * 4 + j] = static_cast<char>(n % TEN + '0');
  51.                 n /= TEN;
  52.             }
  53.         }
  54.     }
  55. };
  56. struct IO {
  57. #if !HAVE_DECL_FREAD_UNLOCKED
  58.     #define fread_unlocked fread
  59. #endif
  60. #if !HAVE_DECL_FWRITE_UNLOCKED
  61.     #define fwrite_unlocked fwrite
  62. #endif
  63.     static constexpr int SZ = 1 << 22, LEN = 32, TEN = 10, HUNDRED = TEN * TEN,
  64.                          THOUSAND = HUNDRED * TEN, TENTHOUSAND = THOUSAND * TEN,
  65.                          MAGIC_MULTIPLY = 205, MAGIC_SHIFT = 11, MASK = 15,
  66.                          TWELVE = 12, SIXTEEN = 16;
  67.     static constexpr IOPre io_pre = {};
  68.     std::array<char, SZ> input_buffer, output_buffer;
  69.     int input_ptr_left, input_ptr_right, output_ptr_right;
  70.  
  71.     IO()
  72.         : input_buffer{},
  73.           output_buffer{},
  74.           input_ptr_left{},
  75.           input_ptr_right{},
  76.           output_ptr_right{} {}
  77.     IO(const IO&) = delete;
  78.     IO(IO&&) = delete;
  79.     IO& operator=(const IO&) = delete;
  80.     IO& operator=(IO&&) = delete;
  81.  
  82.     ~IO() {
  83.         flush();
  84.     }
  85.  
  86.     template <class T>
  87.     struct is_char {
  88.         static constexpr bool value = std::is_same_v<T, char>;
  89.     };
  90.  
  91.     template <class T>
  92.     struct is_bool {
  93.         static constexpr bool value = std::is_same_v<T, bool>;
  94.     };
  95.  
  96.     template <class T>
  97.     struct is_string {
  98.         static constexpr bool value =
  99.             std::is_same_v<T, std::string> || std::is_same_v<T, const char*> ||
  100.             std::is_same_v<T, char*> || std::is_same_v<std::decay_t<T>, char*>;
  101.     };
  102.  
  103.     template <class T, class D = void>
  104.     struct is_custom {
  105.         static constexpr bool value = false;
  106.     };
  107.  
  108.     template <class T>
  109.     struct is_custom<T, std::void_t<typename T::internal_value_type>> {
  110.         static constexpr bool value = true;
  111.     };
  112.  
  113.     template <class T>
  114.     struct is_default {
  115.         static constexpr bool value = is_char<T>::value || is_bool<T>::value ||
  116.                                       is_string<T>::value ||
  117.                                       std::is_integral_v<T>;
  118.     };
  119.  
  120.     template <class T, class D = void>
  121.     struct is_iterable {
  122.         static constexpr bool value = false;
  123.     };
  124.  
  125.     template <class T>
  126.     struct is_iterable<
  127.         T, typename std::void_t<decltype(std::begin(std::declval<T>()))>> {
  128.         static constexpr bool value = true;
  129.     };
  130.  
  131.     template <class T, class D = void, class E = void>
  132.     struct is_applyable {
  133.         static constexpr bool value = false;
  134.     };
  135.  
  136.     template <class T>
  137.     struct is_applyable<T, std::void_t<typename std::tuple_size<T>::type>,
  138.                         std::void_t<decltype(std::get<0>(std::declval<T>()))>> {
  139.         static constexpr bool value = true;
  140.     };
  141.  
  142.     template <class T>
  143.     static constexpr bool needs_newline = (is_iterable<T>::value ||
  144.                                            is_applyable<T>::value) &&
  145.                                           (!is_default<T>::value);
  146.  
  147.     template <typename T, typename U>
  148.     struct any_needs_newline {
  149.         static constexpr bool value = false;
  150.     };
  151.     template <typename T>
  152.     struct any_needs_newline<T, std::index_sequence<>> {
  153.         static constexpr bool value = false;
  154.     };
  155.     template <typename T, std::size_t I, std::size_t... Is>
  156.     struct any_needs_newline<T, std::index_sequence<I, Is...>> {
  157.         static constexpr bool value =
  158.             needs_newline<decltype(std::get<I>(std::declval<T>()))> ||
  159.             any_needs_newline<T, std::index_sequence<Is...>>::value;
  160.     };
  161.  
  162.     inline void load() {
  163.         memmove(std::begin(input_buffer),
  164.                 std::begin(input_buffer) + input_ptr_left,
  165.                 input_ptr_right - input_ptr_left);
  166.         input_ptr_right =
  167.             input_ptr_right - input_ptr_left +
  168.             static_cast<int>(fread_unlocked(
  169.                 std::begin(input_buffer) + input_ptr_right - input_ptr_left, 1,
  170.                 SZ - input_ptr_right + input_ptr_left, stdin));
  171.         input_ptr_left = 0;
  172.     }
  173.  
  174.     inline void read_char(char& c) {
  175.         if (input_ptr_left + LEN > input_ptr_right) load();
  176.         c = input_buffer[input_ptr_left++];
  177.     }
  178.     inline void read_string(std::string& x) {
  179.         char c;
  180.         while (read_char(c), c < '!') continue;
  181.         x = c;
  182.         while (read_char(c), c >= '!') x += c;
  183.     }
  184.     template <class T>
  185.     inline std::enable_if_t<std::is_integral_v<T>, void> read_int(T& x) {
  186.         if (input_ptr_left + LEN > input_ptr_right) load();
  187.         char c = 0;
  188.         do c = input_buffer[input_ptr_left++];
  189.         while (c < '-');
  190.         [[maybe_unused]] bool minus = false;
  191.         if constexpr (std::is_signed<T>::value == true)
  192.             if (c == '-') minus = true, c = input_buffer[input_ptr_left++];
  193.         x = 0;
  194.         while (c >= '0')
  195.             x = x * TEN + (c & MASK), c = input_buffer[input_ptr_left++];
  196.         if constexpr (std::is_signed<T>::value == true)
  197.             if (minus) x = -x;
  198.     }
  199.  
  200.     inline void skip_space() {
  201.         if (input_ptr_left + LEN > input_ptr_right) load();
  202.         while (input_buffer[input_ptr_left] <= ' ') input_ptr_left++;
  203.     }
  204.  
  205.     inline void flush() {
  206.         fwrite_unlocked(std::begin(output_buffer), 1, output_ptr_right, stdout);
  207.         output_ptr_right = 0;
  208.     }
  209.  
  210.     inline void write_char(char c) {
  211.         if (output_ptr_right > SZ - LEN) flush();
  212.         output_buffer[output_ptr_right++] = c;
  213.     }
  214.  
  215.     inline void write_bool(bool b) {
  216.         if (output_ptr_right > SZ - LEN) flush();
  217.         output_buffer[output_ptr_right++] = b ? '1' : '0';
  218.     }
  219.  
  220.     inline void write_string(const std::string& s) {
  221.         for (auto x : s) write_char(x);
  222.     }
  223.  
  224.     inline void write_string(const char* s) {
  225.         while (*s) write_char(*s++);
  226.     }
  227.  
  228.     inline void write_string(char* s) {
  229.         while (*s) write_char(*s++);
  230.     }
  231.  
  232.     template <typename T>
  233.     inline std::enable_if_t<std::is_integral_v<T>, void> write_int(T x) {
  234.         if (output_ptr_right > SZ - LEN) flush();
  235.         if (!x) {
  236.             output_buffer[output_ptr_right++] = '0';
  237.             return;
  238.         }
  239.         if constexpr (std::is_signed<T>::value == true)
  240.             if (x < 0) output_buffer[output_ptr_right++] = '-', x = -x;
  241.         int i = TWELVE;
  242.         std::array<char, SIXTEEN> buf{};
  243.         while (x >= TENTHOUSAND) {
  244.             memcpy(std::begin(buf) + i,
  245.                    std::begin(io_pre.num) + (x % TENTHOUSAND) * 4, 4);
  246.             x /= TENTHOUSAND;
  247.             i -= 4;
  248.         }
  249.         if (x < HUNDRED) {
  250.             if (x < TEN) {
  251.                 output_buffer[output_ptr_right++] = static_cast<char>('0' + x);
  252.             } else {
  253.                 std::uint32_t q =
  254.                     (static_cast<std::uint32_t>(x) * MAGIC_MULTIPLY) >>
  255.                     MAGIC_SHIFT;
  256.                 std::uint32_t r = static_cast<std::uint32_t>(x) - q * TEN;
  257.                 output_buffer[output_ptr_right] = static_cast<char>('0' + q);
  258.                 output_buffer[output_ptr_right + 1] =
  259.                     static_cast<char>('0' + r);
  260.                 output_ptr_right += 2;
  261.             }
  262.         } else {
  263.             if (x < THOUSAND) {
  264.                 memcpy(std::begin(output_buffer) + output_ptr_right,
  265.                        std::begin(io_pre.num) + (x << 2) + 1, 3),
  266.                     output_ptr_right += 3;
  267.             } else {
  268.                 memcpy(std::begin(output_buffer) + output_ptr_right,
  269.                        std::begin(io_pre.num) + (x << 2), 4),
  270.                     output_ptr_right += 4;
  271.             }
  272.         }
  273.         memcpy(std::begin(output_buffer) + output_ptr_right,
  274.                std::begin(buf) + i + 4, TWELVE - i);
  275.         output_ptr_right += TWELVE - i;
  276.     }
  277.     template <typename T_>
  278.     IO& operator<<(T_&& x) {
  279.         using T = typename std::remove_cv<
  280.             typename std::remove_reference<T_>::type>::type;
  281.         static_assert(is_custom<T>::value or is_default<T>::value or
  282.                       is_iterable<T>::value or is_applyable<T>::value);
  283.         if constexpr (is_custom<T>::value) {
  284.             write_int(x.get());
  285.         } else if constexpr (is_default<T>::value) {
  286.             if constexpr (is_bool<T>::value) {
  287.                 write_bool(x);
  288.             } else if constexpr (is_string<T>::value) {
  289.                 write_string(x);
  290.             } else if constexpr (is_char<T>::value) {
  291.                 write_char(x);
  292.             } else if constexpr (std::is_integral_v<T>) {
  293.                 write_int(x);
  294.             }
  295.         } else if constexpr (is_iterable<T>::value) {
  296.             // strings are immune
  297.             using E = decltype(*std::begin(x));
  298.             constexpr char sep = needs_newline<E> ? '\n' : ' ';
  299.             int i = 0;
  300.             for (const auto& y : x) {
  301.                 if (i++) write_char(sep);
  302.                 operator<<(y);
  303.             }
  304.         } else if constexpr (is_applyable<T>::value) {
  305.             // strings are immune
  306.             constexpr char sep =
  307.                 (any_needs_newline<
  308.                     T, std::make_index_sequence<std::tuple_size_v<T>>>::value)
  309.                     ? '\n'
  310.                     : ' ';
  311.             int i = 0;
  312.             std::apply(
  313.                 [this, &sep, &i](auto const&... y) {
  314.                     (((i++ ? write_char(sep) : void()), this->operator<<(y)),
  315.                      ...);
  316.                 },
  317.                 x);
  318.         }
  319.         return *this;
  320.     }
  321.     template <typename T>
  322.     IO& operator>>(T& x) {
  323.         static_assert(is_custom<T>::value or is_default<T>::value or
  324.                       is_iterable<T>::value or is_applyable<T>::value);
  325.         static_assert(!is_bool<T>::value);
  326.         if constexpr (is_custom<T>::value) {
  327.             typename T::internal_value_type y;
  328.             read_int(y);
  329.             x = y;
  330.         } else if constexpr (is_default<T>::value) {
  331.             if constexpr (is_string<T>::value) {
  332.                 read_string(x);
  333.             } else if constexpr (is_char<T>::value) {
  334.                 read_char(x);
  335.             } else if constexpr (std::is_integral_v<T>) {
  336.                 read_int(x);
  337.             }
  338.         } else if constexpr (is_iterable<T>::value) {
  339.             for (auto& y : x) operator>>(y);
  340.         } else if constexpr (is_applyable<T>::value) {
  341.             std::apply([this](auto&... y) { ((this->operator>>(y)), ...); }, x);
  342.         }
  343.         return *this;
  344.     }
  345.  
  346.     IO* tie(std::nullptr_t) {
  347.         return this;
  348.     }
  349.     void sync_with_stdio(bool) {}
  350. };
  351. IO io;
  352. #define cin io
  353. #define cout io
  354.  
  355. #define int long long
  356.  
  357. int d2[LG];
  358.  
  359. int t[2 * R][2];
  360.  
  361. void tag(int v, int x, int l) { t[v][0] = x * l, t[v][1] = x; }
  362. void push(int v, int l) {
  363.     if (~t[v][1]) {
  364.         tag(2 * v, t[v][1], l >> 1), tag(2 * v + 1, t[v][1], l >> 1);
  365.         t[v][1] = -1;
  366.     }
  367. }
  368.  
  369. // fuck you for making me use [l; r] instead of [l; r)
  370. void upd(int ql, int qr, int x, int k, int v = 1, int h = 19, int nl = 0, int nr = R - 1) {
  371.     if (ql == nl && qr == nr) return tag(v, x, nr - nl + 1);
  372.     push(v, nr - nl + 1);
  373.     int nm = (nl + (nr + 1)) >> 1;
  374.     if (qr <= nm - 1) {
  375.         if (k & d2[h]) upd(ql ^ d2[h], qr ^ d2[h], x, k, 2 * v + 1, h - 1, nm, nr);
  376.         else upd(ql, qr, x, k, 2 * v, h - 1, nl, nm - 1);
  377.     }
  378.     else if (ql >= nm) {
  379.         if (k & d2[h]) upd(ql ^ d2[h], qr ^ d2[h], x, k, 2 * v, h - 1, nl, nm - 1);
  380.         else upd(ql, qr, x, k, 2 * v + 1, h - 1, nm, nr);
  381.     }
  382.     else {
  383.         if (k & d2[h]) upd(nl, qr ^ d2[h], x, k, 2 * v, h - 1, nl, nm - 1), upd(ql ^ d2[h], nr, x, k, 2 * v + 1, h - 1, nm, nr);
  384.         else upd(ql, nm - 1, x, k, 2 * v, h - 1, nl, nm - 1), upd(nm, qr, x, k, 2 * v + 1, h - 1, nm, nr);
  385.     }
  386.     t[v][0] = t[2 * v][0] + t[2 * v + 1][0];
  387. }
  388. int get(int ql, int qr, int k, int v = 1, int h = 19, int nl = 0, int nr = R - 1) {
  389.     if (ql == nl && qr == nr) return t[v][0];
  390.     push(v, nr - nl + 1);
  391.     int nm = (nl + (nr + 1)) >> 1;
  392.     if (qr <= nm - 1) {
  393.         if (k & d2[h]) return get(ql ^ d2[h], qr ^ d2[h], k, 2 * v + 1, h - 1, nm, nr);
  394.         return get(ql, qr, k, 2 * v, h - 1, nl, nm - 1);
  395.     }
  396.     if (ql >= nm) {
  397.         if (k & d2[h]) return get(ql ^ d2[h], qr ^ d2[h], k, 2 * v, h - 1, nl, nm - 1);
  398.         return get(ql, qr, k, 2 * v + 1, h - 1, nm, nr);
  399.     }
  400.     if (k & d2[h]) return get(nl, qr ^ d2[h], k, 2 * v, h - 1, nl, nm - 1) + get(ql ^ d2[h], nr, k, 2 * v + 1, h - 1, nm, nr);
  401.     return get(ql, nm - 1, k, 2 * v, h - 1, nl, nm - 1) + get(nm, qr, k, 2 * v + 1, h - 1, nm, nr);
  402. }
  403.  
  404. signed main() {
  405.     FOR(i, 0, LG) d2[i] = 1 << i;
  406.     FOR(i, 1, 2 * R) t[i][1] = -1;
  407.     fastIO;
  408.     int n; cin >> n;
  409.     FOR(i, 0, 1 << n) cin >> t[R + i][0];
  410.     RFOR(i, R - 1, 1) t[i][0] = t[2 * i][0] + t[2 * i + 1][0];
  411.     int q; cin >> q;
  412.     while (q--) {
  413.         int op, l, r, k; cin >> op >> l >> r >> k;
  414.         if (op == 1) {
  415.             int x; cin >> x;
  416.             upd(l, r, x, k);
  417.         }
  418.         else cout << get(l, r, k) << endl;
  419.     }
  420. }
  421.  
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!