結果
問題 |
No.3205 Range Pairwise Xor Query
|
ユーザー |
|
提出日時 | 2025-07-19 12:46:52 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 797 ms / 2,000 ms |
コード長 | 5,616 bytes |
コンパイル時間 | 3,253 ms |
コンパイル使用メモリ | 283,864 KB |
実行使用メモリ | 46,336 KB |
最終ジャッジ日時 | 2025-07-19 12:47:07 |
合計ジャッジ時間 | 14,506 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 20 |
ソースコード
#line 2 "template.hpp" // #pragma GCC target("avx2") // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include <debug.hpp> #else template <class T> concept Streamable = requires(ostream os, T &x) { os << x; }; template <class mint> concept is_modint = requires(mint &x) { { x.val() } -> std::convertible_to<int>; }; #define debug(...) #endif template <Streamable T> void print_one(const T &value) { cout << value; } template <is_modint T> void print_one(const T &value) { cout << value.val(); } void print() { cout << '\n'; } template <class T, class... Ts> void print(const T &a, const Ts &...b) { print_one(a); ((cout << ' ', print_one(b)), ...); cout << '\n'; } template <ranges::range Iterable> requires(!Streamable<Iterable>) void print(const Iterable &v) { for(auto it = v.begin(); it != v.end(); ++it) { if(it != v.begin()) cout << " "; print_one(*it); } cout << '\n'; } using vi = vector<int>; using vii = vector<vector<int>>; using pii = pair<int, int>; using ll = long long; using vl = vector<ll>; using vll = vector<vl>; using pll = pair<ll, ll>; #define all(v) begin(v), end(v) template <class T> void UNIQUE(T &v) { ranges::sort(v); v.erase(unique(all(v)), end(v)); } template <typename T> inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); } template <typename T> inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); } // https://trap.jp/post/1224/ template <class... T> constexpr auto min(T... a) { return min(initializer_list<common_type_t<T...>>{a...}); } template <class... T> constexpr auto max(T... a) { return max(initializer_list<common_type_t<T...>>{a...}); } template <class... T> void input(T &...a) { (cin >> ... >> a); } template <class T> void input(vector<T> &a) { for(T &x : a) cin >> x; } #define INT(...) \ int __VA_ARGS__; \ input(__VA_ARGS__) #define LL(...) \ long long __VA_ARGS__; \ input(__VA_ARGS__) #define STR(...) \ string __VA_ARGS__; \ input(__VA_ARGS__) #define REP1_0(n, c) REP1_1(n, c) #define REP1_1(n, c) \ for(ll REP_COUNTER_##c = 0; REP_COUNTER_##c < (ll)(n); REP_COUNTER_##c++) #define REP1(n) REP1_0(n, __COUNTER__) #define REP2(i, a) for(ll i = 0; i < (ll)(a); i++) #define REP3(i, a, b) for(ll i = (ll)(a); i < (ll)(b); i++) #define REP4(i, a, b, c) for(ll i = (ll)(a); i < (ll)(b); i += (ll)(c)) #define overload4(a, b, c, d, e, ...) e #define rep(...) overload4(__VA_ARGS__, REP4, REP3, REP2, REP1)(__VA_ARGS__) ll inf = 3e18; vl dx = {1, -1, 0, 0}; vl dy = {0, 0, 1, -1}; template <class T> constexpr T floor(T x, T y) noexcept { return x / y - ((x ^ y) < 0 and x % y); } template <class T> constexpr T ceil(T x, T y) noexcept { return x / y + ((x ^ y) >= 0 and x % y); } // yの符号に関わらず非負で定義 \bmod:texコマンド template <class T> constexpr T bmod(T x, T y) noexcept { T m = x % y; return (m < 0) ? m + (y > 0 ? y : -y) : m; } template <std::signed_integral T> constexpr int bit_width(T x) noexcept { return std::bit_width((uint64_t)x); } template <std::signed_integral T> constexpr int popcount(T x) noexcept { return std::popcount((uint64_t)x); } constexpr bool kth_bit(auto n, auto k) { return (n >> k) & 1; } #line 3 "dp/cumulative-sum.hpp" // https://ei1333.github.io/library/dp/cumulative-sum.hpp template <class T = long long> struct CumulativeSum { bool is_built = false; int sz; vector<T> data; CumulativeSum() = default; CumulativeSum(int maxi) : sz(maxi + 1), data(maxi + 1, 0) {} CumulativeSum(const vector<T> &v) : sz(v.size() + 1) { data = {T(0)}; data.reserve(sz); for(auto &&x : v) { data.push_back(data.back() + x); } is_built = true; } void add(int x, T dx) { assert(0 <= x and x < sz); data[x + 1] += dx; is_built = false; } void build() { if(is_built) return; is_built = true; rep(i, sz - 1) { data[i + 1] += data[i]; } } T sum(int r) { // 区間[0,r)の和 assert(0 <= r and r < sz); assert(is_built); return data[r]; } T sum(int l, int r) { // 区間[l,r)の和 assert(is_built); assert(0 <= l and l <= r and r < sz); return sum(r) - sum(l); } T all_sum() { assert(is_built); return data.back(); } const T operator[](int t) { // "累積和をとる前の" t での値 assert(0 <= t and t < sz); assert(is_built); return data[t + 1] - data[t]; } }; #line 3 "/home/y_midori/cp/a.cpp" int main() { INT(n, q); vi a(n); input(a); int len = 26; vector<CumulativeSum<ll>> sum(len, n); rep(i, n) { rep(j, len) { sum[j].add(i, kth_bit(a[i], j)); } } rep(i, len) sum[i].build(); rep(q) { INT(l, r); --l; ll ans = 0; rep(i, len) { ll num = sum[i].sum(l, r); ans += (1LL << i) * num * (r - l - num); } print(ans); } }