#816151 (C++17) No.925 紲星 Extra

提出ソース
結果

問題	No.925 紲星 Extra
コンテスト
ユーザー	hashiryo
提出日時	2022-11-14 23:17:36
言語	C++17 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	5,989 ms / 10,000 ms
コード長	13,586 bytes
コンパイル時間	4,084 ms
コンパイル使用メモリ	265,480 KB
最終ジャッジ日時	2025-02-08 20:21:42
ジャッジサーバーID （参考情報）	judge1 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 3
other	AC * 19
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/stdc++.h>
#ifndef TEMP
#define TEMP
// clang-format off
template <class T, class U>std::ostream &operator<<(std::ostream &os, const std::pair<T, U> &x) {  return os << "(" << x.first << ", " << x.second << ")";}
template <typename T>std::ostream &operator<<(std::ostream &os, const std::vector<T> &vec) {os << '[';for (int _ = 0, __ = vec.size(); _ < __; _++) os << (_ ? ", " : "") << vec[_];return os << ']';}
template <typename T>std::ostream &operator<<(std::ostream &os, const std::set<T> &s) { os << '{'; int _ = 0; for (const auto &x : s) os << (_++ ? ", " : "") << x; return os << '}';}
template <typename T, std::size_t _Nm>std::ostream &operator<<(std::ostream &os, const std::array<T, _Nm> &arr) {  os << '[' << arr[0];  for (std::size_t _ = 1; _ < _Nm; _++) os << ", " << arr[_];  return os << ']';}
template <class Tup, std::size_t... I>void print(std::ostream &os, const Tup &x, std::index_sequence<I...>) {  using swallow = int[];  (void)swallow{(os << std::get<I>(x) << ", ", 0)...};}
template <class... Args>std::ostream &operator<<(std::ostream &os, const std::tuple<Args...> &x) {  static constexpr std::size_t N = sizeof...(Args);  os << "(";  if constexpr (N >= 2) print(os, x, std::make_index_sequence<N - 1>());  return os << std::get<N - 1>(x) << ")";}
std::ostream &operator<<(std::ostream &os, std::int8_t x) {return os << (int)x;}
std::ostream &operator<<(std::ostream &os, std::uint8_t x) {return os << (int)x;}
std::ostream &operator<<(std::ostream &os, const __int128_t &v) {if (v == 0) os << "0";__int128_t tmp = v < 0 ? (os << "-", -v) : v;std::string s;while (tmp) s += '0' + (tmp % 10), tmp /= 10;return std::reverse(s.begin(), s.end()), os << s;}
std::ostream &operator<<(std::ostream &os, const __uint128_t &v) {if (v == 0) os << "0";__uint128_t tmp = v;std::string s;while (tmp) s += '0' + (tmp % 10), tmp /= 10;return std::reverse(s.begin(), s.end()), os << s;}
#ifdef __LOCAL
const std::string COLOR_RESET = "\033[0m", BRIGHT_GREEN = "\033[1;32m", BRIGHT_RED = "\033[1;31m", BRIGHT_CYAN = "\033[1;36m", NORMAL_CROSSED = "\033[0;9;37m", ITALIC = "\033[3m", BOLD = "\033[1m", RED_BACKGROUND = "\033[1;41m", NORMAL_FAINT = "\033[0;2m";
#define func_LINE_FILE  NORMAL_FAINT << " in " << BOLD << __func__ << NORMAL_FAINT << ITALIC << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET
#define checkpoint() std::cerr << BRIGHT_RED << "< check point! >" << func_LINE_FILE << '\n'
#define debug(x) std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << func_LINE_FILE << '\n'
#define debugArray(x, n) do { std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = [" << x[0]; for (int _ = 1; _ < (int)(n); ++_) std::cerr << ", " << x[_]; std::cerr << "]" << func_LINE_FILE << '\n'; } while (0)
#define debugMatrix(x, h, w) do { std::cerr << BRIGHT_CYAN << #x << "\n" << COLOR_RESET << "= "; for (int _ = 0; (_) < (int)(h); ++_) { std::cerr << ((_ ? "   [" : "[[")); for (int __ = 0; __ < (int)(w); ++__) std::cerr << ((__ ? ", " : "")) << x[_][__]; std::cerr << "]" << (_ + 1 == (int)(h) ? "]" : ",\n"); } std::cerr << func_LINE_FILE << '\n'; } while (0)
#else
#define checkpoint() (void(0))
#define debug(x) (void(0))
#define debugArray(x, n) (void(0))
#define debugMatrix(x, h, w) (void(0))
#endif
template <class T>auto compress(std::vector<T> &v) { std::sort(v.begin(), v.end()); v.erase(std::unique(v.begin(), v.end()), v.end()); return [&v](T x) { return std::lower_bound(v.begin(), v.end(), x) - v.begin(); };}
struct ClosedSection { long long l, r; ClosedSection() : l(1), r(0) {} ClosedSection(long long l_, long long r_) : l(l_), r(r_) {} bool valid() { return l <= r; }};
/* closed [l,r] */ template <class Check> ClosedSection bin_search(const Check &isok, long long l, long long r) { bool res_l = isok(l), res_r = isok(r); if (res_l && res_r) return ClosedSection(l, r); if (!res_l && !res_r) return ClosedSection(); long long lb = l, ub = r; for (long long x; ub - lb > 1;) (isok(x = (lb + ub) / 2) == res_l ? lb : ub) = x; return res_l ? ClosedSection(l, lb) : ClosedSection(ub, r);}
template <class Check> ClosedSection bin_search(const Check &isok, ClosedSection cs) { return cs.valid() ? bin_search(isok, cs.l, cs.r) : cs; }
// clang-format on
#endif

