結果
問題 |
No.3205 Range Pairwise Xor Query
|
ユーザー |
|
提出日時 | 2025-07-18 23:18:41 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 36,253 bytes |
コンパイル時間 | 4,340 ms |
コンパイル使用メモリ | 319,008 KB |
実行使用メモリ | 814,672 KB |
最終ジャッジ日時 | 2025-07-18 23:18:50 |
合計ジャッジ時間 | 7,576 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 1 |
other | WA * 5 MLE * 1 -- * 14 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using vl = vector<ll>; using vvl = vector<vl>; using vvvl = vector<vvl>; using xy = pair<ll, ll>; using vxy = vector<xy>; using vvxy = vector<vxy>; using bs8 = bitset<8>; using bs16 = bitset<16>; using bs32 = bitset<32>; using bs64 = bitset<64>; using vbs8 = vector<bs8>; using vbs16 = vector<bs16>; using vbs32 = vector<bs32>; using vbs64 = vector<bs64>; using vs = vector<string>; using vvs = vector<vs>; using ull = unsigned long long; using vul = vector<ull>; using vd = vector<double>; using vvd = vector<vd>; using coord = pair<double, double>; using vcoord = vector<coord>; #define rep(var, n) for (ll var = 0; var < (n); var++) #define cnt(var, n, m) for (ll var = (n); var <= (m); var++) #define rcnt(var, n, m) for (ll var = (n); var >= (m); var--) #define each(ite, C) for (auto ite = (C).begin(); ite != (C).end(); ite++) #define reach(ite, C) for (auto ite = (C).rbegin(); ite != (C).rend(); ite++) #define yn(b) cout << (((b) > 0) ? "Yes" : "No") << endl; ///////////////////////////////////////////////// namespace zz_time { /// @brief プログラム実行時のタイムポイント std::chrono::_V2::system_clock::time_point START_TIME = std::chrono::system_clock::now(); /// @brief プログラム実行から経過時間をミリ秒で取得 /// @param st 経過開始時刻(基本引数指定する必要なし) /// @return 経過時間ミリ秒 ll currentTime(std::chrono::_V2::system_clock::time_point st = START_TIME) { std::chrono::_V2::system_clock::time_point now = std::chrono::system_clock::now(); return (ll)(std::chrono::duration_cast<std::chrono::milliseconds>(now - st) .count()); }; /// @brief 実行時間が超過していないかの判定 /// @param mSec 実行時間制約ミリ秒 /// @return 実行時間制約以下であればtrue,その他はfalse bool punctualityTime(const ll& mSec) { return (currentTime() < mSec); } /// @brief 実行時間が超過しているかの判定 /// @param mSec 実行時間制約ミリ秒 /// @return 実行時間制約超過していればtrue,その他はfalse bool spendTime(const ll& mSec) { return (currentTime() >= mSec); } }; // namespace zz_time using namespace zz_time; namespace zz_random { random_device seed_gen; default_random_engine RANDOM_ENGINE(seed_gen()); /// @brief 整数閉区間[L,R]一様ランダム器生成 /// @param L 下限値 (default 0) /// @param R 上限値 (default 1) /// @return ランダム生成器, RAMDOM_ENGINEを引数としてランダム生成 uniform_int_distribution<> createIntCloseSegRandom(const ll& L = 0, const ll& R = 1) { return uniform_int_distribution<>(L, R); }; /// @brief 実数閉区間[L,R]一様ランダム器生成 /// @param L 下限値 (default 0.0) /// @param R 上限値 (default 1.0) /// @return ランダム生成器, RAMDOM_ENGINEを引数としてランダム生成 uniform_real_distribution<> createRealCloseSegRandom(const double& L = 0.0, const double& R = 1.0) { return uniform_real_distribution<>(L, R); }; /// @brief 正規表現ランダム器生成 /// @param average 平均値 /// @param s 標準偏差 /// @return ランダム生成器, RAMDOM_ENGINEを引数としてランダム生成 normal_distribution<> createNormalRandom(const double& average = 0.0, const double& s = 1.0) { return normal_distribution<>(average, s); }; }; // namespace zz_random using namespace zz_random; namespace zz_mod { class pp { public: ll val; ll mod; void recalc() { val %= mod; if (val < 0) val += mod; }; /// @brief modint (+-*/ != exp ~ inv recalc ) /// @param x value /// @param y mod (default= 998244353) pp(const ll& x = 0, const ll& y = 998244353) { val = x; mod = y; recalc(); }; friend pp operator+(const pp& x, const pp& y) { return pp(x.val + y.val, x.mod); }; friend pp operator+(const pp&& x, const pp& y) { return pp(x.val + y.val, x.mod); }; friend pp operator+(const pp& x, const pp&& y) { return pp(x.val + y.val, x.mod); }; friend pp operator+(const pp&& x, const pp&& y) { return pp(x.val + y.val, x.mod); }; template <typename T> friend pp operator+(const pp& x, const T& y) { return pp(x.val + y, x.mod); }; template <typename T> friend pp operator+(const pp&& x, const T& y) { return pp(x.val + y, x.mod); }; template <typename T> friend pp operator+(const pp& x, const T&& y) { return pp(x.val + y, x.mod); }; template <typename T> friend pp operator+(const pp&& x, const T&& y) { return pp(x.val + y, x.mod); }; friend pp operator-(const pp& x) { return pp(-x.val, x.mod); }; friend pp operator-(const pp&& x) { return pp(-x.val, x.mod); }; friend pp operator-(const pp& x, const pp& y) { return pp(x.val - y.val, x.mod); }; friend pp operator-(const pp&& x, const pp& y) { return pp(x.val - y.val, x.mod); }; friend pp operator-(const pp& x, const pp&& y) { return pp(x.val - y.val, x.mod); }; friend pp operator-(const pp&& x, const pp&& y) { return pp(x.val - y.val, x.mod); }; template <typename T> friend pp operator-(const pp& x, const T& y) { return pp(x.val - y, x.mod); }; template <typename T> friend pp operator-(const pp&& x, const T& y) { return pp(x.val - y, x.mod); }; template <typename T> friend pp operator-(const pp& x, const T&& y) { return pp(x.val - y, x.mod); }; template <typename T> friend pp operator-(const pp&& x, const T&& y) { return pp(x.val - y, x.mod); }; friend pp operator*(const pp& x, const pp& y) { return pp(x.val * y.val, x.mod); }; friend pp operator*(const pp&& x, const pp& y) { return pp(x.val * y.val, x.mod); }; friend pp operator*(const pp& x, const pp&& y) { return pp(x.val * y.val, x.mod); }; friend pp operator*(const pp&& x, const pp&& y) { return pp(x.val * y.val, x.mod); }; template <typename T> friend pp operator*(const pp& x, const T& y) { return pp(x.val * y, x.mod); }; template <typename T> friend pp operator*(const pp&& x, const T& y) { return pp(x.val * y, x.mod); }; template <typename T> friend pp operator*(const pp& x, const T&& y) { return pp(x.val * y, x.mod); }; template <typename T> friend pp operator*(const pp&& x, const T&& y) { return pp(x.val * y, x.mod); }; friend pp operator~(const pp& x) { return x.exp(-1); } friend pp operator~(const pp&& x) { return x.exp(-1); } friend pp operator/(const pp& x, const pp& y) { return x * (~y); }; friend pp operator/(const pp&& x, const pp& y) { return x * (~y); }; friend pp operator/(const pp& x, const pp&& y) { return x * (~y); }; friend pp operator/(const pp&& x, const pp&& y) { return x * (~y); }; template <typename T> friend pp operator/(const pp& x, const T& y) { return x * pp(y, x.mod).inv(); }; template <typename T> friend pp operator/(const pp&& x, const T& y) { return x * pp(y, x.mod).inv(); }; template <typename T> friend pp operator/(const pp& x, const T&& y) { return x * pp(y, x.mod).inv(); }; template <typename T> friend pp operator/(const pp&& x, const T&& y) { return x * pp(y, x.mod).inv(); }; friend pp& operator+=(pp& x, const pp& y) { x.val += y.val; x.recalc(); return x; }; friend pp& operator+=(pp& x, const pp&& y) { x.val += y.val; x.recalc(); return x; }; template <typename T> friend pp& operator+=(pp& x, const T& y) { x.val += y; x.recalc(); return x; }; template <typename T> friend pp& operator+=(pp& x, const T&& y) { x.val += y; x.recalc(); return x; }; friend pp& operator-=(pp& x, const pp& y) { x.val -= y.val; x.recalc(); return x; }; friend pp& operator-=(pp& x, const pp&& y) { x.val -= y.val; x.recalc(); return x; }; template <typename T> friend pp& operator-=(pp& x, const T& y) { x.val -= y; x.recalc(); return x; }; template <typename T> friend pp& operator-=(pp& x, const T&& y) { x.val -= y; x.recalc(); return x; }; friend pp& operator*=(pp& x, const pp& y) { x.val *= y.val; x.recalc(); return x; }; friend pp& operator*=(pp& x, const pp&& y) { x.val *= y.val; x.recalc(); return x; }; template <typename T> friend pp& operator*=(pp& x, const T& y) { x.val *= y; x.recalc(); return x; }; template <typename T> friend pp& operator*=(pp& x, const T&& y) { x.val *= y; x.recalc(); return x; }; friend pp& operator/=(pp& x, const pp& y) { x *= pp(y.val, x.mod).inv(); x.recalc(); return x; }; friend pp& operator/=(pp& x, const pp&& y) { x *= pp(y.val, x.mod).inv(); x.recalc(); return x; }; template <typename T> friend pp& operator/=(pp& x, const T& y) { x *= pp(y, x.mod).inv(); x.recalc(); return x; }; template <typename T> friend pp& operator/=(pp& x, const T&& y) { x *= pp(y, x.mod).inv(); x.recalc(); return x; }; pp exp(ll x) const { if (x == 0) { return pp(1, this->mod); } pp y = *this; if (x > 0) { vl Vec; while (x > 0) { Vec.push_back(x & 1); x >>= 1; } pp ans(1, this->mod); each(ite, Vec) { if (*ite) ans = ans * y; y = y * y; } return ans; } return y.exp(y.mod - 2).exp(-x); }; pp inv() const { return ~(*this); return pp(this->val, this->mod).exp(-1); } }; class factorial { public: const ll size; vector<pp> vec; /// @brief mod! (operator[] comb) /// @param x max! [0,x] (default 1000000) /// @param y mod (default 998244353) factorial(const ll&& x = 1000000, const ll&& y = 998244353) : size(x + 1) { vec = vector<pp>(x + 1, pp(1, y)); cnt(i, 2, x) vec[i] *= (vec[i - 1] * pp(i, y)); }; /// @brief mod factorial /// @return x! mod pp operator[](const ll& x) const { return vec[x]; }; /// @brief mod factorial /// @return x! mod pp operator[](const ll&& x) const { return vec[x]; }; /// @brief mod combination /// @param n /// @param m /// @return nCm pp comb(const ll n, const ll m) const { return (vec[n] / (vec[m] * vec[n - m])); }; }; } // namespace zz_mod using namespace zz_mod; namespace zz_print { namespace elm { template <typename Arg> void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space, const Arg&& arg) { cout << "[" << arg << "| " << Indent << " " << Space << " ]" << endl; }; void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space, const ll& elm) { if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' '); cout << elm << string(Space, ' '); }; void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space, const int& elm) { if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' '); cout << elm << string(Space, ' '); }; void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space, const ull& elm) { if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' '); cout << elm << string(Space, ' '); }; void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space, const unsigned int& elm) { if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' '); cout << elm << string(Space, ' '); }; template <typename Elm1, typename Elm2> void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space, const pair<Elm1, Elm2>& pr) { if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' '); cout << "< " << pr.first << " , " << pr.second << " >" << string(Space, ' '); }; void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space, const pp& pr) { if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' '); cout << "{ " << pr.val << " | " << pr.mod << " }" << string(Space, ' '); }; void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space, const double& elm) { if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' '); cout << elm << string(Space, ' '); }; void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space, const float& elm) { if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' '); cout << elm << string(Space, ' '); }; void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space, const char& elm) { if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' '); cout << elm << string(Space, ' '); }; void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space, const string& elm) { if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' '); cout << elm << string(Space, ' '); }; void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space, const bs8& elm) { if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' '); cout << elm << string(Space, ' '); }; void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space, const bs16& elm) { if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' '); cout << elm << string(Space, ' '); }; void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space, const bs32& elm) { if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' '); cout << elm << string(Space, ' '); }; void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space, const bs64& elm) { if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' '); cout << elm << string(Space, ' '); }; template <typename Elm> void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space, const vector<Elm>& Vec) { if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' '); cout << "[" << string(Space, ' '); if (FlatHier == 1) cout << endl << string(Indent + (1 + Space), ' '); each(ite, Vec) ZOUT(max<ll>(0, FlatHier - 1), Indent + (FlatHier > 0 ? 3 : 0), Space, *ite); if (FlatHier >= 1) cout << endl << string(Indent, ' '); cout << "]" << string(Space, ' '); }; template <typename Elm> void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space, const list<Elm>& Lst) { if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' '); cout << "[" << string(Space, ' '); if (FlatHier == 1) cout << endl << string(Indent + (1 + Space), ' '); each(ite, Lst) ZOUT(max<ll>(0, FlatHier - 1), Indent + (FlatHier > 0 ? 3 : 0), Space, *ite); if (FlatHier >= 1) cout << endl << string(Indent, ' '); cout << "]" << string(Space, ' '); }; template <typename Elm> void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space, const set<Elm>& SET) { if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' '); cout << "[" << string(Space, ' '); if (FlatHier == 1) cout << endl << string(Indent + (1 + Space), ' '); each(ite, SET) ZOUT(max<ll>(0, FlatHier - 1), Indent + (FlatHier > 0 ? 3 : 0), Space, *ite); if (FlatHier >= 1) cout << endl << string(Indent, ' '); cout << "]" << string(Space, ' '); }; template <typename Elm> void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space, const multiset<Elm>& SET) { if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' '); cout << "[" << string(Space, ' '); if (FlatHier == 1) cout << endl << string(Indent + (1 + Space), ' '); each(ite, SET) ZOUT(max<ll>(0, FlatHier - 1), Indent + (FlatHier > 0 ? 3 : 0), Space, *ite); if (FlatHier >= 1) cout << endl << string(Indent, ' '); cout << "]" << string(Space, ' '); }; template <typename Elm> void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space, const unordered_set<Elm>& SET) { if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' '); cout << "[" << string(Space, ' '); if (FlatHier == 1) cout << endl << string(Indent + (1 + Space), ' '); each(ite, SET) ZOUT(max<ll>(0, FlatHier - 1), Indent + (FlatHier > 0 ? 3 : 0), Space, *ite); if (FlatHier >= 1) cout << endl << string(Indent, ' '); cout << "]" << string(Space, ' '); }; template <typename Elm> void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space, const unordered_multiset<Elm>& SET) { if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' '); cout << "[" << string(Space, ' '); if (FlatHier == 1) cout << endl << string(Indent + (1 + Space), ' '); each(ite, SET) ZOUT(max<ll>(0, FlatHier - 1), Indent + (FlatHier > 0 ? 3 : 0), Space, *ite); if (FlatHier >= 1) cout << endl << string(Indent, ' '); cout << "]" << string(Space, ' '); }; template <typename Elm1, typename Elm2> void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space, const map<Elm1, Elm2>& MAP) { if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' '); cout << "[" << string(Space, ' '); if (FlatHier == 1) cout << endl << string(Indent + (1 + Space), ' '); each(ite, MAP) ZOUT(max<ll>(0, FlatHier - 1), Indent + (FlatHier > 0 ? 3 : 0), Space, *ite); if (FlatHier >= 1) cout << endl << string(Indent, ' '); cout << "]" << string(Space, ' '); }; template <typename Elm1, typename Elm2> void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space, const multimap<Elm1, Elm2>& MAP) { if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' '); cout << "[" << string(Space, ' '); if (FlatHier == 1) cout << endl << string(Indent + (1 + Space), ' '); each(ite, MAP) ZOUT(max<ll>(0, FlatHier - 1), Indent + (FlatHier > 0 ? 3 : 0), Space, *ite); if (FlatHier >= 1) cout << endl << string(Indent, ' '); cout << "]" << string(Space, ' '); }; template <typename Elm1, typename Elm2> void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space, const unordered_map<Elm1, Elm2>& MAP) { if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' '); cout << "[" << string(Space, ' '); if (FlatHier == 1) cout << endl << string(Indent + (1 + Space), ' '); each(ite, MAP) ZOUT(max<ll>(0, FlatHier - 1), Indent + (FlatHier > 0 ? 3 : 0), Space, *ite); if (FlatHier >= 1) cout << endl << string(Indent, ' '); cout << "]" << string(Space, ' '); }; template <typename Elm1, typename Elm2> void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space, const unordered_multimap<Elm1, Elm2>& MAP) { if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' '); cout << "[" << string(Space, ' '); if (FlatHier == 1) cout << endl << string(Indent + (1 + Space), ' '); each(ite, MAP) ZOUT(max<ll>(0, FlatHier - 1), Indent + (FlatHier > 0 ? 3 : 0), Space, *ite); if (FlatHier >= 1) cout << endl << string(Indent, ' '); cout << "]" << string(Space, ' '); }; template <typename Elm> void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space, const stack<Elm>& Sta) { stack<Elm> Datas = Sta; if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' '); cout << "(" << string(Space, ' '); if (FlatHier == 1) cout << endl << string(Indent + (1 + Space), ' '); while (!Datas.empty()) { Elm Data = Datas.top(); Datas.pop(); ZOUT(max<ll>(0, FlatHier - 1), Indent + (FlatHier > 0 ? 3 : 0), Space, Data); } if (FlatHier >= 1) cout << endl << string(Indent, ' '); cout << "]" << string(Space, ' '); }; template <typename Elm> void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space, const queue<Elm>& Que) { queue<Elm> Datas = Que; if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' '); cout << "(" << string(Space, ' '); if (FlatHier == 1) cout << endl << string(Indent + (1 + Space), ' '); while (!Datas.empty()) { Elm Data = Datas.front(); Datas.pop(); ZOUT(max<ll>(0, FlatHier - 1), Indent + (FlatHier > 0 ? 3 : 0), Space, Data); } if (FlatHier >= 1) cout << endl << string(Indent, ' '); cout << "]" << string(Space, ' '); }; template <typename Elm> void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space, const priority_queue<Elm>& Que) { priority_queue<Elm> Datas = Que; if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' '); cout << "(" << string(Space, ' '); if (FlatHier == 1) cout << endl << string(Indent + (1 + Space), ' '); while (!Datas.empty()) { Elm Data = Datas.top(); Datas.pop(); ZOUT(max<ll>(0, FlatHier - 1), Indent + (FlatHier > 0 ? 3 : 0), Space, Data); } if (FlatHier >= 1) cout << endl << string(Indent, ' '); cout << "]" << string(Space, ' '); }; template <typename Elm> void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space, const deque<Elm>& Que) { deque<Elm> Datas = Que; if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' '); cout << "(" << string(Space, ' '); if (FlatHier == 1) cout << endl << string(Indent + (1 + Space), ' '); while (!Datas.empty()) { Elm Data = Datas.front(); Datas.pop_front(); ZOUT(max<ll>(0, FlatHier - 1), Indent + (FlatHier > 0 ? 3 : 0), Space, Data); } if (FlatHier >= 1) cout << endl << string(Indent, ' '); cout << "]" << string(Space, ' '); }; } // namespace elm namespace branch { void ZOUT_branch(const ll& FlatHier, const ll& Indent, const ll& Space) {}; template <typename HeadArg, typename... Args> void ZOUT_branch(const ll& FlatHier, const ll& Indent, const ll& Space, HeadArg&& headArg, Args&&... args) { zz_print::elm::ZOUT(FlatHier, Indent, Space, headArg); ZOUT_branch(FlatHier, Indent, Space, std::forward<Args>(args)...); }; template <typename HeadArg, typename... Args> void ZOUT_branch(const ll& FlatHier, const ll& Indent, const ll& Space, HeadArg& headArg, Args&... args) { zz_print::elm::ZOUT(FlatHier, Indent, Space, headArg); ZOUT_branch(FlatHier, Indent, Space, std::forward<Args>(args)...); }; } // namespace branch /// @brief プリント関数 /// @tparam FlatHier 改行による階層表示数 (default 0 改行なし) /// @tparam Space 表示スペース間隔 (default 2) /// @tparam InitIndent インデント間隔 (default 0) /// @tparam ...Args 可変引数型 (指定する必要なし) /// @param ...args 可変引数 template <ll FlatHier = 0, ll Space = 2, ll InitIndent = 0, typename... Args> void zout(Args&&... args) { cout << flush; branch::ZOUT_branch(FlatHier, InitIndent, Space, std::forward<Args>(args)...); cout << endl; }; }; // namespace zz_print using namespace zz_print; ///////////////////////////////////////////////// namespace lazeSegment { template <class S, class F> class lazySeg { private: public: vector<S> A; vector<F> B; vxy Rng; public: const ll N; const ll Size; lazySeg(ll n = 300000) : N([&n] { ll x = 1; while (x < n) x *= 2; return x; }()), Size(2 * N - 1) { A = vector<S>(Size, S::e()); B = vector<F>(Size, F::id()); Rng = vxy(Size); Rng[0] = make_pair(0, N); cnt(i, 1, Size - 1) { if (i % 2 == 1) { Rng[i] = make_pair(Rng[(i - 1) / 2].first, (Rng[(i - 1) / 2].first + Rng[(i - 1) / 2].second) / 2); } else { Rng[i] = make_pair((Rng[(i - 1) / 2].first + Rng[(i - 1) / 2].second) / 2, Rng[(i - 1) / 2].second); } } }; template <typename... Arg> S s(Arg... arg) { return S(arg...); }; template <typename... Arg> F f(Arg... arg) { return F(arg...); }; S get(ll L, ll R, bool dbg = false) { S s = S::e(); if (R <= L) return s; L = max<ll>(0, L); R = min<ll>(R, N); if (N <= L) return s; if (R <= 0) return s; function<void(const ll&)> Func = [this, &L, &R, &dbg, &s, &Func](const ll& at) { if (at < (N - 1)) { B[at * 2 + 1] = B[at] * B[at * 2 + 1]; B[(at + 1) * 2] = B[at] * B[(at + 1) * 2]; } A[at] = B[at] * A[at]; B[at] = F::id(); if ((R <= Rng[at].first) || (Rng[at].second <= L)) { if (dbg) cout << " 1 return" << endl; return; } if ((L <= Rng[at].first) && (Rng[at].second <= R)) { if (dbg) cout << " 2 in" << endl; s = A[at] * s; } else { if (dbg) cout << " 3 cross" << endl; Func((at + 1) * 2); Func(at * 2 + 1); A[at] = A[at * 2 + 1] * A[(at + 1) * 2]; } }; Func(0); return s; }; void set(ll L, ll R, F Act, bool dbg = false) { if (dbg) cout << "set(" << L << " " << R << " " << Act.str() << " " << dbg << ")" << endl; if (R <= L) return; L = max<ll>(0, L); R = min<ll>(R, N); if (N <= L) return; if (R <= 0) return; function<void(const ll&)> Func = [this, &L, &R, &Act, &dbg, &Func](const ll& at) { if ((L <= Rng[at].first) && (Rng[at].second <= R)) { B[at] = Act * B[at]; } if (at < (N - 1)) { B[at * 2 + 1] = B[at] * B[at * 2 + 1]; B[(at + 1) * 2] = B[at] * B[(at + 1) * 2]; } A[at] = B[at] * A[at]; B[at] = F::id(); if (dbg) cout << "@=" << at << " [" << L << "," << R << ") Rng=[" << Rng[at].first << "," << Rng[at].second << ") S=" << A[at].str() << " F=" << B[at].str() << endl; if ((R <= Rng[at].first) || (Rng[at].second <= L)) { if (dbg) cout << " 1 return" << endl; return; } if ((L <= Rng[at].first) && (Rng[at].second <= R)) { if (dbg) cout << " 2 in" << endl; } else { if (dbg) cout << " 3 cross" << endl; Func((at + 1) * 2); Func(at * 2 + 1); A[at] = A[at * 2 + 1] * A[(at + 1) * 2]; } }; Func(0); }; S operator[](const ll& at) { return get(at, at + 1); }; string str(const ll& at, const ll rngShow = true, const ll sShow = true, const ll fShow = true, const ll length = 0) { // S s = get(at, s + 1); string T(1, '_'); if (rngShow) T += "[" + to_string(Rng[at].first) + "," + to_string(Rng[at].second) + ")"; if (sShow) { if (*T.rbegin() != '_') T.push_back(' '); T += A[at].str(); } if (fShow) { if (*T.rbegin() != '_') T.push_back(' '); T += B[at].str(); } T.push_back('_'); if (length > 0) { while (T.size() < length) T.push_back('_'); } return T; } void show(const bool Hier = false, const ll rngShow = true, const ll sShow = true, const ll fShow = true, const ll length = 0) { if (Hier) { rep(i, Size) { cout << str(i, rngShow, sShow, fShow, length) << flush; if (Rng[i].second == N) cout << endl; } } else { rep(i, Size) cout << str(i, rngShow, sShow, fShow, length) << endl; } } }; class S_sum { public: ll e_sum; ll len; S_sum(const ll& x, const ll& y) : e_sum(x), len(y) {}; static S_sum e() { return S_sum(0, 1); }; friend S_sum operator*(const S_sum& l, const S_sum& r) { return S_sum(l.e_sum + r.e_sum, l.len + r.len); } string str() { return "<" + to_string(e_sum) + "," + to_string(len) + ">"; }; friend string str(S_sum x) { return x.str(); } }; class F_sum { public: ll a; ll b; F_sum(const ll& x, const ll& y) : a(x), b(y) {}; static F_sum id() { return F_sum(1, 0); }; friend F_sum operator*(const F_sum& l, const F_sum& r) { return F_sum(l.a * r.a, l.a * r.b + l.b); }; friend S_sum operator*(const F_sum& l, const S_sum& r) { return S_sum(l.a * r.e_sum + l.b * r.len, r.len); }; string str() { return ("<" + to_string(a) + "," + to_string(b) + ">"); }; friend string str(F_sum x) { return x.str(); } }; class S_01 { public: ll len; ll zero; ll one; ll full; ll lft0; ll lft1; ll rgt0; ll rgt1; S_01(const ll& b, const ll& x, const ll& y, const ll& z, const ll& a1, const ll& a2, const ll& a3, const ll& a4) : len(b), zero(x), one(y), full(z), lft0(a1), lft1(a2), rgt0(a3), rgt1(a4) {}; static S_01 e() { return S_01(0, 0, 0, 0, 0, 0, 0, 0); }; friend S_01 operator*(const S_01& l, const S_01& r) { if (l.len == 0) { return r; } if (r.len == 0) { return l; } ll Zero = ((l.full ^ r.full) ? 1 : 0) + l.zero + r.zero + (l.full ? r.lft1 : r.lft0) + (r.full ? l.lft1 : l.lft0); ll One = ((l.full ^ r.full) ? 0 : 1) + l.one + r.one + (l.full ? r.lft0 : r.lft1) + (r.full ? l.lft0 : l.lft1); ll L0 = l.lft0 + (l.full == 0 ? r.lft0 : r.lft1) + (l.full ? 0 : 1); ll L1 = l.lft1 + (l.full == 0 ? r.lft1 : r.lft0) + (l.full ? 1 : 0); ll R0 = r.rgt0 + (r.full == 0 ? l.rgt0 : l.rgt1) + (r.full ? 0 : 1); ll R1 = r.rgt1 + (r.full == 0 ? l.rgt1 : l.rgt0) + (r.full ? 1 : 0); return S_01(l.len + r.len, Zero, One, (l.full ^ r.full), L0, L1, R0, R1); } string str() { return ("<" + to_string(len) + "|" + to_string(zero) + "|" + to_string(one) + " [" + to_string(full) + "] " + to_string(lft0) + " " + to_string(lft1) + " | " + to_string(rgt0) + " " + to_string(rgt1) + ">"); }; friend string str(S_01 x) { return x.str(); } }; class F_01 { public: ll len; ll zero; ll one; ll full; ll lft0; ll lft1; ll rgt0; ll rgt1; F_01(const ll& b, const ll& x, const ll& y, const ll& z, const ll& a1, const ll& a2, const ll& a3, const ll& a4) : len(b), zero(x), one(y), full(z), lft0(a1), lft1(a2), rgt0(a3), rgt1(a4) {}; static F_01 id() { return F_01(0, 0, 0, 0, 0, 0, 0, 0); }; friend F_01 operator*(const F_01& l, const F_01& r) { return F_01(l.len + r.len, l.zero + r.zero, l.one + r.one, l.full + r.full, l.lft0 + r.lft0, l.lft1 + r.lft1, l.rgt0 + r.rgt0, l.rgt1 + r.rgt1); }; friend S_01 operator*(const F_01& l, const S_01& r) { return S_01(l.len + r.len, l.zero + r.zero, l.one + r.one, l.full + r.full, l.lft0 + r.lft0, l.lft1 + r.lft1, l.rgt0 + r.rgt0, l.rgt1 + r.rgt1); }; string str() { return ("<" + to_string(len) + "|" + to_string(zero) + "|" + to_string(one) + " [" + to_string(full) + "] " + to_string(lft0) + " " + to_string(lft1) + " | " + to_string(rgt0) + " " + to_string(rgt1) + ">"); }; friend string str(F_01 x) { return x.str(); } }; class S_sum998244353 { public: ll e_sum; ll len; S_sum998244353(const ll& x, const ll& y) : e_sum(x), len(y) {}; static S_sum998244353 e() { return S_sum998244353(0, 1); }; friend S_sum998244353 operator*(const S_sum998244353& l, const S_sum998244353& r) { return S_sum998244353((l.e_sum + r.e_sum) % 998244353, (l.len + r.len) % 998244353); } string str() { return "<" + to_string(e_sum) + "," + to_string(len) + ">"; }; friend string str(S_sum998244353 x) { return x.str(); } }; class F_sum998244353 { public: ll a; ll b; F_sum998244353(const ll& x, const ll& y) : a(x), b(y) {}; static F_sum998244353 id() { return F_sum998244353(1, 0); }; friend F_sum998244353 operator*(const F_sum998244353& l, const F_sum998244353& r) { return F_sum998244353((l.a * r.a) % 998244353, (((l.a * r.b) % 998244353) + l.b) % 998244353); }; friend S_sum998244353 operator*(const F_sum998244353& l, const S_sum998244353& r) { return S_sum998244353( (((l.a * r.e_sum) % 998244353) + ((l.b * r.len) % 998244353)) % 998244353, r.len); }; string str() { return ("<" + to_string(a) + "," + to_string(b) + ">"); }; friend string str(F_sum998244353 x) { return x.str(); } }; class S_func998244353 { public: ll a; ll b; S_func998244353(const ll& x, const ll& y) : a(x), b(y) {}; static S_func998244353 e() { return S_func998244353(1, 0); }; friend S_func998244353 operator*(const S_func998244353& l, const S_func998244353& r) { return S_func998244353((r.a * l.a) % 998244353, (((r.a * l.b) % 998244353) + r.b) % 998244353); } string str() { return "<" + to_string(a) + "," + to_string(b) + ">"; }; friend string str(S_func998244353 x) { return x.str(); } }; struct F_func998244353 { public: ll a; ll b; ll c; ll d; F_func998244353(const ll& x, const ll& y, const ll& z, const ll& w) : a(x), b(y), c(z), d(w) {}; static F_func998244353 id() { return F_func998244353(1, 0, 1, 0); }; friend F_func998244353 operator*(const F_func998244353& l, const F_func998244353& r) { return F_func998244353( (r.a * l.a) % 998244353, (((r.a * l.b) % 998244353) + r.b) % 998244353, (r.c * l.c) % 998244353, (((r.c * l.d) % 998244353) + r.d) % 998244353); }; friend S_func998244353 operator*(const F_func998244353& l, const S_func998244353& r) { return S_func998244353((((l.a * r.a) % 998244353) + l.b) % 998244353, (((l.c * r.b) % 998244353) + l.d) % 998244353); }; string str() { return ("<" + to_string(a) + "," + to_string(b) + "," + to_string(c) + "," + to_string(d) + ">"); }; friend string str(F_func998244353 x) { return x.str(); } }; class S_bitflp { public: ll zero; ll one; ll zo; ll oz; S_bitflp(const ll& x, const ll& y, const ll& z, const ll& w) : zero(x), one(y), zo(z), oz(w) {}; static S_bitflp e() { return S_bitflp(0, 0, 0, 0); }; friend S_bitflp operator*(const S_bitflp& l, const S_bitflp& r) { return S_bitflp(l.zero + r.zero, l.one + r.one, l.zo + r.zo + l.zero * r.one, l.oz + r.oz + l.one * r.zero); } string str() { return "<" + to_string(zero) + "," + to_string(one) + "," + to_string(zo) + "," + to_string(oz) + ">"; }; friend string str(S_bitflp x) { return x.str(); } }; class F_bitflp { public: ll flp; ll set_a; ll set_b; F_bitflp(const ll& x, const ll& y, const ll& z) : flp(x), set_a(y), set_b(z) {}; static F_bitflp id() { return F_bitflp(0, 1, 0); }; friend F_bitflp operator*(const F_bitflp& l, const F_bitflp& r) { return F_bitflp((l.flp + r.flp) % 2, l.set_a, l.set_b); }; friend S_bitflp operator*(const F_bitflp& l, const S_bitflp& r) { if (l.flp == 0) { if (l.set_a != 1) { return S_bitflp(l.set_b == 0, l.set_b == 1, 0, 0); } return r; } return S_bitflp(r.one, r.zero, r.oz, r.zo); }; string str() { return ("<" + to_string(flp) + ">"); }; friend string str(F_bitflp x) { return x.str(); } }; using sum = lazySeg<lazeSegment::S_sum, lazeSegment::F_sum>; using zz01 = lazySeg<lazeSegment::S_01, lazeSegment::F_01>; using sum998244353 = lazySeg<lazeSegment::S_sum998244353, lazeSegment::F_sum998244353>; using func998244353 = lazySeg<lazeSegment::S_func998244353, lazeSegment::F_func998244353>; using bitflip = lazeSegment::lazySeg<lazeSegment::S_bitflp, lazeSegment::F_bitflp>; }; // namespace lazeSegment int main() { ll N, Q; cin >> N >> Q; vl A(N); rep(i, N) cin >> A[i]; vxy Query(N); rep(i, N) cin >> Query[i].first >> Query[i].second; vector<lazeSegment::zz01> SEGvec(27, lazeSegment::zz01(N)); rep(i, N) { ll X = A[i]; // zout(i, bs32(A[i])); rep(j, 27) { if (X & (1 << j)) { SEGvec[j].set(i, i + 1, SEGvec[j].f(1, 1, 0, 1, 1, 0, 1, 0)); } X >>= 1; } } rep(i, Q) { // zout("@=", i); ll Cnt = 0; rep(j, 27) { // zout("- j=", j); // SEGvec[i].show(true); Cnt += (1LL << j) * SEGvec[j].get(Query[i].first, Query[i].second + 1).one; } cout << Cnt << endl; } return 0; }