結果

問題 No.2611 Count 01
ユーザー inksamuraiinksamurai
提出日時 2024-01-19 23:13:54
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 305 ms / 6,000 ms
コード長 2,735 bytes
コンパイル時間 4,756 ms
コンパイル使用メモリ 268,160 KB
実行使用メモリ 40,476 KB
最終ジャッジ日時 2024-01-19 23:14:08
合計ジャッジ時間 12,342 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,676 KB
testcase_01 AC 2 ms
6,676 KB
testcase_02 AC 2 ms
6,676 KB
testcase_03 AC 271 ms
40,476 KB
testcase_04 AC 301 ms
40,476 KB
testcase_05 AC 278 ms
40,476 KB
testcase_06 AC 271 ms
40,476 KB
testcase_07 AC 282 ms
40,476 KB
testcase_08 AC 273 ms
40,476 KB
testcase_09 AC 279 ms
40,476 KB
testcase_10 AC 273 ms
40,476 KB
testcase_11 AC 305 ms
40,476 KB
testcase_12 AC 275 ms
40,476 KB
testcase_13 AC 278 ms
40,476 KB
testcase_14 AC 280 ms
40,476 KB
testcase_15 AC 271 ms
40,476 KB
testcase_16 AC 272 ms
40,476 KB
testcase_17 AC 278 ms
40,476 KB
testcase_18 AC 271 ms
40,476 KB
testcase_19 AC 279 ms
40,476 KB
testcase_20 AC 271 ms
40,476 KB
testcase_21 AC 271 ms
40,476 KB
testcase_22 AC 271 ms
40,476 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
#define int ll
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _48SMghu ios::sync_with_stdio(0),cin.tie(0)
using ll=long long;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}

// snuke's mod int
template <ll mod>
struct modint{
	ll x;
	modint(ll x=0):x((x%mod+mod)%mod){}
	modint operator-()const{return modint(-x);}
	modint& operator+=(const modint a){if((x+=a.x)>=mod) x-=mod; return *this;}
	modint& operator-=(const modint a){if((x+=mod-a.x)>=mod) x-=mod; return *this;}
	modint& operator*=(const modint a){(x*=a.x)%=mod; return *this;}
	modint operator+(const modint a)const{modint res(*this); return res+=a;}
	modint operator-(const modint a)const{modint res(*this); return res-=a;}
	modint operator*(const modint a)const{modint res(*this); return res*=a;}
	modint pow(ll n)const{
		modint res=1,x(*this);
		while(n){
			if(n&1)res*=x;
			x*=x;
			n>>=1;
		}
		return res;
	}
	modint inv()const{return pow(mod-2);}
};

using mint=modint<998244353>;

struct N{
	mint ad=0;
	array<mint,2> cnt={0};
	array<mint,2> s={0};
	array<mint,2> f={0};
};

N op(N l,N r){
	N res;
	rep(i,2){
		res.cnt[i]+=l.cnt[i]+r.cnt[i];
		res.s[i]+=l.s[i]+r.s[i];
		res.f[i]+=l.f[i]+r.f[i];
	}
	res.ad=l.ad+r.ad;
	// (0, 1)
	res.f[1]+=l.cnt[0]*r.s[1];
	res.f[0]+=l.s[0]*r.cnt[1];
	res.ad+=l.s[0]*r.s[1];
	// (1, 0)
	res.f[1]+=l.cnt[1]*r.s[0];
	res.f[0]+=l.s[1]*r.cnt[0];
	res.ad+=l.s[1]*r.s[0];
	return res;
}

N e(){
	return N{};
}

void slv(){
	int n,q;
	cin>>n>>q;
	string s;
	cin>>s;
	atcoder::segtree<N,op,e> seg(n);
	rep(i,n){
		N now;
		if(s[i]=='1'){
			now.cnt[1]+=1;
			now.s[1]+=i;
		}else{
			now.cnt[0]+=1;
			now.s[0]+=i;
		}
		seg.set(i,now);
	}
	rep(i,q){
		int typ;
		cin>>typ;
		if(typ==2){
			int l,r;
			cin>>l>>r;
			l-=1,r-=1;
			l-=1,r+=1;
			N now=seg.prod(l+1,r);
			mint ans=mint(l)*now.f[1]+mint(r)*now.f[0]-mint(l*r)*now.cnt[0]*now.cnt[1];
			ans-=now.ad;
			cout<<ans.x<<"\n";	
		}else{
			int pos;
			cin>>pos;
			pos-=1;
			s[pos]^=1;
			N now;
			if(s[pos]=='1'){
				now.cnt[1]+=1;
				now.s[1]+=pos;
			}else{
				now.cnt[0]+=1;
				now.s[0]+=pos;
			}
			seg.set(pos,now);
		}
	}
	// int l=2,r=5;
	// N now=seg.prod(l+1,r);
	// mint ans=mint(l)*now.f[1]+mint(r)*now.f[0]-mint(l*r)*now.cnt[0]*now.cnt[1];
	// ans-=now.ad;
	// print(now.f[1].x);
	// // print(now.f[1].x,now.f[0].x);
	// print(ans.x);
}

signed main(){
_48SMghu;
	slv();
}
0