#include #ifndef TEMP #define TEMP // clang-format off template std::ostream &operator<<(std::ostream &os, const std::pair &x) { return os << "(" << x.first << ", " << x.second << ")";} template std::ostream &operator<<(std::ostream &os, const std::vector &vec) {os << '[';for (int _ = 0, __ = vec.size(); _ < __; _++) os << (_ ? ", " : "") << vec[_];return os << ']';} template std::ostream &operator<<(std::ostream &os, const std::set &s) { os << '{'; int _ = 0; for (const auto &x : s) os << (_++ ? ", " : "") << x; return os << '}';} template std::ostream &operator<<(std::ostream &os, const std::array &arr) { os << '[' << arr[0]; for (std::size_t _ = 1; _ < _Nm; _++) os << ", " << arr[_]; return os << ']';} template void print(std::ostream &os, const Tup &x, std::index_sequence) { using swallow = int[]; (void)swallow{(os << std::get(x) << ", ", 0)...};} template std::ostream &operator<<(std::ostream &os, const std::tuple &x) { static constexpr std::size_t N = sizeof...(Args); os << "("; if constexpr (N >= 2) print(os, x, std::make_index_sequence()); return os << std::get(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 auto compress(std::vector &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 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 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 RangeChminChmaxAddSumQuery { static constexpr T INF = std::numeric_limits::max() / 2; struct Dat { const std::size_t n; std::array a, sorted; std::array 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); for (int i = 0; i < n; i++) acc[i + 1] = acc[i] + sorted[i]; } 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; template 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 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 &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( 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( 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( 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 a(N); for (int i = 0; i < N; i++) cin >> a[i]; RangeChminChmaxAddSumQuery 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 a(N); for (int i = 0; i < N; i++) cin >> a[i]; RangeChminChmaxAddSumQuery 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 #include using namespace __gnu_pbds; namespace yuki925 { signed main() { cin.tie(0); ios::sync_with_stdio(0); int N, Q; cin >> N >> Q; vector a(N); for (int i = 0; i < N; i++) cin >> a[i]; RangeChminChmaxAddSumQuery sqrtdc(a); long long s = 0; tree, 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 a(N); for (int i = 0; i < N; i++) cin >> a[i]; RangeChminChmaxAddSumQuery 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 a(N); for (int i = 0; i < N; i++) cin >> a[i]; RangeChminChmaxAddSumQuery 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; }