結果
問題 | No.2879 Range Flip Queries |
ユーザー |
|
提出日時 | 2024-09-08 12:55:42 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 470 ms / 2,000 ms |
コード長 | 2,421 bytes |
コンパイル時間 | 1,662 ms |
コンパイル使用メモリ | 132,196 KB |
実行使用メモリ | 7,420 KB |
最終ジャッジ日時 | 2024-09-08 12:55:57 |
合計ジャッジ時間 | 13,009 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#line 1 "main.cpp"#pragma GCC optimize("Ofast")#pragma GCC optimize("unroll-loops")#ifdef local#include <C++/core/io/debug_print.hpp>#else#define dump(...) void(0);#endif#include <iostream>#include <ranges>#line 2 "/home/wa_haya_exe/CP_Library/C++/ds/DualSegmentTree.hpp"#pragma GCC diagnostic ignored "-Wreorder"#include <vector>#include <functional>template <class T> struct DualSegTree {private:using F = std::function<T(T, T)>;int sz, h;std::vector<T> lazy;const T id;const F ap;inline void propagate(const int k) {if(lazy[k] != id) {lazy[2 * k] = ap(lazy[2 * k], lazy[k]);lazy[2 * k + 1] = ap(lazy[2 * k + 1], lazy[k]);lazy[k] = id;}}inline void thrust(const int k) {for(int i = h; i > 0; i--) {propagate(k >> i);}}public:DualSegTree(const int n, const F &ap, const T &id): ap(ap), id(id) {sz = 1;h = 0;while(sz < n) {sz <<= 1;h++;}lazy.assign(2 * sz, id);}void apply(int a, int b, const T &x) {thrust(a += sz);thrust(b += sz - 1);for(int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {if(l & 1) {lazy[l] = ap(lazy[l], x);l++;}if(r & 1) {r--;lazy[r] = ap(lazy[r], x);}}}inline T operator[](int k) {thrust(k += sz);return lazy[k];}};/*** @brief 双対セグ木* @see https://ei1333.github.io/library/structure/segment-tree/dual-segment-tree.hpp*/#line 12 "main.cpp"namespace man {}int main() {std::cin.tie(nullptr) -> sync_with_stdio(false);using namespace std::ranges;using namespace std::views;int n, q;std::cin >> n >> q;DualSegTree<int> seg(n, [](const int a, const int b) -> int { return a ^ b; }, 0);for(const auto &i: iota(0, n)) {int a;std::cin >> a;seg.apply(i, i + 1, a);}// for(const auto i: iota(0, n)) {// std::cout << seg[i] << " \n"[i + 1 == n];// }for([[maybe_unused]] const auto _: iota(0, q)) {int l, r;std::cin >> l >> r;seg.apply(--l, r, 1);}for(const auto i: iota(0, n)) {std::cout << seg[i] << " \n"[i + 1 == n];}}