template <class T, std::size_t B = 700>
class RangeChminChmaxAddSumQuery {
  static constexpr T INF = std::numeric_limits<T>::max() / 2;
  struct Dat {
    const std::size_t n;
    std::array<T, B> a, sorted;
    std::array<T, B + 1> acc;
    T add, lb, ub;
    Dat(std::size_t b)
        : n(b), a{0}, sorted{0}, acc{0}, add(0), lb(-INF), ub(INF) {}
    Dat(const T *bg, std::size_t b)
        : n(b), a{0}, acc{0}, add(0), lb(-INF), ub(INF) {
      for (int i = n; i--;) a[i] = *(bg + i);
      build();
    }
    inline bool eval() {
      if (add == 0 && lb == -INF && ub == INF) return false;
      for (auto &x : a) x = std::clamp(x, lb, ub) + add;
      return add = 0, lb = -INF, ub = INF, true;
    }
    inline void build() {
      sorted = a, std::sort(sorted.begin(), sorted.begin() + n);
      std::partial_sum(sorted.begin(), sorted.begin() + n, acc.begin() + 1);
    }
    inline std::size_t idx(T x) const {
      return std::lower_bound(sorted.begin(), sorted.begin() + n, x) -
             sorted.begin();
    }
    inline std::size_t count(T x) const {
      return x -= add, (x <= lb ? 0 : ub < x ? n : idx(x));
    }
    inline T sum() const {
      std::size_t l = idx(lb), u = idx(ub);
      return acc[u] - acc[l] + lb * l + ub * (n - u) + add * n;
    }
    inline T sum(T x) const {
      if (x -= add; x <= lb) return 0;
      if (ub < x) return sum();
      std::size_t l = idx(lb), u = idx(x);
      return acc[u] - acc[l] + lb * l + add * u;
    }
    inline T get(std::size_t k) const { return std::clamp(a[k], lb, ub) + add; }
  };
  const std::size_t n;
  std::vector<Dat> dat;
  template <class U, class All, class One>
  inline U fold(std::size_t l, std::size_t r, const All &all,
                const One &one) const {
    U ret = 0;
    if (std::size_t i = l / B, j = r / B, k = l % B, m = r % B; i < j) {
      if (k) {
        for (; k < dat[i].n; k++) ret += one(dat[i].get(k));
        i++;
      }
      for (; i < j; i++) ret += all(dat[i]);
      if (m)
        for (; m--;) ret += one(dat[j].get(m));
    } else
      for (; k < m; k++) ret += one(dat[i].get(k));
    return ret;
  }
  template <class All, class One>
  inline void update(std::size_t l, std::size_t r, const All &all,
                     const One &one) {
    if (std::size_t i = l / B, j = r / B, k = l % B, m = r % B; i < j) {
      if (k) {
        for (dat[i].eval(); k < dat[i].n; k++) one(dat[i].a[k]);
        dat[i].build(), i++;
      }
      for (; i < j; i++) all(dat[i]);
      if (m) {
        for (dat[j].eval(); m--;) one(dat[j].a[m]);
        dat[j].build();
      }
    } else {
      for (dat[i].eval(); k < m; k++) one(dat[i].a[k]);
      dat[i].build();
    }
  }

