結果
問題 | No.2762 Counting and Deleting |
ユーザー |
![]() |
提出日時 | 2025-01-13 23:06:49 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 198 ms / 4,000 ms |
コード長 | 10,095 bytes |
コンパイル時間 | 8,623 ms |
コンパイル使用メモリ | 316,912 KB |
実行使用メモリ | 14,692 KB |
最終ジャッジ日時 | 2025-01-13 23:07:03 |
合計ジャッジ時間 | 9,188 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 15 |
ソースコード
#ifdef t9unkubj #include"debug.cpp" //#include"template_no_debug.h" #else #define dbg(...) 199958 #endif #undef _GLIBCXX_DEBUG #pragma GCC optimize("O3") using namespace std; #include<bits/stdc++.h> using ll=long long; using ull=unsigned long long; template<class T>using vc=vector<T>; template<class T>using vvc=vc<vc<T>>; #define rep(i,n) for(ll i=0;i<(ll)(n);i++) #define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++) #define DREP(i,n,m) for(ll i=(n);i>=(m);i--) #define drep(i,n) for(ll i=((n)-1);i>=0;i--) #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() template<class T,class F> bool chmin(T &x, F y){ if(x>y){ x=y; return true; } return false; } template<class T, class F> bool chmax(T &x, F y){ if(x<y){ x=y; return true; } return false; } double pass_time=0; template <class T,T (*op)(T, T),class F,T (*mapping)(T,F),F (*merge)(F, F)> struct lazy_segtree{ int n; vector<T>data; vector<F>lazy; int log; T e; F id; lazy_segtree(int n1,T e,F id):n(n1),e(e),id(id){ int n_=1; log=0; while(n_<=n)n_*=2,log++; data=vector<T>(n_*2,e); lazy=vector<F>(n_,id); n=n_; for(int i=n_-1;i>0;i--)update(i); } void update(int k){ data[k]=op(data[k*2],data[k*2+1]); } void apply(int k,F x){// data[k]=mapping(data[k],x); if(k<n){ lazy[k]=merge(lazy[k],x); if(lazy[k]==id)return; //segment tree beats! if(data[k].fail)push(k),update(k); } } void push(int k){//上から遅延素を伝播させる apply(k*2,lazy[k]); apply(k*2+1,lazy[k]); lazy[k]=id; } void set(int p,T x){ p+=n; for(int i=log;i>=1;i--){ push(p>>i); } data[p]=x; for(int i=1;i<=log;i++){ update(p>>i); } } void apply(int l,int r,F x){ if(l==r)return; l+=n,r+=n; for(int i=log;i>=1;i--){ if(((l>>i)<<i)!=l)push(l>>i); if(((r>>i)<<i)!=r)push((r-1)>>i); } int l2{l},r2{r}; while(l<r){ if(l&1)apply(l++,x); if(r&1)apply(--r,x); l>>=1,r>>=1; } l=l2,r=r2; for(int i=1;i<=log;i++){ if(((l>>i)<<i)!=l)update(l>>i); if(((r>>i)<<i)!=r)update((r-1)>>i); } } T prod(int l,int r){ l+=n,r+=n; for(int i=log;i>=1;i--){ if(((l>>i)<<i)!=l)push(l>>i); if(((r>>i)<<i)!=r)push((r-1)>>i); } T sml=e,smr=e; while(l<r){ if(l&1)sml=op(sml,data[l++]); if(r&1)smr=op(data[--r],smr); l>>=1,r>>=1; } return op(sml,smr); } T get(int p){ p+=n; for(int i=log;i>=1;i--)push(p>>i); return data[p]; } }; template<class T,class G,class F> F modpow(T x,G p,F m){ T ret=1%m; x%=m; while(p){ if(p&1)ret=(1ll*ret*x)%m; x=(1ll*x*x)%m; p>>=1; } return ret; } template<class T> T extgcd(T a,T b,T&x,T&y){//ax+by=gcd(a,b)となるようなもの if(b==0){ x=1; y=0; return a; }else{ T res=extgcd(b,a%b,y,x); y-=(a/b)*x; return res; } } template<class T> pair<T,T> inv(T x,T m){ T a1,a2; T res=extgcd(x,m,a1,a2); return {a1,m/res}; } constexpr int mod=998244353; struct mint{ long long val; inline long long fast(long long x){ if(x<mod&&x>=0)return x; x%=mod; if(x<0)x+=mod; return x; } mint():val(0){} mint(long long val):val(fast(val)){} mint power(long long m)const { mint res(1); mint ret(*this); while(m){ if(m&1)res*=ret; ret*=ret; m>>=1; } return res; } mint& operator++() { val++; if (val == mod) val = 0; return *this; } mint& operator--() { if (val == 0)val=mod; val--; return *this; } mint operator++(int) { mint result = *this; ++*this; return result; } mint operator--(int) { mint result = *this; --*this; return result; } mint operator-() const { return mint(-val); } friend mint operator +(const mint&a,const mint&b) noexcept{ return mint(a)+=b; } friend mint operator -(const mint&a,const mint&b) noexcept{ return mint(a)-=b; } friend mint operator *(const mint&a,const mint&b) noexcept{ return mint(a)*=b; } friend mint operator /(const mint&a,const mint&b) noexcept{ return mint(a)/=b; } mint& operator+=(const mint&a)noexcept{ val+=a.val; if(val>=mod)val-=mod; return *this; } mint& operator-=(const mint&a)noexcept{ val-=a.val; if(val<0)val+=mod; return *this; } mint& operator*=(const mint&a){ val*=a.val; val=fast(val); return *this; } mint& operator/=(const mint&a){ val*=inv<long long>(a.val,mod).first; val=fast(val); return *this; } bool operator == (const mint&x)const noexcept{ return this->val==x.val; } bool operator != (const mint&x)const noexcept{ return this->val!=x.val; } friend ostream& operator << (ostream &os, const mint &x) noexcept { return os << x.val; } friend istream& operator >> (istream &is, mint &x) noexcept { long long v; is >> v; x=mint(v); return is; } }; vector<mint>fact(1,1),invfact(1,1); void build(int n){ if(n<(int)fact.size())return; fact=invfact=vector<mint>(n+1); fact[0]=1; for(int i=1;i<=n;i++)fact[i]=fact[i-1]*i; invfact[n]=(1/fact[n]); for(int i=n-1;i>=0;i--)invfact[i]=invfact[i+1]*(i+1); } mint C(int a,int b){//aCb if(a<0||b<0||a-b<0)return mint(0); while((int)fact.size()<=a){ fact.push_back(fact.back()*(fact.size())); } while((int)invfact.size()<=a){ invfact.push_back(invfact.back()/invfact.size()); } return fact[a]*invfact[b]*invfact[a-b]; } mint P(int a,int b){ if(a<b||b<0)return 0; return fact[a]*invfact[a-b]; } //a個のものからb個を重複を許して選ぶ mint H(int a,int b){ return C(a+b-1,b); } void print(mint a) { cout << a; } template<class T> pair<T,T> mod_solve(T a,T b,T m){//ax=b mod mとなるxを返す a%=m,b%=m;if(a<0)a+=m;if(b<0)b+=m; T g=gcd(gcd(a,b),m); a/=g,b/=g,m/=g; if(gcd(a,m)>1)return {-1,-1}; return {(inv(a,m).first*b)%m,inv(a,m).second}; } template<class monoid> struct segtree{ int n; vector<monoid>node; static monoid e(){ return monoid::e(); } static monoid op(monoid a,monoid b){ return monoid::op(a,b); } segtree(){} segtree(int n):n(n),node(n*2,e()){ assert(0<=n); } void set(int i,monoid x){ assert(0<=i&&i<n); node[i+=n]=x; while(i>>=1)node[i]=op(node[i<<1],node[i<<1|1]); } monoid prod(int l,int r) const { assert(0<=l&&l<=r&&r<=n); l+=n,r+=n; monoid sml=e(),smr=e(); while(l<r){ if(l&1)sml=op(sml,node[l++]); if(r&1)smr=op(node[--r],smr); l>>=1,r>>=1; } return op(sml,smr); } monoid get(int i){ assert(0<=i&&i<=n); return node[i+n]; } //return max val s.t. f([L,val))) = true template<class F> int max_right(int L,const F&f) const { assert(f(e())); int l=n+L; int w=1; monoid ansL=e(); for(;L+w<=n;l>>=1,w<<=1){ if(l&1){ if(!(f(op(ansL,node[l]))))break; ansL=op(ansL,node[l++]); L+=w; } } while(l<<=1,w>>=1){ if(L+w<=n&&f(op(ansL,node[l]))){ ansL=op(ansL,node[l++]); L+=w; } } return L; } //return min val s.t. f([val,R)) = true template<class F> int min_left(int R,const F&f) const { assert(f(e())); int r=n+R; int w=1; monoid ansR=e(); for(;R-w>=n;r>>=1,w<<=1){ if(r&1){ if(!(f(op(ansR,node[r-1]))))break; ansR=op(ansR,node[--r]); R-=w; } } while(r<<=1,w>>=1){ if(R-w>=n&&f(op(ansR,node[r-1]))){ ansR=op(ansR,node[--r]); R-=w; } } return R; } }; struct mat{ array<array<mint,3>,3>a; static mat op(mat &a, mat &b) { mat res{}; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { for (int k = 0; k < 3; k++) { (res.a[i][j] += a.a[i][k] * b.a[k][j]); } } } return res; } static mat e(){ mat res; rep(i,3)res.a[i][i]=1; return res; } }; mat zero(){ mat res=mat::e(); res.a[0][1]=1; return res; } mat one(){ mat res=mat::e(); res.a[1][0]=1; res.a[1][2]=1; return res; } void solve(){ int n,q; cin>>n>>q; string s; cin>>s; segtree<mat>seg(n); rep(i,n){ seg.set(n-i-1,(s[i]=='1'?one():zero())); } set<int>st; rep(i,n)st.insert(i); while(q--){ int t,l,r; cin>>t>>l>>r; --l,--r; if(t==1){ while(1){ auto it=st.lower_bound(l); if(it==st.end()||*it>r)break; seg.set(n-*it-1,mat::e()); st.erase(it); } }else{ auto R=seg.prod(n-r-1,n-l); cout<<R.a[0][2]+R.a[1][2]<<"\n"; } } } signed main(){ cin.tie(0)->sync_with_stdio(0); pass_time=clock(); int t=1; //cin>>t; while(t--)solve(); pass_time=clock()-pass_time; dbg(pass_time/CLOCKS_PER_SEC); }