結果

問題 No.879 Range Mod 2 Query
ユーザー テナガザルテナガザル
提出日時 2024-08-04 03:48:03
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,589 bytes
コンパイル時間 1,401 ms
コンパイル使用メモリ 118,616 KB
実行使用メモリ 16,248 KB
最終ジャッジ日時 2024-08-04 03:48:12
合計ジャッジ時間 7,291 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 AC 472 ms
15,804 KB
testcase_20 AC 449 ms
15,880 KB
testcase_21 AC 496 ms
15,772 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

template <typename T, typename X> class LazySegTree
{
private:
  const T et;
  const X ex;
  int num;
  std::vector<T> dat;
  std::vector<X> lazy;
  T (*const eval)(const T, const T) {};
  T (*const fa)(const T, const X) {};
  X (*const fm)(const X, const X) {};
  X (*const fp)(const X, int) {};
    
public:
  LazySegTree(std::vector<T> &v, T Et, X Ex, T (*valcal)(T, T), T (*lazyupdate)(T, X), X (*lazypropagation)(X, X), X (*rangelazy)(X, int)) : et(Et), ex(Ex), eval(valcal), fa(lazyupdate), fm(lazypropagation), fp(rangelazy)
  {
    int siz = static_cast<int>(v.size());
    for (num = 1; num < siz; num <<= 1);
    dat = std::vector<T> (2 * num - 1, et);
    lazy = std::vector<X> (2 * num - 1, ex);
    for (int i = 0; i < siz; ++i) dat[i + num - 1] = v[i];
    for (int i = num - 2; i >= 0; --i) dat[i] = eval(dat[i * 2 + 1], dat[i * 2 + 2]);
  }

  LazySegTree(int n, T Et, X Ex, T (*valcal)(T, T), T (*lazyupdate)(T, X), X (*lazypropagation)(X, X), X (*rangelazy)(X, int)) : et(Et), ex(Ex), eval(valcal), fa(lazyupdate), fm(lazypropagation), fp(rangelazy)
  {
    for (num = 1; num < n; num <<= 1);
    dat = std::vector<T> (2 * num - 1, et);
    lazy = std::vector<X> (2 * num - 1, ex);
  }

  //update [left,right)
  void rangeupdate(int left, int right, X val)
  {
    std::stack<std::pair<int, int>> st;
    std::stack<int> s;
    for (st.push({0, num}); !st.empty();)
    {
      auto v = st.top();
      st.pop();
      int now = (num + v.first) / (v.second - v.first) - 1;
      lazyupdate(now, v.second - v.first);
      if (left <= v.first && v.second <= right)
      {
        lazy[now] = fm(lazy[now], val);
        lazyupdate(now, v.second - v.first);
      }
      else if (!(v.second <= left || right <= v.first))
      {
        st.push({(v.first + v.second) / 2, v.second});
        st.push({v.first, (v.first + v.second) / 2});
        s.push(now);
      }
    }
    while (!s.empty())
    {
      int index = s.top();
      dat[index] = eval(dat[2 * index + 1], dat[2 * index + 2]);
      s.pop();
    }
  }

  //get value [left,right)
  T getval(int left, int right)
  {
    std::stack<std::pair<int, int>> s;
    T ans = et;
    for (s.push({0, num}); !s.empty();)
    {
      auto v = s.top();
      s.pop();
      int now = (num + v.first) / (v.second - v.first) - 1;
      lazyupdate(now, v.second - v.first);
      if (left <= v.first && v.second <= right) ans = eval(ans, dat[now]);
      else if (!(v.second <= left || right <= v.first))
      {
        s.push({(v.first + v.second) / 2, v.second});
        s.push({v.first, (v.first + v.second) / 2});
      }
    }
    return ans;
  }

  //get value [id]
  T getval(int id) {return getval(id, id + 1);}

private:
  void lazyupdate(int index, int len)
  {
    if (lazy[index] == ex) return;
    if (index < num - 1)
    {
      lazy[index * 2 + 1] = fm(lazy[index * 2 + 1], lazy[index]);
      lazy[index * 2 + 2] = fm(lazy[index * 2 + 2], lazy[index]);
    }
    dat[index] = fa(dat[index], fp(lazy[index], len));
    lazy[index] = ex;
  }
};

int main()
{
  struct dat
  {
    int cnt0, cnt1, len;
    long long sum;
    dat(int c0, int c1, int l, long long v) : cnt0(c0), cnt1(c1), len(l), sum(v) {}
  };
  auto eval = [](dat a, dat b) -> dat {return dat(a.cnt0 + b.cnt0, a.cnt1 + b.cnt1, a.len + b.len, a.sum + b.sum);};
  auto fa = [](dat a, pair<bool, long long> b) -> dat
  {
    if (b.first) a.sum = a.cnt1;
    a.sum += b.second * a.len;
    if (b.second % 2) swap(a.cnt1, a.cnt0);
    return a;
  };
  auto fm = [](pair<bool, long long> a, pair<bool, long long> b) -> pair<bool, long long>
  {
    if (b.first) a.second = 0;
    a.first |= b.first;
    a.second += b.second;
    return a;
  };
  auto fp = [](pair<bool, long long> a, int b) -> pair<bool, long long>
  {
    return a;
  };
  int n, q;
  cin >> n >> q;
  vector<dat> v;
  dat e(0, 0, 1, 0);
  for (int i = 0; i < n; ++i)
  {
    int a;
    cin >> a;
    v.push_back(dat((a + 1) % 2, a % 2, 1, a));
  }
  LazySegTree<dat, pair<bool, long long>> lsg(v, e, {false, 0}, eval, fa, fm, fp);
  while (q--)
  {
    int t;
    cin >> t;
    if (t == 1)
    {
      int l, r;
      cin >> l >> r;
      --l;
      lsg.rangeupdate(l, r, {true, 0});
    }
    else if (t == 2)
    {
      int l, r, x;
      cin >> l >> r >> x;
      --l;
      lsg.rangeupdate(l, r, {false, x});
    }
    else if (t == 3)
    {
      int l, r;
      cin >> l >> r;
      --l;
      auto res = lsg.getval(l, r);
      cout << res.sum << endl;
    }
  }
}
0