 public:
  RangeChminChmaxAddSumQuery(std::size_t n_) : n(n_) {
    for (int l = 0, r; l < n; l = r)
      r = std::min(l + B, n), dat.emplace_back(r - l);
  }
  RangeChminChmaxAddSumQuery(const std::vector<T> &a) : n(a.size()) {
    for (int l = 0, r; l < n; l = r)
      r = std::min(l + B, n), dat.emplace_back(a.data() + l, r - l);
  }
  // count i s.t. (l <= i < r) && (a[i] < ub)
  std::size_t count(std::size_t l, std::size_t r, T ub) const {
    return fold<std::size_t>(
        l, r, [&](const Dat &d) { return d.count(ub); },
        [&](T x) { return x < ub; });
  }
  // count i s.t. (l <= i < r) && (lb <= a[i] < ub)
  std::size_t count(std::size_t l, std::size_t r, T lb, T ub) const {
    return count(l, r, ub) - count(l, r, lb);
  }
  // sum a[i] s.t. (l <= i < r)
  T sum(std::size_t l, std::size_t r) const {
    return fold<T>(
        l, r, [&](const Dat &d) { return d.sum(); }, [&](T x) { return x; });
  }
  // sum a[i] s.t. (l <= i < r) && (a[i] < ub)
  T sum(std::size_t l, std::size_t r, T ub) const {
    return fold<T>(
        l, r, [&](const Dat &d) { return d.sum(ub); },
        [&](T x) { return x < ub ? x : 0; });
  }
  // sum a[i] s.t. (l <= i < r)  && (lb <= a[i] < ub)
  T sum(std::size_t l, std::size_t r, T lb, T ub) const {
    return sum(l, r, ub) - sum(l, r, lb);
  }
  void set(std::size_t k, T x) {
    std::size_t i = k / B, j = k % B;
    dat[i].eval(), dat[i].a[j] = x, dat[i].build();
  }
  T get(std::size_t k) const { return dat[k / B].get(k % B); }
  T operator[](std::size_t k) const { return get(k); }
  void add(std::size_t l, std::size_t r, T v) {
    update(
        l, r, [&](Dat &d) { d.add += v; }, [&](T &x) { x += v; });
  }
  void chmin(std::size_t l, std::size_t r, T ub) {
    auto f = [&](Dat &d) {
      T b = ub - d.add;
      d.ub = std::min(d.ub, b), d.lb = std::min(d.lb, b);
    };
    update(l, r, f, [&](T &x) { x = std::min(x, ub); });
  }
  void chmax(std::size_t l, std::size_t r, T lb) {
    auto f = [&](Dat &d) {
      T a = lb - d.add;
      d.lb = std::max(d.lb, a), d.ub = std::max(d.ub, a);
    };
    update(l, r, f, [&](T &x) { x = std::max(x, lb); });
  }
  void chclamp(std::size_t l, std::size_t r, T lb, T ub) {
    auto f = [&](Dat &d) {
      T a = lb - d.add, b = ub - d.add;
      d.ub = std::clamp(d.ub, a, b), d.lb = std::clamp(d.lb, a, b);
    };
    update(l, r, f, [&](T &x) { x = std::clamp(x, lb, ub); });
  }
};

using namespace std;

// https://judge.yosupo.jp/problem/range_chmin_chmax_add_range_sum
namespace yosupo_range_chmin_chmax_add_range_sum {
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  int N, Q;
  cin >> N >> Q;
  vector<long long> a(N);
  for (int i = 0; i < N; i++) cin >> a[i];
  RangeChminChmaxAddSumQuery<long long> sqrtdc(a);
  while (Q--) {
    int op, l, r;
    cin >> op >> l >> r;
    if (op == 3) {
      cout << sqrtdc.sum(l, r) << '\n';
    } else {
      long long b;
      cin >> b;
      if (op == 0) sqrtdc.chmin(l, r, b);
      if (op == 1) sqrtdc.chmax(l, r, b);
      if (op == 2) sqrtdc.add(l, r, b);
    }
  }
  return 0;
}
}  // namespace yosupo_range_chmin_chmax_add_range_sum

