結果
問題 |
No.3208 Parse AND OR Affection
|
ユーザー |
![]() |
提出日時 | 2025-07-18 23:18:42 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 104 ms / 5,000 ms |
コード長 | 11,075 bytes |
コンパイル時間 | 3,461 ms |
コンパイル使用メモリ | 296,104 KB |
実行使用メモリ | 69,264 KB |
最終ジャッジ日時 | 2025-07-18 23:18:49 |
合計ジャッジ時間 | 6,381 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 20 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll=long long; using ull=unsigned long long; using P=pair<ll,ll>; template<typename T>using minque=priority_queue<T,vector<T>,greater<T>>; template<typename T>bool chmax(T &a,const T &b){return (a<b?(a=b,true):false);} template<typename T>bool chmin(T &a,const T &b){return (a>b?(a=b,true):false);} template<typename T1,typename T2>istream &operator>>(istream &is,pair<T1,T2>&p){is>>p.first>>p.second;return is;} template<typename T1,typename T2,typename T3>istream &operator>>(istream &is,tuple<T1,T2,T3>&a){is>>std::get<0>(a)>>std::get<1>(a)>>std::get<2>(a);return is;} template<typename T,size_t n>istream &operator>>(istream &is,array<T,n>&a){for(auto&i:a)is>>i;return is;} template<typename T>istream &operator>>(istream &is,vector<T> &a){for(auto &i:a)is>>i;return is;} template<typename T1,typename T2>void operator++(pair<T1,T2>&a,int n){a.first++,a.second++;} template<typename T1,typename T2>void operator--(pair<T1,T2>&a,int n){a.first--,a.second--;} template<typename T>void operator++(vector<T>&a,int n){for(auto &i:a)i++;} template<typename T>void operator--(vector<T>&a,int n){for(auto &i:a)i--;} #define overload3(_1,_2,_3,name,...) name #define rep1(i,n) for(int i=0;i<(int)(n);i++) #define rep2(i,l,r) for(int i=(int)(l);i<(int)(r);i++) #define rep(...) overload3(__VA_ARGS__,rep2,rep1)(__VA_ARGS__) #define reps(i,l,r) rep2(i,l,r) #define all(x) x.begin(),x.end() #define pcnt(x) __builtin_popcountll(x) #define fin(x) return cout<<(x)<<'\n',static_cast<void>(0) #define yn(x) cout<<((x)?"Yes\n":"No\n") #define uniq(x) sort(all(x)),x.erase(unique(all(x)),x.end()) template<typename T> inline int fkey(vector<T>&z,T key){return lower_bound(z.begin(),z.end(),key)-z.begin();} ll myceil(ll a,ll b){return (a+b-1)/b;} template<typename T,size_t n,size_t id=0> auto vec(const int (&d)[n],const T &init=T()){ if constexpr (id<n)return vector(d[id],vec<T,n,id+1>(d,init)); else return init; } #ifdef LOCAL #include<debug.h> #define SWITCH(a,b) (a) #else #define debug(...) static_cast<void>(0) #define debugg(...) static_cast<void>(0) #define SWITCH(a,b) (b) template<typename T1,typename T2>ostream &operator<<(ostream &os,const pair<T1,T2>&p){os<<p.first<<' '<<p.second;return os;} #endif struct Timer{ clock_t start; Timer(){ start=clock(); ios::sync_with_stdio(false); cin.tie(nullptr); cout<<fixed<<setprecision(16); } inline double now(){return (double)(clock()-start)/1000;} #ifdef LOCAL ~Timer(){ cerr<<"time:"; cerr<<now(); cerr<<"ms\n"; } #endif }timer; void SOLVE(); int main(){ int testcase=1; //cin>>testcase; for(int i=0;i<testcase;i++){ SOLVE(); } } #include<type_traits> #include<concepts> template<typename T> constexpr std::enable_if_t<std::numeric_limits<T>::digits<=32,int>msb(T n){return n==0?-1:31-__builtin_clz(n);} template<typename T> constexpr std::enable_if_t<(std::numeric_limits<T>::digits>32),int>msb(T n){return n==0?-1:63-__builtin_clzll(n);} template<typename T> constexpr std::enable_if_t<std::numeric_limits<T>::digits<=32,int>lsb(T n){return n==0?-1:__builtin_ctz(n);} template<typename T> constexpr std::enable_if_t<(std::numeric_limits<T>::digits>32),int>lsb(T n){return n==0?-1:__builtin_ctzll(n);} template<typename T> constexpr std::enable_if_t<std::is_integral_v<T>,T>floor_pow2(T n){return n==0?0:T(1)<<msb(n);} template<typename T> constexpr std::enable_if_t<std::is_integral_v<T>,T>ceil_pow2(T n){return n<=1?1:T(1)<<(msb(n-1)+1);} template<std::integral T> constexpr T safe_div(T a,T b){return a/b-(a%b&&(a^b)<0);} template<std::integral T> constexpr T safe_ceil(T a,T b){return a/b+(a%b&&(a^b)>0);} template<typename M,int L=5> struct SparseTable{ using S=typename M::S; private: std::vector<S>dat,prefix,suffix; std::vector<std::vector<S>>sp; public: SparseTable(){} SparseTable(std::vector<S>a):dat(a){ int n=a.size(); n=(n+(1<<L)-1)&~((1<<L)-1); a.resize(n,M::e()); prefix=suffix=a; std::vector<S>d2(n>>L,M::e()); for(int i=0;i<d2.size();i++){ for(int j=0;j<(1<<L);j++)d2[i]=M::op(d2[i],a[(i<<L)+j]); } for(int i=0;i<(n>>L);i++){ for(int j=1;j<(1<<L);j++)prefix[(i<<L)+j]=M::op(prefix[(i<<L)+j-1],prefix[(i<<L)+j]); } for(int i=(n>>L)-1;i>=0;i--){ for(int j=(1<<L)-1;j>=1;j--)suffix[(i<<L)+j-1]=M::op(suffix[(i<<L)+j-1],suffix[(i<<L)+j]); } int d=(d2.size()==1?1:32-__builtin_clz(d2.size()-1)); sp.resize(d,d2); for(int i=1;i<d;i++){ int w=1<<i; for(int j=w;j<=d2.size();j+=w*2){ for(int k=j-2;k>=j-w;k--)sp[i][k]=M::op(d2[k],sp[i][k+1]); int r=std::min<int>(d2.size(),j+w); for(int k=j+1;k<r;k++)sp[i][k]=M::op(sp[i][k-1],d2[k]); } } } S prod(int l,int r)const{ if(l==r)return M::e(); r--; int lid=l>>L,rid=r>>L; if(lid==rid){ S ret=M::e(); for(int i=l;i<=r;i++)ret=M::op(ret,dat[i]); return ret; } else{ lid++; rid--; S mid=M::e(); if(lid==rid)mid=sp[0][lid]; else if(lid<rid){ int s=msb(lid^rid); mid=M::op(sp[s][lid],sp[s][rid]); } return M::op(suffix[l],M::op(mid,prefix[r])); } } }; template<typename T,int N,int M=N> struct ConstantMatrix{ private: std::array<std::array<T,M>,N>dat; public: ConstantMatrix(){ dat.fill([](){std::array<T,M>res;res.fill(T());return res;}()); } static ConstantMatrix E(){ static_assert(N==M); ConstantMatrix res; for(int i=0;i<N;i++)res[i][i]=T(1); return res; } inline ConstantMatrix &operator+=(const ConstantMatrix&rhs){ for(int i=0;i<N;i++)for(int j=0;j<M;j++)(*this)[i][j]+=rhs[i][j]; return *this; } inline ConstantMatrix &operator-=(const ConstantMatrix&rhs){ for(int i=0;i<N;i++)for(int j=0;j<M;j++)(*this)[i][j]-=rhs[i][j]; return *this; } inline ConstantMatrix &operator*=(const ConstantMatrix&rhs){ static_assert(N==M); ConstantMatrix res; for(int i=0;i<N;i++)for(int j=0;j<M;j++)for(int k=0;k<M;k++)res[i][k]+=(*this)[i][j]*rhs[j][k]; (*this)=std::move(res); return *this; } friend ConstantMatrix operator+(const ConstantMatrix&lhs,const ConstantMatrix&rhs){return ConstantMatrix(lhs)+=rhs;} friend ConstantMatrix operator-(const ConstantMatrix&lhs,const ConstantMatrix&rhs){return ConstantMatrix(lhs)-=rhs;} template<int K>friend ConstantMatrix<T,N,K> operator*(const ConstantMatrix&lhs,const ConstantMatrix<T,M,K>&rhs){ ConstantMatrix<T,N,K>res; for(int i=0;i<N;i++)for(int j=0;j<M;j++)for(int k=0;k<K;k++)res[i][k]+=lhs[i][j]*rhs[j][k]; return res; } std::array<T,M> &operator[](int i){return dat[i];} const std::array<T,M> &operator[](int i)const{return dat[i];} friend bool operator==(const ConstantMatrix&lhs,const ConstantMatrix&rhs){ for(int i=0;i<N;i++)for(int j=0;j<M;j++)if(lhs[i][j]!=rhs[i][j])return false; return true; } friend bool operator!=(const ConstantMatrix&lhs,const ConstantMatrix&rhs){ for(int i=0;i<N;i++)for(int j=0;j<M;j++)if(lhs[i][j]!=rhs[i][j])return true; return false; } T det()const{ static_assert(N==M); T res=1; ConstantMatrix mat(*this); for(int i=0;i<M;i++){ int idx=-1; for(int j=i;j<N;j++)if(mat[j][i]!=T()){ idx=j; break; } if(idx==-1)return T(); if(i!=idx)std::swap(mat[i],mat[idx]),res=-res; res*=mat[i][i]; T inv_ii=mat[i][i].inv(); for(int j=i+1;j<M;j++)mat[i][j]*=inv_ii; for(int j=i+1;j<N;j++){ T coef=-mat[j][i]; for(int k=i+1;k<M;k++)mat[j][k]+=coef*mat[i][k]; } } return res; } ConstantMatrix inv()const{ static_assert(N==M); ConstantMatrix res=E(),mat=(*this); for(int i=0;i<N;i++){ int id=-1; for(int j=i;j<N;j++)if(mat[j][i]!=T()){ id=j; break; } if(id==-1)return ConstantMatrix(); if(i!=id){ std::swap(mat[i],mat[id]); std::swap(res[i],res[id]); } T inv=mat[i][i].inv(); for(int j=0;j<N;j++)if(i!=j){ T x=mat[j][i]; for(int k=0;k<N;k++){ mat[j][k]-=mat[i][k]*x; res[j][k]-=res[i][k]*x; } } } return res; } template<std::integral U> ConstantMatrix pow(U k)const{ static_assert(N==M); ConstantMatrix res=ConstantMatrix::E(),a(*this); while(k){ if(k&1)res*=a; a*=a; k>>=1; } return res; } std::vector<std::vector<T>>to_vector()const{ std::vector<std::vector<T>>res(N,std::vector<T>(M)); for(int i=0;i<N;i++)for(int j=0;j<M;j++)res[i][j]=dat[i][j]; return res; } friend std::ostream &operator<<(std::ostream &os,const ConstantMatrix&rhs){ for(int i=0;i<N;i++){ for(int j=0;j<M;j++)os<<rhs[i][j]<<" \n"[j+1==M]; } return os; } }; int operate(int lhs,int rhs,int op){ if(op==0)return lhs|rhs; else if(op==1)return lhs&rhs; else if(op==2)return lhs^rhs; else{ debug(lhs,rhs,op); } return -1; } struct M{ struct S{ // ll cntl[2]={0,0}; ConstantMatrix<ll,2,2>mat,allmat; ll cntr[2]={0,0}; // ll al=0; ll ans=0; int rop=-1; }; static S op(S x,S y){ if(x.rop==-1)return y; if(y.rop==-1)return x; S res; res.rop=y.rop; res.mat=x.mat+y.mat*x.allmat; res.allmat=y.allmat*x.allmat; rep(i,2){ res.cntr[i]+=y.cntr[i]; } // res.cntl[operate(x.al,0,x.rop)]+=y.cntl[0]; // res.cntl[operate(x.al,1,x.rop)]+=y.cntl[1]; // debug(res.cntr[0]); // debug(y.allmat); debug(y.allmat); rep(i,2)rep(j,2)if(y.allmat[j][i])res.cntr[j]+=x.cntr[i]; // res.cntr[operate(0,y.al,x.rop)]+=x.cntr[0]; // res.cntr[operate(1,y.al,x.rop)]+=x.cntr[1]; // res.al=operate(x.al,y.al,x.rop); res.ans=x.ans+y.ans; // debug(res.cntr[0]); // debug(x.ans,y.ans,res.ans); rep(i,2){ res.ans+=x.cntr[i]*y.mat[1][i]; // if(y.allmat[1][i])res.ans+=x.cntr[i]; // debug(i,res.ans,x.cntr[i]); } // rep(i,2)rep(j,2){ // if(operate(i,j,x.rop))res.ans+=(ll)x.cntr[i]*y.cntl[j]; // } return res; } static S e(){return S();} }; ConstantMatrix<ll,2,2>getmat(char c,int v){ ConstantMatrix<ll,2,2>res; if(c=='+'){ if(v==0)res[0][0]=res[1][1]=1; else res[1][0]=res[1][1]=1; } else if(c=='*'){ if(v==1)res[0][0]=res[1][1]=1; else res[0][0]=res[0][1]=1; } else{ if(v==0)res[0][0]=res[1][1]=1; else res[0][1]=res[1][0]=1; } return res; } void SOLVE(){ int n,q; cin>>n>>q; n=(n+1)/2; string x; cin>>x; // x+='+'; vector<M::S>init(n); rep(i,n){ // init[i].cntl[x[i*2]=='T']++; init[i].cntr[x[i*2]=='T']++; // init[i].al=x[i*2]=='T'; if(x[i*2]=='T')init[i].ans++; init[i].rop=0; init[i].mat=init[i].allmat=getmat(i==0?'+':x[i*2-1],x[i*2]=='T'); init[i].allmat=init[i].mat; // debug(i,init[i]); debug(i,init[i].cntr[0]); } SparseTable<M>sp(init); debug('U'); rep(i,q){ int l,r; cin>>l>>r; l--,r--; l/=2,r/=2; cout<<sp.prod(l,r+1).ans<<'\n'; } }