結果
| 問題 | No.3569 Xor to Zero |
| コンテスト | |
| ユーザー |
👑  hamamu
|
| 提出日時 | 2026-04-12 18:27:04 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 296 ms / 2,000 ms |
| コード長 | 56,300 bytes |
| 記録 | |
| コンパイル時間 | 3,951 ms |
| コンパイル使用メモリ | 386,780 KB |
| 実行使用メモリ | 34,312 KB |
| 最終ジャッジ日時 | 2026-06-05 20:53:21 |
| 合計ジャッジ時間 | 7,023 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge3_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 25 |
ソースコード
#ifndef MYLOCAL
//# pragma GCC target("avx2")//yukiではNG
# pragma GCC optimize("O3")
# pragma GCC optimize("unroll-loops")
#endif
#if defined(NDEBUG)
#undef NDEBUG
#endif
#include "bits/stdc++.h"
using namespace std;
using ll=long long;
using dd=long double;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll,ll>;
using qll=tuple<ll,ll,ll,ll>;
using namespace chrono;
constexpr ll INF = 1201001001001001001;
struct Fast{ Fast(){ cin.tie(0); ios::sync_with_stdio(false); cout<<fixed<<setprecision(numeric_limits<double>::max_digits10); } } fast;
#define EXPAND( x ) x//VS用おまじない
#define overload3(_1,_2,_3,name,...) name
#define overload4(_1,_2,_3,_4,name,...) name
#define overload5(_1,_2,_3,_4,_5,name,...) name
#define rep1(N) for (ll dmyi = 0; dmyi < (N); dmyi++)
#define rep2(i, N) for (ll i = 0; i < (N); i++)
#define rep3(i, S, E) for (ll i = (S); i <= (E); i++)
#define rep4(i, S, E, t) for (ll i = (S); i <= (E); i+=(t))
#define rep(...) EXPAND(overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__))
#define dep3(i, E, S) for (ll i = (E); i >= (S); i--)
#define dep4(i, E, S, t) for (ll i = (E); i >= (S); i-=(t))
#define dep(...) EXPAND(overload4(__VA_ARGS__, dep4, dep3,_,_)(__VA_ARGS__))
#define ALL1(v) (v).begin(), (v).end()
#define ALL2(v,E) (v).begin(), (v).begin()+((E)+1)
#define ALL3(v,S,E) (v).begin()+(S), (v).begin()+((E)+1)
#define all(...) EXPAND(overload3(__VA_ARGS__, ALL3, ALL2, ALL1)(__VA_ARGS__))
template<class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; }return false; }
template<class T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; }return false; }
template<class T> [[nodiscard]] inline T limithi(T a,T b){ return min(a,b); }
template<class T> [[nodiscard]] inline T limitlo(T a,T b){ return max(a,b); }
template<class T> inline bool chlimithi(T &a,T b){ return chmin(a,b); }
template<class T> inline bool chlimitlo(T &a,T b){ return chmax(a,b); }
template<class T> inline auto maxe(T &&v,ll S,ll E){ return *max_element(all(v,S,E)); }
template<class T> inline auto maxe(T &&v){ return *max_element(all(v)); }
template<class T> inline auto mine(T &&v,ll S,ll E){ return *min_element(all(v,S,E)); }
template<class T> inline auto mine(T &&v){ return *min_element(all(v)); }
template<class T,class U=typename remove_reference<T>::type::value_type>
inline U sum(T &&v,ll S,ll E) {return accumulate(all(v,S,E),U());}
template<class T> inline auto sum(T &&v) {return sum(v,0,v.end()-v.begin()-1);}
template<class T> inline ll sz(T &&v){ return (ll)v.size(); }
//cin
struct cinutil{
template<class T> static void cin1core(T &a){ cin>>a; }
template<class T,class S> static void cin1core(pair<T,S> &a){
cin1core(a.first),cin1core(a.second);
}
template<class... Args> static void cin1core(tuple<Args...> &a){
cinTplRec<tuple<Args...>,sizeof...(Args)-1>()(a);
}
template<class T,size_t N>
static void cin1core(array<T,N> &a){ for (int i=0; i<(int)N; ++i) cin>>a[i]; }
private:
template<class Tpl,int i> struct cinTplRec{
void operator()(Tpl &a){ cinTplRec<Tpl,i-1>()(a); cin1core(get<i>(a)); }
};
template<class Tpl> struct cinTplRec<Tpl,0>{
void operator()(Tpl &a){ cin1core(get<0>(a)); }
};
};
template<class T> T cin1(){ T a; cinutil::cin1core(a); return a; }
template<class... Args> tuple<Args...> cins(){ return cin1<tuple<Args...>>(); }
//cout
template<class T,class S> inline ostream &operator<<(ostream &os,const pair<T,S> &a){ return os << a.first << ' ' << a.second; }
template<class T,class S,class R> inline ostream &operator<<(ostream &os,const tuple<T,S,R> &a){ return os << get<0>(a) << ' ' << get<1>(a) << ' ' << get<2>(a); }
template<class T,class S,class R,class Q> inline ostream &operator<<(ostream &os,const tuple<T,S,R,Q> &a){ return os << get<0>(a) << ' ' << get<1>(a) << ' ' << get<2>(a) << ' ' << get<3>(a); }
template<class T> inline ostream &operator<<(ostream &os,const vector<T> &a){ for (ll i=0; i<(ll)a.size(); i++) os<<(i>0?" ":"")<<a[i]; return os; }
inline struct{
system_clock::time_point st = system_clock::now();
ll operator()()const{return duration_cast<microseconds>(system_clock::now()-st).count()/1000;}
} timeget;
template<long long MOD> struct mll_{
using Int = long long;
using ll = long long;
ll val_=0;
/*---- utility ----*/
mll_ &norm(){ return normR().normS(); }//正規化
mll_ &normR(){ val_%=MOD; return *this; }//剰余正規化のみ
mll_ &normS(){ if (val_<0) val_+=MOD; return *this; }//正負正規化のみ
mll_ &normP(){ if (val_>=MOD) val_-=MOD; return *this; }//加算時正規化
mll_ &invsg(){ val_=-val_; return normS(); }//正負反転
ll modinv(int a){//a^-1 mod MOD
int ypre=0,y=1,apre=MOD;
while (a>1){
int t=apre/a;
apre-=a*t,swap(a,apre);
ypre-=y*t,swap(y,ypre);
}
return y<0 ? y+MOD : y;
}
/*---- I/F ----*/
mll_(){}
mll_(ll v): val_(v){ norm(); }
mll_(ll v,bool b): val_(v){} //正規化無のコンストラクタ
Int val()const{ return (Int)val_; }
bool isnone() const { return val_==-1; } //true:値なし
mll_ &none() { val_=-1; return *this; } //値なしにする
mll_ &inv(){ val_=modinv((int)val_); return *this; }
mll_ &operator+=(mll_ b){ val_+=b.val_; return normP(); }
mll_ &operator-=(mll_ b){ val_-=b.val_; return normS(); }
mll_ &operator*=(mll_ b){ val_*=b.val_; return normR(); }
mll_ &operator/=(mll_ b){ return *this*=b.inv(); }
mll_ &operator+=(ll b){ return *this+=mll_(b); }
mll_ &operator-=(ll b){ return *this-=mll_(b); }
mll_ &operator*=(ll b){ return *this*=mll_(b); }
mll_ &operator/=(ll b){ return *this/=mll_(b); }
mll_ operator-()const{ return mll_(*this).invsg(); }
mll_ operator+(mll_ b)const{ return mll_(*this)+=b; }
mll_ operator-(mll_ b)const{ return mll_(*this)-=b; }
mll_ operator*(mll_ b)const{ return mll_(*this)*=b; }
mll_ operator/(mll_ b)const{ return mll_(*this)/=b; }
mll_ operator+(ll b)const{ return mll_(*this)+=b; }
mll_ operator-(ll b)const{ return mll_(*this)-=b; }
mll_ operator*(ll b)const{ return mll_(*this)*=b; }
mll_ operator/(ll b)const{ return mll_(*this)/=b; }
friend mll_ operator+(ll a,mll_ b){ return b+a; }
friend mll_ operator-(ll a,mll_ b){ return -b+a; }
friend mll_ operator*(ll a,mll_ b){ return b*a; }
friend mll_ operator/(ll a,mll_ b){ return mll_(a)/b; }
bool operator==(mll_ b)const{ return val_==b.val_; }
bool operator!=(mll_ b)const{ return val_!=b.val_; }
bool operator==(ll b)const{ return *this==mll_(b); }
bool operator!=(ll b)const{ return *this!=mll_(b); }
friend bool operator==(ll a,mll_ b){ return mll_(a)==b; }
friend bool operator!=(ll a,mll_ b){ return mll_(a)!=b; }
friend ostream &operator<<(ostream &os,mll_ a){ return os << a.val_; }
friend istream &operator>>(istream &is,mll_ &a){ return is >> a.val_; }
mll_ pow(ll k)const{
mll_ ret(1,false),a(*this);
for (; k>0; k>>=1,a*=a) if (k&1)ret*=a;
return ret;
}
static constexpr int mod() { return MOD; }
//enum{ modll=MOD };
};
template<class T> struct Vector: vector<T>{
using Int = long long;
using vT=vector<T>;
using cvT=const vector<T>;
using cT=const T;
using vT::vT; //親クラスのコンストラクタの隠蔽を回避
using vT::begin,vT::end,vT::insert,vT::erase;
auto it(Int i){ return begin()+i; }
auto it(Int i)const{ return begin()+i; }
Vector(cvT& b):vT(b){}
Vector(vT&& b):vT(move(b)){}
Vector(int n,cT& x):vT(n,x){}// ┬ 型推論のためラッパー
Vector(long long n,cT& x):vT(n,x){}
template<class S> Vector(const Vector<S>& b):vT(b.begin(),b.end()){}
template<class S> Vector(const vector<S>& b):vT(b.begin(),b.end()){}
Vector(Int n,T s,T d){ iota(n,s,d); }
Vector(Int n,function<T(Int)> g):vT(n){ for(Int i=0;i<n;++i) (*this)[i]=g(i); }
Vector &operator+=(cvT &b){ assert(size()==b.size()); for(Int i=0;i<size();++i) (*this)[i]+=b[i]; return *this; }
Vector &operator-=(cvT &b){ assert(size()==b.size()); for(Int i=0;i<size();++i) (*this)[i]-=b[i]; return *this; }
Vector &operator*=(cvT &b){ assert(size()==b.size()); for(Int i=0;i<size();++i) (*this)[i]*=b[i]; return *this; }
Vector &operator/=(cvT &b){ assert(size()==b.size()); for(Int i=0;i<size();++i) (*this)[i]/=b[i]; return *this; }
Vector &operator%=(cvT &b){ assert(size()==b.size()); for(Int i=0;i<size();++i) (*this)[i]%=b[i]; return *this; }
Vector &operator+=(const Vector<T> &b){ return *this+=(cvT&)b; }
Vector &operator-=(const Vector<T> &b){ return *this-=(cvT&)b; }
Vector &operator*=(const Vector<T> &b){ return *this*=(cvT&)b; }
Vector &operator/=(const Vector<T> &b){ return *this/=(cvT&)b; }
Vector &operator%=(const Vector<T> &b){ return *this%=(cvT&)b; }
Vector operator+(cvT &b){ return Vector(*this)+=b; }
Vector operator-(cvT &b){ return Vector(*this)-=b; }
Vector operator*(cvT &b){ return Vector(*this)*=b; }
Vector operator/(cvT &b){ return Vector(*this)/=b; }
Vector operator%(cvT &b){ return Vector(*this)%=b; }
Vector operator+(const Vector<T> &b){ return Vector(*this)+=b; }
Vector operator-(const Vector<T> &b){ return Vector(*this)-=b; }
Vector operator*(const Vector<T> &b){ return Vector(*this)*=b; }
Vector operator/(const Vector<T> &b){ return Vector(*this)/=b; }
Vector operator%(const Vector<T> &b){ return Vector(*this)%=b; }
template<class S> Vector &operator+=(S x){ for(T &e: *this) e+=x; return *this; }
template<class S> Vector &operator-=(S x){ for(T &e: *this) e-=x; return *this; }
template<class S> Vector &operator*=(S x){ for(T &e: *this) e*=x; return *this; }
template<class S> Vector &operator/=(S x){ for(T &e: *this) e/=x; return *this; }
template<class S> Vector &operator%=(S x){ for(T &e: *this) e%=x; return *this; }
template<class S> Vector operator+(S x)const{ return Vector(*this)+=x; }
template<class S> Vector operator-(S x)const{ return Vector(*this)-=x; }
template<class S> Vector operator*(S x)const{ return Vector(*this)*=x; }
template<class S> Vector operator/(S x)const{ return Vector(*this)/=x; }
template<class S> Vector operator%(S x)const{ return Vector(*this)%=x; }
Vector &operator--(int){ return *this-=1; }
Vector &operator++(int){ return *this+=1; }
Vector operator-()const{ return Vector(*this)*=-1; }
template<class S> friend Vector operator-(S x,const Vector &a){ return -a+=x; }
T& at(Int i){ assert(i>=0); if(n()<=i)vT::resize(i+1); return vT::operator[](i); }
Vector slice(Int l,Int r,Int d=1)const{
Vector ret;
for(Int i=l;(d>0&&i<=r)||(d<0&&r<=i);i+=d) ret.push_back((*this)[i]);
return ret;
}
Int size()const{ return (Int)vT::size(); }
Int n()const{ return size(); }
Vector &push_back(cT& x,Int n=1){ for(Int i=0;i<n;++i){ vT::push_back(x); } return *this; }
Vector &pop_back(Int n=1){ for(Int i=0;i<n;++i){ vT::pop_back(); } return *this; }
Vector &push_front(cT& x,Int n=1){ this->insert(0,x,n); return *this; }
Vector &pop_front(Int n=1){ erase(0,n-1); return *this; }
T pull_back(){ T x=move(vT::back()); vT::pop_back(); return x; }
T pull_front(){ T x=move(vT::front()); erase(0); return x; }
Vector &insert(Int i,cT& x,Int n=1){ insert(it(i),n,x); return *this; }
Vector &insert(Int i,cvT& b){ insert(it(i),b.begin(),b.end()); return *this; }
Vector &erase(Int i){ erase(it(i)); return *this; }
Vector &erase(Int l,Int r){ erase(it(l),it(r+1)); return *this; }
Vector &erase(const Vector<Int> &idxs){
for (Int I=0; I<idxs.n(); ++I){
Int l=idxs[I]+1, r = (I<idxs.n()-1) ? idxs[I+1] : this->n();
copy(it(l),it(r),it(l-I-1));//[l,r)を前にI+1個ずらす
}
vT::resize(this->n()-idxs.n());
return *this;
}
Vector &eraseall(cT& x){ return eraseall(0,size()-1,x); }
Vector &eraseall(Int l,Int r,cT& x){ erase(remove(it(l),it(r+1),x),it(r+1)); return *this; }
template<class Pr> Vector &eraseif(Pr pr){ return eraseif(0,size()-1,pr); }
template<class Pr> Vector &eraseif(Int l,Int r,Pr pr){ erase(remove_if(it(l),it(r+1),pr),it(r+1)); return *this; }
Vector &concat(cvT &b,Int n=1){
cvT B = (&b==this) ? *this : vT{};
for(int i=0;i<n;++i) this->insert(size(),(&b==this)?B:b);
return *this;
}
Vector repeat(Int n){ return Vector{}.concat(*this,n); }
Vector &reverse(Int l=0,Int r=-1){ r+=r<0?size():0; std::reverse(it(l),it(r+1)); return *this; }
Vector &rotate(Int m){ return rotate(0,size()-1,m); }
Vector &rotate(Int l,Int r,Int m){ std::rotate(it(l),it(m),it(r+1)); return *this; }
Vector &sort(Int l=0,Int r=-1){ r+=r<0?size():0; std::sort(it(l),it(r+1)); return *this; }
Vector &rsort(Int l=0,Int r=-1){ return sort(l,r).reverse(l,r); }
template<class Pr> Vector &sort(Pr pr){ return sort(0,size()-1,pr); }
template<class Pr> Vector &sort(Int l,Int r,Pr pr){ std::sort(it(l),it(r+1),pr); return *this; }
template<int key> Vector &sortbykey(Int l=0,Int r=-1){
r+=r<0?size():0;
sort(l,r,[](cT &x,cT &y){return get<key>(x)<get<key>(y);});
return *this;
}
Vector &uniq(){ erase(unique(begin(),end()),end()); return *this; }
Vector &sortq(){ return sort().uniq(); }
Vector &fill(cT& x){ return fill(0,size()-1,x); }
Vector &fill(Int l,Int r,cT& x){ std::fill(it(l),it(r+1),x); return *this; }
Vector ©(Int i,cvT &b,Int n=1){//A[i]スタートでbをn回分コピー
for (int t=0; t<n; ++t) for (int j=0; j<(int)b.size(); ++j){
if (i>=size()) return *this;
if (i>=0) (*this)[i]=b[j];
i++;
}
return *this;
}
template<class S=Int> Vector &iota(Int n,T s=0,S d=1){
vT::resize(n);
if(n==0) return *this;
(*this)[0]=s;
for(int i=1;i<n;++i) (*this)[i]=(*this)[i-1]+d;
return *this;
}
Int count(cT& x)const{ return count(0,size()-1,x); }
Int count(Int l,Int r,cT& x)const{ return Int(std::count(it(l),it(r+1),x)); }
template<class Pr> Int countif(Pr pr)const{ return countif(0,size()-1,pr); }
template<class Pr> Int countif(Int l,Int r,Pr pr)const{ return Int(count_if(it(l),it(r+1),pr)); }
Int find(cT& x)const{ return find(0,size()-1,x); }
Int find(Int l,Int r,cT& x)const{ return Int(std::find(it(l),it(r+1),x)-begin()); }
Int rfind(cT& x)const{ return rfind(0,size()-1,x); }
Int rfind(Int l,Int r,cT& x)const{
for (int i=r;i>=l;--i) if ((*this)[i]==x) return i;
return l-1;
}
template<class Pr> Int findif(Pr pr)const{ return findif(0,size()-1,pr); }
template<class Pr> Int findif(Int l,Int r,Pr pr)const{ return Int(find_if(it(l),it(r+1),pr)-begin()); }
Vector<Int> findall(cT& x)const{ return findall(0,size()-1,x); }
Vector<Int> findall(Int l,Int r,cT& x)const{ return findallif(l,r,[&](cT& y){return y==x;}); }
template<class Pr> Vector<Int> findallif(Pr pr)const{ return findallif(0,size()-1,pr); }
template<class Pr> Vector<Int> findallif(Int l,Int r,Pr pr)const{
Vector<Int> ret;
for(Int i=l;i<=r;++i) if(pr((*this)[i])) ret.push_back(i);
return ret;
}
Int flooridx(cT& x)const{ return Int(upper_bound(begin(),end(),x)-begin()-1); }
Int ceilidx(cT& x)const{ return Int(lower_bound(begin(),end(),x)-begin()); }
Int leftnmof(cT& x)const{ return flooridx(x)+1; }
Int rightnmof(cT& x)const{ return size()-ceilidx(x); }
bool contains(cT& x)const{ Int i=flooridx(x); return i>=0 && (*this)[i]==x; }
template<class Pr> Int flooridx(cT& x,Pr pr)const{ return Int(upper_bound(begin(),end(),x,pr)-begin()-1); }
template<class Pr> Int ceilidx(cT& x,Pr pr)const{ return Int(lower_bound(begin(),end(),x,pr)-begin()); }
template<class Pr> Int leftnmof(cT& x,Pr pr)const{ return flooridx(x,pr)+1; }
template<class Pr> Int rightnmof(cT& x,Pr pr)const{ return size()-ceilidx(x,pr); }
template<class Pr> bool contains(cT& x,Pr pr)const{ Int i=flooridx(x,pr); return i>=0 && (*this)[i]==x; }
template<class S> using VV = Vector<Vector<S>>; template<class S> using sVV = vector<vector<S>>;
template<class S> using VVV = Vector<VV<S>>; template<class S> using sVVV = vector<sVV<S>>;
template<class S> using VVVV = Vector<VVV<S>>; template<class S> using sVVVV = vector<sVVV<S>>;
template<class S> using VVVVV = Vector<VVVV<S>>; template<class S> using sVVVVV = vector<sVVVV<S>>;
auto tostd()const{ return tov(*this); }
template <class S> static vector<S> tov(const Vector<S>&v){ return v; }
template <class S> static sVV<S> tov(const VV<S> &v){ sVV<S> ret; for(auto&& e:v) ret.push_back(e); return ret; }
template <class S> static sVVV<S> tov(const VVV<S> &v){ sVVV<S> ret; for(auto&& e:v) ret.push_back(e.tostd()); return ret; }
template <class S> static sVVVV<S> tov(const VVVV<S> &v){ sVVVV<S> ret; for(auto&& e:v) ret.push_back(e.tostd()); return ret; }
template <class S> static sVVVVV<S> tov(const VVVVV<S> &v){ sVVVVV<S> ret; for(auto&& e:v) ret.push_back(e.tostd()); return ret; }
};
#if 0
#define MODLL (1000000007LL)
#else
#define MODLL (998244353LL)
#endif
using mll = mll_<MODLL>;
//using mll = fraction;
namespace SolvingSpace{
template<class T> using vector = Vector<T>;
using vll=vector< ll>; using vmll=vector< mll>; using vdd=vector< dd>;
using vvll=vector< vll>; using vvmll=vector< vmll>; using vvdd=vector< vdd>;
using vvvll=vector< vvll>; using vvvmll=vector< vvmll>; using vvvdd=vector< vvdd>;
using vvvvll=vector<vvvll>; using vvvvmll=vector<vvvmll>; using vvvvdd=vector<vvvdd>;
using vpll=vector< pll>; using vtll=vector< tll>; using vqll=vector< qll>;
using vvpll=vector< vpll>; using vvtll=vector< vtll>; using vvqll=vector< vqll>;
using vss=vector<string>;
template<class T> vector<T> cinv(ll nm){ return vector<T>(nm,[](ll i){ (void)i; return cin1<T>(); }); }
template<class T> vector<vector<T>> cinvv(ll H,ll W){ return vector<vector<T>>(H,[&](ll i){ (void)i; return cinv<T>(W); }); }
/*■■■■■■■■■■■■■■
■■■■■■■■■■■■■■■
■■■■■■■■■■■■■■■
■■■■■■■■■■■■■■■
■■■■■■■■■■■■■■■
■■■■■■■■■■■■■■■
■■■■■■■■■■■■■■■
■■■■■■■■■■■■■■■
■■■■■■■■■■■■■■■
■■■■■■■■■■■■■■■
■■■■■■■■■■■■■■■
■■■■■■■■■■■■■■■*/
//generated by GPT-5.4, modified by hamamu
template<class T,class F,class Ope,class Mapping,class Composition>
struct lazyDynamicSegTree{
using Int = long long;
using ll = long long;
using cT = const T;
using cF = const F;
Ope ope; // データ同士の合成
Mapping rawMapping; // 生の作用: mapping(f,x,l,r) 区間は閉区間 [l,r]
Composition rawComposition; // 生の作用素合成: composition(g,f) は f の後に g
T e; // データの単位元
F id; // 作用素の単位元
ll B; // 添字範囲は [0, 2^B-1] 根/葉の深さがB/0
int rootid=-1;
ll offset,offsetOrg;
ll xr=0; // 全添字に仮想的に xor する値
struct Node{
T x; // 部分木の集約値。自ノードの laz は反映済み
F laz; // 子孫へ未伝播の作用。葉では常に id
array<int,2> cids={-1,-1};
Node(cT &e,cF &id):x(e),laz(id){}
ll nChild()const{ return 2-(cids[0]==-1)-(cids[1]==-1); }
};
vector<Node> pool;
lazyDynamicSegTree(
T,F,Int B,T e,F id,Ope ope,Mapping mapping,Composition composition,Int offset=0
):ope(ope),rawMapping(mapping),rawComposition(composition),
e(e),id(id),B(B),offset(offset),offsetOrg(offset)
{
assert(B>=1);
rootid=newNode();
}
void clear(){
pool.clear();
rootid=newNode();
offset=offsetOrg;
xr=0;
}
ll imin()const{ return offset; }
ll imax()const{ return (1LL<<B)-1+offset; }
// 見かけ上の全添字に xor を掛ける。
// 木の形は変えず、以後の探索順・区間解釈だけを変える。
// offset 付きモードとは併用しない前提。
void xorAllIndex(ll x){
assert(offset==0);
assert(0<=x && x<(1LL<<B));
xr^=x;
}
// 位置 i の葉を削除する。
// 削除後に空部分木になったノードは、親からの参照も切っていく。
void erase(ll i){
if (!IsIn(i)) return;
ll j=toInner(i);
ll s=toStored(j);
Erase(rootid,s,0,(1LL<<B)-1,B);
}
// 位置 i に「葉が存在するか」を返す。
// 値が e かどうかではなく、葉ノードが生成されているかで判定する。
bool contains(ll i)const{
if (!IsIn(i)) return false;
ll j=toInner(i);
ll s=toStored(j);
return Exists(rootid,s,0,(1LL<<B)-1,B);
}
// i 以下で最大の生成済み位置とその値を返す。なければ {imin()-1, e}。
pair<ll,T> floor(ll i)const{
auto [pos,val]=FloorLeaf(normalizeR(i),rootid,0,(1LL<<B)-1,B,id);
return pos==-1 ? pair<ll,T>{imin()-1,e} : pair<ll,T>{pos+offset,val};
}
// i 以上で最小の生成済み位置とその値を返す。なければ {imax()+1, e}。
pair<ll,T> ceil(ll i)const{
auto [pos,val]=CeilLeaf(normalizeL(i),rootid,0,(1LL<<B)-1,B,id);
return pos==(1LL<<B) ? pair<ll,T>{imax()+1,e} : pair<ll,T>{pos+offset,val};
}
// 最小の生成済み位置とその値を返す。空なら {imax()+1, e}。
pair<ll,T> front()const{
auto [pos,val]=FirstLeaf(rootid,0,(1LL<<B)-1,B,id);
return pos==(1LL<<B) ? pair<ll,T>{imax()+1,e} : pair<ll,T>{pos+offset,val};
}
// 最大の生成済み位置とその値を返す。空なら {imin()-1, e}。
pair<ll,T> back()const{
auto [pos,val]=LastLeaf(rootid,0,(1LL<<B)-1,B,id);
return pos==-1 ? pair<ll,T>{imin()-1,e} : pair<ll,T>{pos+offset,val};
}
// 点代入。存在しない点なら新規作成する。
void set(ll i,cT &x){
assert(IsIn(i));
ll j=toInner(i);
ll s=toStored(j);
Set(rootid,s,0,(1LL<<B)-1,B,x);
}
// 点作用。葉が存在しないなら何もしない。
void apply(ll i,cF &f){
apply(i,i,f);
}
// 閉区間 [l,r] の「既存の葉」にだけ作用する。
void apply(ll l,ll r,cF &f){
l=normalizeL(l);
r=normalizeR(r);
if (r<l) return;
ApplyRange(rootid,l,r,0,(1LL<<B)-1,B,f);
}
T operator[](ll i)const{ return prod(i,i); }
T get(ll i)const{ return prod(i,i); }
T get(ll l,ll r)const{ return prod(l,r); }
// 閉区間 [l,r] の集約
T prod(ll l,ll r)const{
l=normalizeL(l);
r=normalizeR(r);
if (r<l) return e;
return Prod(l,r,rootid,0,(1LL<<B)-1,B,id);
}
T allprod()const{
return node(rootid).x;
}
// [l,p] が初めて true になる最左の p。なければ R+1
template<class IsOK> ll minRight(ll l,ll R,IsOK isOK)const{
assert(!isOK(e));
ll nl=normalizeL(l);
ll nR=normalizeR(R);
if (nR<nl) return R+1;
auto [pos,ignore]=SearchR(nl,rootid,0,(1LL<<B)-1,B,e,id,isOK,false);
return nR<pos ? R+1 : pos+offset;
}
// [l,p] が true を保つ最右の p。なければ l-1
template<class IsOK> ll maxRight(ll l,ll R,IsOK isOK)const{
ll pos=minRight(l,R,[&](const T &prd){ return !isOK(prd); });
return max(pos-1,l-1);
}
// [p,r] が初めて true になる最右の p。なければ L-1
template<class IsOK> ll maxLeft(ll L,ll r,IsOK isOK)const{
assert(!isOK(e));
ll nL=normalizeL(L);
ll nr=normalizeR(r);
if (nr<nL) return L-1;
auto [pos,ignore]=SearchL(nr,rootid,0,(1LL<<B)-1,B,e,id,isOK,false);
return pos<nL ? L-1 : pos+offset;
}
// [p,r] が true を保つ最左の p。なければ r+1
template<class IsOK> ll minLeft(ll L,ll r,IsOK isOK)const{
ll pos=maxLeft(L,r,[&](const T &prd){ return !isOK(prd); });
return min(pos+1,r+1);
}
// 生成済み葉だけ列挙する。
// 祖先の lazy は carry に積んで読み、木自体は書き換えない。
// 列挙順は格納座標順ではなく、xor 後の「見かけ上の添字昇順」。
vector<pair<ll,T>> enumerate()const{
vector<pair<ll,T>> ret;
auto dfs=[&](auto dfs,int v,ll sl,ll sr,ll d,F carry)->void{
if (v==-1) return;
const Node &nd=node(v);
if (d==0){
// 葉に着いたら、祖先からの carry を反映した見かけ上の値を返す。
ll i=storedBlockL(sl,d)+offset;
ret.emplace_back(i,mapping(carry,nd.x,i,i));
return;
}
// 子へ降りるときは、自ノードの laz を carry に積む。
F nextCarry=composition(carry,nd.laz);
// low/high は「見かけ上の昇順」で並んでいる。
auto ch=orderedChildren(v,sl,sr,d);
if (ch.low.cid !=-1) dfs(dfs,ch.low.cid,ch.low.sl,ch.low.sr,d-1,nextCarry);
if (ch.high.cid!=-1) dfs(dfs,ch.high.cid,ch.high.sl,ch.high.sr,d-1,nextCarry);
};
dfs(dfs,rootid,0,(1LL<<B)-1,B,id);
return ret;
}
vector<T> tov()const{
vector<T> ret(1LL<<B,e);
for (auto&& [i,x]:enumerate()) ret[i-offset]=x;
return ret;
}
private:
int newNode(){
pool.emplace_back(e,id);
return (int)pool.size()-1;
}
Node &node(int v){ return pool[v]; }
const Node &node(int v)const{ return pool[v]; }
bool IsIn(ll i)const{ return imin()<=i && i<=imax(); }
bool IsId(cF &f)const{ return f==id; }
T mapping(cF &f,cT &x,ll l,ll r)const{
if (IsId(f)) return x;
return rawMapping(f,x,l,r);
}
F composition(cF &g,cF &f)const{ //f の後に g
if (IsId(g)) return f;
if (IsId(f)) return g;
return rawComposition(g,f);
}
ll normalizeL(ll l)const{ return clamp(l-offset,0LL,(1LL<<B)); }
ll normalizeR(ll r)const{ return clamp(r-offset,-1LL,(1LL<<B)-1); }
// 公開添字 -> offset を外した内部添字
ll toInner(ll i)const{ return i-offset; }
// 内部添字 -> 実際に木へ格納する座標
// xorAllIndex は木の組み替えではなく、この対応だけを変える。
ll toStored(ll i)const{ return i^xr; }
// 深さ d のノード [sl,sr] が表す「見かけ上の連続区間」の左端。
// 下位 d bit はブロック内で自由に動くため、xor の影響は上位側だけで決まる。
ll storedBlockL(ll sl,ll d)const{
return ((sl>>d)^(xr>>d))<<d;
}
// 深さ d のノード [sl,sr] が表す「見かけ上の連続区間」の右端。
ll storedBlockR(ll sl,ll d)const{
return storedBlockL(sl,d)+((1LL<<d)-1);
}
// 深さ d において、見かけ上の昇順で low / high どちらの子が先に来るかを返す。
// xr の第 d-1 bit が 0 なら 0 側→1 側、1 なら 1 側→0 側になる。
int childOrderBit(ll d,bool takeHigh)const{
int lowBit=((xr>>(d-1))&1) ? 1 : 0;
return takeHigh ? (lowBit^1) : lowBit;
}
struct ChildInfo{
int cid;
ll sl,sr; // 格納座標上の区間
};
struct OrderedChildren{
ChildInfo low; // 見かけ上の昇順で先に来る子
ChildInfo high; // 見かけ上の昇順で後に来る子
};
// ノード v の 2 子を、xor 後の見かけ上の昇順に並べて返す
OrderedChildren orderedChildren(int v,ll sl,ll sr,ll d)const{
assert(d>=1);
ll sm=(sl+sr)>>1;
int lowBit=childOrderBit(d,false);
int highBit=lowBit^1;
OrderedChildren ret;
ret.low={
node(v).cids[lowBit],
lowBit==0 ? sl : sm+1,
lowBit==0 ? sm : sr
};
ret.high={
node(v).cids[highBit],
highBit==0 ? sl : sm+1,
highBit==0 ? sm : sr
};
return ret;
}
// ノード v 全体へ作用 f を掛ける。sl,sr は格納座標上の区間。
// ここでは subtree 全体が一様に更新されるので、x をまとめて更新し、
// 子孫への遅延は laz に積むだけでよい。
void AllApply(int v,cF &f,ll sl,ll sr,ll d){
Node &nd=node(v);
ll l=storedBlockL(sl,d)+offset;
ll r=storedBlockR(sl,d)+offset;
nd.x = mapping(f,nd.x,l,r);
if (d==0) nd.laz=id;
else nd.laz=composition(f,nd.laz);
}
// v の未伝播 lazy を「既存の子にだけ」配る。
// sparse 実装なので、更新のために新しい子は作らない。
void Push(int v,ll sl,ll sr,ll d){
Node &nd=node(v);
if (d==0 || IsId(nd.laz)) return;
ll sm=(sl+sr)>>1;
if (nd.cids[0]!=-1) AllApply(nd.cids[0],nd.laz,sl,sm,d-1);
if (nd.cids[1]!=-1) AllApply(nd.cids[1],nd.laz,sm+1,sr,d-1);
nd.laz=id;
}
// cids[bit] が未生成なら新規ノードを作る。点代入で新しい葉を生やすときだけ使う。
int EnsureChild(int v,int bit){
int cid=node(v).cids[bit];
if (cid==-1){
cid=newNode();
node(v).cids[bit]=cid;
}
return cid;
}
// 子の x から親の x を再計算する。
// xr!=0 のときも x 自体は格納座標順で持つため、
// xor 利用時は ope が順序入れ替えに耐えることが前提。
void Pull(int v){
Node &nd=node(v);
T lx = nd.cids[0]==-1 ? e : node(nd.cids[0]).x;
T rx = nd.cids[1]==-1 ? e : node(nd.cids[1]).x;
nd.x = ope(lx,rx);
}
// 格納座標 s の葉を x にする。
// 書き込み系なので、途中で必要な lazy は Push してから降りる。
void Set(int v,ll s,ll sl,ll sr,ll d,cT &x){
if (d==0){
Node &nd=node(v);
nd.x=x;
nd.laz=id; // 葉の laz は常に id
return;
}
Push(v,sl,sr,d);
ll sm=(sl+sr)>>1;
if (s<=sm){
int cid=EnsureChild(v,0);
Set(cid,s,sl,sm,d-1,x);
}
else{
int cid=EnsureChild(v,1);
Set(cid,s,sm+1,sr,d-1,x);
}
Pull(v);
}
// 位置 s の葉が存在するかだけを調べる。
// 値が e かどうかではなく、葉ノードがあるかで判定する。
bool Exists(int v,ll s,ll sl,ll sr,ll d)const{
if (v==-1) return false;
if (d==0) return true;
ll sm=(sl+sr)>>1;
if (s<=sm) return Exists(node(v).cids[0],s,sl,sm,d-1);
else return Exists(node(v).cids[1],s,sm+1,sr,d-1);
}
// 位置 s の葉を削除し、空になった部分木は親からも切り離す。
// 戻り値:
// true -> この部分木全体が空になった
// false -> まだこの部分木内に葉が残っている
bool Erase(int v,ll s,ll sl,ll sr,ll d){
if (v==-1) return true;
if (d==0){
// 葉を削除。pool 上のノード自体は残すが、親から切れば外からは到達しない。
Node &nd=node(v);
nd.x=e;
nd.laz=id;
return true;
}
// 子の状態を正しく保つため、潜る前に未伝播 lazy を既存の子へ配る。
Push(v,sl,sr,d);
ll sm=(sl+sr)>>1;
int bit=(s<=sm ? 0 : 1);
int cid=node(v).cids[bit];
// そもそもその子がなければ、消すものはない。
if (cid==-1) return node(v).nChild()==0;
bool childEmpty;
if (bit==0) childEmpty=Erase(cid,s,sl,sm,d-1);
else childEmpty=Erase(cid,s,sm+1,sr,d-1);
// 子部分木が空になったら、親から参照を切る。
if (childEmpty) node(v).cids[bit]=-1;
if (node(v).nChild()==0){
// 自分も空部分木になった。
Node &nd=node(v);
nd.x=e;
nd.laz=id;
return true;
}
// まだ葉が残るなら、子から親の x を再構築する。
Pull(v);
return false;
}
// 部分木 v の中で、見かけ上もっとも左にある生成済み葉を返す。
// 返り値の位置は内部添字系 [0, 2^B-1] で、見つからなければ {2^B, e}。
pair<ll,T> FirstLeaf(int v,ll sl,ll sr,ll d,F carry)const{
if (v==-1) return {1LL<<B,e};
const Node &nd=node(v);
if (d==0){
ll i=storedBlockL(sl,d);
return {i,mapping(carry,nd.x,i+offset,i+offset)};
}
// 自ノードの lazy を carry に積んでから、見かけ上左の子を優先して降りる。
carry=composition(carry,nd.laz);
auto ch=orderedChildren(v,sl,sr,d);
// 見かけ上左の子を優先し、見つからなければ右の子へ進む。
auto ret=FirstLeaf(ch.low.cid,ch.low.sl,ch.low.sr,d-1,carry);
if (ret.first!=(1LL<<B)) return ret;
return FirstLeaf(ch.high.cid,ch.high.sl,ch.high.sr,d-1,carry);
}
// 部分木 v の中で、見かけ上もっとも右にある生成済み葉を返す。
// 返り値の位置は内部添字系 [0, 2^B-1] で、見つからなければ {-1, e}。
pair<ll,T> LastLeaf(int v,ll sl,ll sr,ll d,F carry)const{
if (v==-1) return {-1,e};
const Node &nd=node(v);
if (d==0){
ll i=storedBlockL(sl,d);
return {i,mapping(carry,nd.x,i+offset,i+offset)};
}
// 自ノードの lazy を carry に積んでから、見かけ上右の子を優先して降りる。
carry=composition(carry,nd.laz);
auto ch=orderedChildren(v,sl,sr,d);
// 見かけ上右の子を優先し、見つからなければ左の子へ進む。
auto ret=LastLeaf(ch.high.cid,ch.high.sl,ch.high.sr,d-1,carry);
if (ret.first!=-1) return ret;
return LastLeaf(ch.low.cid,ch.low.sl,ch.low.sr,d-1,carry);
}
// 見かけ上の添字で a 以上にある生成済み葉のうち、最小のものを探す。
// 戻り値:
// {pos,val} 見つかった葉
// {1LL<<B,e} 見つからない
pair<ll,T> CeilLeaf(ll a,int v,ll sl,ll sr,ll d,F carry)const{
if (v==-1) return {1LL<<B,e};
ll l=storedBlockL(sl,d);
ll r=storedBlockR(sl,d);
// この部分木全体が a より左にあるなら候補なし。
if (r<a) return {1LL<<B,e};
// この部分木全体が a 以上なら、その中の最左葉が答え。
if (a<=l) return FirstLeaf(v,sl,sr,d,carry);
const Node &nd=node(v);
if (d==0){
return {l,mapping(carry,nd.x,l+offset,l+offset)};
}
carry=composition(carry,nd.laz);
auto ch=orderedChildren(v,sl,sr,d);
// ceil なので、見かけ上より左にある low 側を先に探す。
auto ret=CeilLeaf(a,ch.low.cid,ch.low.sl,ch.low.sr,d-1,carry);
if (ret.first!=(1LL<<B)) return ret;
return CeilLeaf(a,ch.high.cid,ch.high.sl,ch.high.sr,d-1,carry);
}
// 見かけ上の添字で b 以下にある生成済み葉のうち、最大のものを探す。
// 戻り値:
// {pos,val} 見つかった葉
// {-1,e} 見つからない
pair<ll,T> FloorLeaf(ll b,int v,ll sl,ll sr,ll d,F carry)const{
if (v==-1) return {-1,e};
ll l=storedBlockL(sl,d);
ll r=storedBlockR(sl,d);
// この部分木全体が b より右にあるなら候補なし。
if (b<l) return {-1,e};
// この部分木全体が b 以下なら、その中の最右葉が答え。
if (r<=b) return LastLeaf(v,sl,sr,d,carry);
const Node &nd=node(v);
if (d==0){
// [l,r] が b をまたぐのは葉では起こらないが、統一的にここで返せる。
return {l,mapping(carry,nd.x,l+offset,l+offset)};
}
// 子へ降りるときは carry に自ノード laz を積む。
carry=composition(carry,nd.laz);
auto ch=orderedChildren(v,sl,sr,d);
// floor なので、見かけ上より右にある high 側を先に探す。
auto ret=FloorLeaf(b,ch.high.cid,ch.high.sl,ch.high.sr,d-1,carry);
if (ret.first!=-1) return ret;
// high 側に候補がなければ low 側へ。
return FloorLeaf(b,ch.low.cid,ch.low.sl,ch.low.sr,d-1,carry);
}
void ApplyRange(int v,ll a,ll b,ll sl,ll sr,ll d,cF &f){
if (v==-1) return;
ll l=storedBlockL(sl,d);
ll r=storedBlockR(sl,d);
if (r<a || b<l) return;
if (a<=l && r<=b){
if (v==rootid && node(v).nChild()==0) return;
AllApply(v,f,sl,sr,d);
return;
}
Push(v,sl,sr,d);
ll sm=(sl+sr)>>1;
ApplyRange(node(v).cids[0],a,b,sl,sm,d-1,f);
ApplyRange(node(v).cids[1],a,b,sm+1,sr,d-1,f);
Pull(v);
}
// a,b は見かけ上の添字
// carry は祖先から降ってきた未伝播作用
// 木は書き換えず、carry に積んで読む
T Prod(ll a,ll b,int v,ll sl,ll sr,ll d,F carry)const{
if (v==-1) return e;
ll l=storedBlockL(sl,d);
ll r=storedBlockR(sl,d);
if (r<a || b<l) return e;
const Node &nd=node(v);
if (a<=l && r<=b){
return mapping(carry,nd.x,l+offset,r+offset);
}
carry=composition(carry,nd.laz);
auto ch=orderedChildren(v,sl,sr,d);
T lx=Prod(a,b,ch.low.cid,ch.low.sl,ch.low.sr,d-1,carry);
T rx=Prod(a,b,ch.high.cid,ch.high.sl,ch.high.sr,d-1,carry);
return ope(lx,rx);
}
// isOK が「近くで false、遠くで true」のとき、左から最初の true を探す。
// prePrd は「この部分木より左にある確定済み部分」の集約値。
// carry は祖先からまだ子へ配っていない lazy。
template<class IsOK> pair<ll,T> SearchR(
ll a,int v,ll sl,ll sr,ll d,
T prePrd,F carry,
IsOK isOK,bool rev
)const{
ll l=storedBlockL(sl,d);
ll r=storedBlockR(sl,d);
if (r<a) return {r+1,prePrd};
if (v==-1) return {r+1,prePrd};
const Node &nd=node(v);
// 部分木全体をまとめて採用したときの prefix 値。
T whole=ope(prePrd,mapping(carry,nd.x,l+offset,r+offset));
// この部分木が丸ごと「まだ条件を越えない」なら、葉まで降りずに打ち切る。
if (a<=l && (bool)isOK(whole)==rev) return {r+1,whole};
if (d==0) return {l,prePrd};
carry=composition(carry,nd.laz);
auto ch=orderedChildren(v,sl,sr,d);
ll lowBlockR=storedBlockR(ch.low.sl,d-1);
ll pos; T cur=prePrd;
tie(pos,cur)=SearchR(a,ch.low.cid,ch.low.sl,ch.low.sr,d-1,cur,carry,isOK,rev);
if (pos==lowBlockR+1){
// low 側を全部読んでもまだ足りなければ high 側へ進む。
tie(pos,cur)=SearchR(a,ch.high.cid,ch.high.sl,ch.high.sr,d-1,cur,carry,isOK,rev);
}
return {pos,cur};
}
// isOK が「近くで false、遠くで true」のとき、右から最初の true を探す。
// prePrd は「この部分木より右にある確定済み部分」の集約値。
template<class IsOK> pair<ll,T> SearchL(
ll b,int v,ll sl,ll sr,ll d,
T prePrd,F carry,
IsOK isOK,bool rev
)const{
ll l=storedBlockL(sl,d);
ll r=storedBlockR(sl,d);
if (b<l) return {l-1,prePrd};
if (v==-1) return {l-1,prePrd};
const Node &nd=node(v);
// 部分木全体をまとめて採用したときの suffix 値。
T whole=ope(mapping(carry,nd.x,l+offset,r+offset),prePrd);
if (r<=b && (bool)isOK(whole)==rev) return {l-1,whole};
if (d==0) return {l,prePrd};
carry=composition(carry,nd.laz);
auto ch=orderedChildren(v,sl,sr,d);
ll highBlockL=storedBlockL(ch.high.sl,d-1);
ll pos; T cur=prePrd;
tie(pos,cur)=SearchL(b,ch.high.cid,ch.high.sl,ch.high.sr,d-1,cur,carry,isOK,rev);
if (pos==highBlockL-1){
// high 側を全部読んでもまだ足りなければ low 側へ進む。
tie(pos,cur)=SearchL(b,ch.low.cid,ch.low.sl,ch.low.sr,d-1,cur,carry,isOK,rev);
}
return {pos,cur};
}
};
/*
- ノード未生成の部分は「データがない」とする(単位元のデータがあるとはしない)
- よって区間への操作時、ノード未生成の部分には何もしない
- offset、Bは広めにとる(広くしてもほとんど処理時間変わらない)
- xorAllIndex使用時は、opeは可換、mappingは座標非依存が前提
- offset と xorAllIndex の併用は不可
- ---- 定義 ---- (区間加算、区間max取得の例)
. ┌添字のビット数
. 作用素型F┐ │ ┌データの単位元(実際の単位元でないとだめ)
. データ型T┐ ↓ ↓ ↓ ┌作用素の単位元(使わない値ならOK)
lazyDynamicSegTree dsg(ll(),ll(),B,-INF,0,
[](const T &x,const T &y){ return max(x,y); }, //op T(T,T)
[](const F &f,const T &x,ll l,ll r){ return x+f; }, //[l,r]への作用 T(F,T,l,r)
[](const F &g,const F &f){ return g+f; } //作用素合成 F(F,F) fの後gを作用
);
lazyDynamicSegTree dsg(T(),F(),B,e,id,ope,mapping,composition,offset);
. 添字のoffset a[i-offset]に対応する ┘
- ---- 操作 ----
dsg.clear(); //空にする
ll i=dsg.imin(); //iの下限
ll i=dsg.imax(); //iの上限
dsg.set(i,x); //a[i]←x 位置iにx代入、位置iがなければ新規作成
dsg.erase(i); //位置iを削除
bool b=dsg.contains(i); //位置iが存在すればtrue
dsg.apply(i,f); //a[i]←f(a[i]) 位置iがなければ何もしない
dsg.apply(l,r,f); //区間[l,r]内の既存データにだけfを作用
ll x=dsg[i]; //a[i] 位置iの値。未生成なら e
ll x=dsg.get(i); //a[i] 位置iの値。未生成なら e
ll x=dsg.get(l,r); //[l,r]の値
ll x=dsg.prod(l,r); //[l,r]の値
ll x=dsg.allprod(); //全区間の値
auto[j,va]=dsg.floor(i); //i以下の最大の生成済み位置と値。なければ {imin()-1,e}
auto[j,va]=dsg.ceil(i); //i以上の最小の生成済み位置と値。なければ {imax()+1,e}
auto[j,va]=dsg.front(); //最小の生成済み位置と値。空なら {imax()+1,e}
auto[j,va]=dsg.back(); //最大の生成済み位置と値。空なら {imin()-1,e}
dsg.xorAllIndex(x); //見かけ上の全添字に xor を掛ける
vpll ixs=dsg.enumerate(); //生成済み葉を位置昇順に列挙 {<位置i,値x>,…}
vll v=dsg.tov(); //長さ 2^B の配列化
- ---- 二分探索 ----
[L,R]内でラムダ式isOKが○(true)になる位置 L,Rは範囲外や逆転も可
未生成の点は e として扱われる
- 使用例
ll i=dsg.minRight(L,R,[&](ll x){ return x>=th; }); // L×→×→×ⓡ○R
ll i=dsg.maxRight(L,R,[&](ll x){ return x<=th; }); // L○→○→ⓡ××R
ll i=dsg.maxLeft (L,R,[&](ll x){ return x>=th; }); //L○ⓛ×←×←×R
ll i=dsg.minLeft (L,R,[&](ll x){ return x<=th; }); //L××ⓛ←○←○R
- 要件・挙動
minRight: isOK([L,r])=○(L≦r≦R)となる最左のr、ないときR+1 要件:isOK(e)=×
maxRight: isOK([L,r])=○(L≦r≦R)となる最右のr、ないときL-1 要件:isOK(e)=○
maxLeft: isOK([l,R])=○(L≦l≦R)となる最右のl、ないときL-1 要件:isOK(e)=×
minLeft: isOK([l,R])=○(L≦l≦R)となる最左のl、ないときR+1 要件:isOK(e)=○
*/
//pair用テンプレート
template<class T,class S> inline pair<T,S>& operator+=(pair<T,S> &a,const pair<T,S> &b){ a.first+=b.first; a.second+=b.second; return a; }
template<class T,class S> inline pair<T,S>& operator-=(pair<T,S> &a,const pair<T,S> &b){ a.first-=b.first; a.second-=b.second; return a; }
template<class T,class S> inline pair<T,S>& operator*=(pair<T,S> &a,const pair<T,S> &b){ a.first*=b.first; a.second*=b.second; return a; }
template<class T,class S> inline pair<T,S>& operator/=(pair<T,S> &a,const pair<T,S> &b){ a.first/=b.first; a.second/=b.second; return a; }
template<class T,class S> inline pair<T,S>& operator%=(pair<T,S> &a,const pair<T,S> &b){ a.first%=b.first; a.second%=b.second; return a; }
template<class T,class S,class R> inline pair<T,S>& operator+=(pair<T,S> &a,R b){ a.first+=b; a.second+=b; return a; }
template<class T,class S,class R> inline pair<T,S>& operator-=(pair<T,S> &a,R b){ a.first-=b; a.second-=b; return a; }
template<class T,class S,class R> inline pair<T,S>& operator*=(pair<T,S> &a,R b){ a.first*=b; a.second*=b; return a; }
template<class T,class S,class R> inline pair<T,S>& operator/=(pair<T,S> &a,R b){ a.first/=b; a.second/=b; return a; }
template<class T,class S,class R> inline pair<T,S>& operator%=(pair<T,S> &a,R b){ a.first%=b; a.second%=b; return a; }
template<class T,class S,class R> inline pair<T,S> operator+(const pair<T,S> &a,R b){ pair<T,S> c=a; return c+=b; }
template<class T,class S,class R> inline pair<T,S> operator-(const pair<T,S> &a,R b){ pair<T,S> c=a; return c-=b; }
template<class T,class S,class R> inline pair<T,S> operator*(const pair<T,S> &a,R b){ pair<T,S> c=a; return c*=b; }
template<class T,class S,class R> inline pair<T,S> operator/(const pair<T,S> &a,R b){ pair<T,S> c=a; return c/=b; }
template<class T,class S,class R> inline pair<T,S> operator%(const pair<T,S> &a,R b){ pair<T,S> c=a; return c%=b; }
template<class T,class S,class R> inline pair<T,S> operator-(R b,const pair<T,S> &a){ pair<T,S> c=-a; return c+=b; }
template<class T,class S> inline pair<T,S> operator-(const pair<T,S> &a,const pair<T,S> &b){ pair<T,S> c=a; return c-=b; }
template<class T,class S> inline pair<T,S> operator-(const pair<T,S> &a){ pair<T,S> c=a; return c*=(-1); }
auto solve(
ll N,vll A
){
A.push_back(0);
/*
現在位置iを左から右へ動かす
keyは、左端をi+1としてあり得る右端それぞれの総xor値
valueは、<右端個数c, xor=0にならずたまっている左方の個数s>
(1)Ai>総xor値 のとき
1手で0にできる。(1)の範囲のsの総和×1→ans、(1)の範囲のsに0代入
//(2)Ai=総xor値 のとき
//0手で0にできる。ansそのまま、(2)の範囲のsに0代入
(3)Ai<総xor値 のとき
Ai≧2＆A_{i+1}以降続く1の連続数が偶数個のとき→2手
その他→1手
(3)の範囲のsの総和×手数→ans、(3)の範囲のsへの代入なし
i→i+1にする準備
空区間を削除：key=0の右端個数cを1減らす
左端を追加：全keyのsにcを足す
総xor値から左端1つ削る：全keyにAi+1をxorする
*/
vll ren1(N+1);//右方への1の連続数
dep(i,N-1,0){
if (A[i]==1)
ren1[i]=ren1[i+1]+1;
}
using T=pll;//<個数,和>
using F=pll;//<y=0/1,z> y=0:z代入,1:z加算
#if defined(_MSC_VER)
ll B=4;
#else
ll B=20;
#endif
// ┌添字のビット数
// 作用素型F┐ │ ┌データの単位元(実際の単位元でないとだめ)
// データ型T┐ ↓ ↓ ↓ ┌作用素の単位元(使わない値ならOK)
lazyDynamicSegTree sgt(T(), F(),B,pll(0,0),pll(2,0),
[](const T &x,const T &y){ return x+y; }, //op T(T,T)
[](const F &f,const T &x,ll l,ll r)->T
{
auto[c,s]=x;
auto[y,z]=f;
if (y==0)
return {c,c*z};
else
return {c,s+c*z};
}, //[l,r]への作用 T(F,T,l,r)
[](const F &g,const F &f)->F
{
auto [y , z]=f;
auto [yy,zz]=g;
if (yy==0) //後が代入
return {yy,zz};
else
return {y,z+zz};
} //作用素合成 F(F,F) fの後gを作用
);
{//左端1の全区間の各総xor値をsgtにセット
map<ll,ll> mp;
ll smx=0;
mp[smx]++;
rep(i,1,N-1){
smx^=A[i];
mp[smx]++;
}
for (auto&&[key,ct]:mp){
sgt.set(key,pll(ct,ct));
}
}
ll ans=0;
rep(i,0,N-1){
//for (auto&& e: sgt.tov()) cout << e << '\n';
ll ai=A[i];
//(1)Ai>総xor値 のとき
{
auto [c,sm]= sgt.get(0,ai-1);
ans+=sm*1;
sgt.apply(0,ai-1,pll(0,0));
//for (auto&& e: sgt.tov()) cout << e << '\n';
}
//(3)Ai<=総xor値 のとき
{
ll te= (ai>=2 and ren1[i+1]%2==0) ? 2 : 1;
auto [c,sm]= sgt.get(ai,INF);
ans+=sm*te;
}
//i→i+1にする準備
{//空区間を削除：key=0の右端個数cを1減らす
auto [c,s]=sgt[0];
assert(c>0);
if (c>1)
sgt.set(0,pll(c-1,s));
else
sgt.erase(0);
}
//左端を追加：全keyのsにcを足す
sgt.apply(0,INF,pll(1,1));
//総xor値から左端1つ削る：全keyにAi+1をxorする
sgt.xorAllIndex(A[i+1]);
}
//cout << ans << '\n';
return ans;
}
auto solve2(
ll N,vll A
){
vll Ax=A;
Ax.push_front(0);
rep(i,1,N)
Ax[i]^=Ax[i-1];
auto cmx=[&](ll l,ll r){
return Ax[r+1]^Ax[l];
};
auto ren1=[&](ll i,ll r){
ll ret=0;
rep(j,i,r-1){
if (A[j]==1)
ret++;
else break;
}
return ret;
};
ll ans=0;
rep(l,0,N-1) rep(r,l,N-1){
ll sm=0;
rep(i,l,r){
ll ai=A[i];
ll cx=cmx(i+1,r);
if (ai>cx){
sm++; break;
}
if (ai==1) sm++;
else if (ren1(i+1,r)%2==1) sm++;
else sm+=2;
}
ans+=sm;
}
return ans;
}
//#define RANDOM_TEST
#if defined(_MSC_VER)
#include <conio.h>
#endif
void solvecomp(
ll N,vll A
){
auto coutans=[](auto ans){
cout << ans << '\n';
};
auto ans=solve(
N,A
);
coutans(ans);
#if defined(RANDOM_TEST)
cout << "- - - - -\n";
auto an2=solve2(
N,A
);
coutans(an2);
cout << "================\n";
if (ans!=an2){
cout << "============ input =============\n";
cout << N << '\n';
cout << A << '\n';
cout << "============ input end =========\n\n================\n";
#if defined(_MSC_VER)
(void)_getch();
#endif
}
#endif
}
void cin2solve(){
auto N=cin1<ll>();
auto A=cinv<ll>(N);
solvecomp(
N,A
);
}
namespace RndSpace{
using Int = long long;
using dd = long double;
struct rndutil{
mt19937 mt;
rndutil(Int seed=0):mt(GetSeed(seed)){}
Int val(Int a,Int b){ return mt()%(b-a+1)+a; }//[a,b]の乱数
dd dval(){ return (dd)mt()/(1ll<<32); }//[0,1)の浮動小数点乱数
vector<Int> ary(Int n,Int a,Int b){//長さnの配列、要素[a,b]内、重複可
vector<Int> v(n);
for (Int i=0; i<n; ++i) v[i]=this->val(a,b);
return v;
}
vector<dd> dary(Int n){//長さnの[0,1)の浮動小数点乱数
vector<dd> v(n);
for (Int i=0; i<n; ++i) v[i]=this->dval();
return v;
}
string str(Int n,char cs,char ce){//長さnのstring、使用文字cs~ce、重複可
string str(n,cs);
for (Int i=0; i<n; ++i) str[i]+=(char)this->val(0,ce-cs);
return str;
}
vector<Int> sample(Int n,Int a,Int b){//長さnの配列、要素[a,b]内、重複無
Int len=b-a+1;
assert(n<=len);
vector<Int> v(len);
iota(v.begin(),v.end(),a);
for (Int i=0; i<n; ++i) swap(v[i],v[this->val(i,len-1)]);
v.resize(n);
return v;
}
template <class T> auto sample(const T &v){//1つ選択
return v[val(0,(Int)v.size()-1)];
}
template <class T> auto samplepop(T &v){//1つ取り出し(末尾swapし削除)
Int i=val(0,(Int)v.size()-1);
auto ret=v[i];
v[i]=v.back();
v.pop_back();
return ret;
}
Int weightedSampleCore(const vector<Int> &cm){//重み付き乱択 累積和版
Int randval=val(1,cm.back());
return Int(lower_bound(cm.begin(),cm.end(),randval)-cm.begin());
}
Int weightedSample(const vector<Int> &pr){//重み付き乱択
vector<Int> cm=pr;
for (Int i=1; i<(Int)cm.size(); ++i) cm[i]+=cm[i-1];
return weightedSampleCore(cm);
}
template <class T> void shuffle(T &v){//配列や文字列をシャッフル
Int n=(Int)v.size();
for (Int i=0; i<n; ++i) swap(v[i],v[this->val(i,n-1)]);
}
pair<Int,Int> range(Int a,Int b,Int m=1){ //[a,b]内閉区間長さm以上
while (true){
Int l=this->val(a,b+1),r=this->val(a,b+1);
if (r-l<m)continue;
return {l,r-1};
}
}
#if 1 //グラフ使用時ON
vector<pair<Int,Int>> tree(Int N,bool zeroIndexed=false);
vector<pair<Int,Int>> graph(
Int N,Int M,bool isConnected,bool isDirected,bool zeroIndexed=false);
vector<tuple<Int,Int,Int>> wgraph(Int N,Int M,Int cmin,Int cmax,
bool isConnected,bool isDirected,bool zeroIndexed=false);
template<class EDGES>
EDGES GraphCore(Int N,Int M,bool isConnected,bool isDirected,bool zeroIndexed);
#endif
private:
unsigned int GetSeed(Int seed){
if (seed>=0) return (unsigned int)seed;
return (unsigned int)chrono::system_clock::now().time_since_epoch().count();
}
};
}//namespace
using RndSpace::rndutil;
/*
rndutil ru;
rndutil ru(-1); //seedランダム(時刻使用)
- -------- 整数x -------- 区間[a,b]
ll x=ru.val(a,b);
- -------- 浮動小数点数x -------- [0,1)
dd x=ru.dval();
- -------- 整数ベクトルv -------- 長さn,要素の区間[a,b] 配列重複有
vll v=ru.ary(n,a,b);
- -------- 整数ベクトルv -------- 長さn,要素の区間[a,b] 配列重複無
vll v=ru.sample(n,a,b);
- -------- 浮動小数点ベクトルv -------- 長さn,[0,1)
vdd v=ru.dary(n);
- -------- 文字列s -------- 長さn,使用文字'a'~'z'
string s=ru.str(n,'a','z');
- -------- 乱択 -------- vll,string等から1つ選択
ll x=ru.sample(v);
char c=ru.sample(s);
- -------- 乱択削除 -------- vll,string等から1つ取り出し(末尾swapし削除)
ll x=ru.samplepop(v);
- -------- 重み付き乱択 -------- i∈{0,1,…,n-1}を重みwiで選択
ll i=ru.weightedSample(w);
ll i=ru.weightedSampleCore(cm);
. ↑wの累積和を与えることで高速に
- -------- シャッフル -------- vll,string等
ru.shuffle(a);
- -------- 範囲[l,r] -------- [l,r]⊆[a,b] 区間長1以上
auto[l,r]=ru.range(a,b);
auto[l,r]=ru.range(a,b,m);
. ↑区間長m以上
*/
void generand(){
rndutil ru;
rep(q,0,INF){
ll N=ru.val(1,4);
vll A=ru.ary(N,1,3);
//vpll vu=ru.tree(n);
solvecomp(
N,A
);
}
}
}//SolvingSpace
//////////////////////////////////////////
int main(){
#if defined(RANDOM_TEST)
SolvingSpace::cin2solve();
SolvingSpace::generand();
#else
#if 1
//SolvingSpace::labo();'
SolvingSpace::cin2solve();
#else
ll t; cin >> t;
rep(i,0,t-1){
SolvingSpace::cin2solve();
}
#endif
#endif
cerr << timeget() <<"ms"<< '\n';
return 0;
}