// https://onlinejudge.u-aizu.ac.jp/problems/3170
namespace AOJ_3170 {
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  int N, Q;
  cin >> N >> Q;
  vector<long long> a(N);
  for (int i = 0; i < N; i++) cin >> a[i];
  RangeChminChmaxAddSumQuery<long long, 100> sqrtdc(a);
  while (Q--) {
    int op, l, r;
    long long x;
    cin >> op >> l >> r >> x;
    l--;
    if (op == 4) {
      long long y;
      cin >> y;
      cout << sqrtdc.count(l, r, x, y + 1) << '\n';
    } else {
      if (op == 1) sqrtdc.chmin(l, r, x);
      if (op == 2) sqrtdc.chmax(l, r, x);
      if (op == 3) sqrtdc.add(l, r, x);
    }
  }
  return 0;
}
}  // namespace AOJ_3170

// https://yukicoder.me/problems/no/925
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

namespace yuki925 {

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  int N, Q;
  cin >> N >> Q;
  vector<long long> a(N);
  for (int i = 0; i < N; i++) cin >> a[i];
  RangeChminChmaxAddSumQuery<long long, 1024> sqrtdc(a);
  long long s = 0;
  tree<long long, null_type, less<long long>, rb_tree_tag,
       tree_order_statistics_node_update>
      S(a.begin(), a.end());
  while (Q--) {
    int op;
    cin >> op;
    if (op == 1) {
      long long X, Y;
      cin >> X >> Y;
      (X ^= s) &= (1 << 16) - 1, (Y ^= s) &= (1ll << 40) - 1;
      X--;
      sqrtdc.set(X, Y);
      S.insert(Y);
    } else {
      int L, R;
      cin >> L >> R;
      (L ^= s) &= (1 << 16) - 1, (R ^= s) &= (1 << 16) - 1;
      if (L > R) swap(L, R);
      L--;
      int m = (R - L) / 2;
      auto cs = bin_search(
          [&](int i) { return sqrtdc.count(L, R, *S.find_by_order(i)) <= m; },
          0, S.size() - 1);
      long long x = *S.find_by_order(cs.r);
      long long ans = sqrtdc.sum(L, R) - sqrtdc.sum(L, R, x) * 2;
      ans -= x * (R - L - sqrtdc.count(L, R, x) * 2);
      cout << ans << '\n';
      s ^= ans;
    }
  }
  return 0;
}
}  // namespace yuki925

namespace yosupo_range_kth_smallest {
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  int N, Q;
  cin >> N >> Q;
  vector<long long> a(N);
  for (int i = 0; i < N; i++) cin >> a[i];
  RangeChminChmaxAddSumQuery<long long, 1200> sqrtdc(a);
  compress(a);
  while (Q--) {
    int l, r, k;
    cin >> l >> r >> k;
    auto cs = bin_search([&](int i) { return sqrtdc.count(l, r, a[i]) <= k; },
                         0, a.size() - 1);
    auto x = a[cs.r];
    cout << x << '\n';
  }
  return 0;
}
}  // namespace yosupo_range_kth_smallest

// https://www.hackerrank.com/challenges/library-query/problem
namespace hr_library_query {
//  動的wavletな問題
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  int T;
  for (cin >> T; T--;) {
    int N;
    cin >> N;
    vector<int> a(N);
    for (int i = 0; i < N; i++) cin >> a[i];
    RangeChminChmaxAddSumQuery<int, 50> sqrtdc(a);
    int Q;
    cin >> Q;
    while (Q--) {
      int type;
      cin >> type;
      if (type) {
        int x, k;
        cin >> x >> k, x--;
        sqrtdc.set(x, k);
      } else {
        int x, y, k;
        cin >> x >> y >> k, x--;
        auto cs = bin_search([&](int t) { return sqrtdc.count(x, y, t) < k; },
                             1, 1000);
        cout << cs.r << '\n';
      }
    }
  }
  return 0;
}
}  // namespace hr_library_query

signed main() {
  // yosupo_range_chmin_chmax_add_range_sum::main();
  // AOJ_3170::main();
  yuki925::main();
  // yosupo_range_kth_smallest::main();
  // hr_library_query::main();
  return 0;
}