Submission #72544898

---

Source Code Expand

#include<bits/stdc++.h>
#include<limits.h>
#include<unordered_map>
//#include<chrono>
using namespace std;
//#define randint uniform_int_distribution<int>
#define ll long long
#define ld long double
#define Int __int128
#define ull unsigned long long
#define uint unsigned
#define pii pair<int,int>
#define pll pair<long long,long long>
#define fi first
#define se second

template<typename T>T Max(T a,T b){return a>b?a:b;}template<typename T,typename...Args>T Max(T a,Args...args){return a>Max(args...)?a:Max(args...);}
template<typename T>T Min(T a,T b){return a<b?a:b;}template<typename T,typename...Args>T Min(T a,Args...args){return a<Min(args...)?a:Min(args...);}

namespace io{const int __SIZE=(1<<21)+1;char ibuf[__SIZE],*iS,*iT,obuf[__SIZE],*oS=obuf,*oT=oS+__SIZE-1,__c,qu[55];int __f,qr,_eof;
#define Gc()(iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,__SIZE,stdin),(iS==iT?EOF:*iS++)):*iS++)
	inline void flush(){fwrite(obuf,1,oS-obuf,stdout),oS=obuf;}inline void gc(char&x){x=Gc();}inline void pc(char x){*oS++=x;if(oS==oT)flush();}inline void pstr(const char*s){int __len=strlen(s);for(__f=0;__f<__len;++__f)pc(s[__f]);}inline void gstr(char*s){for(__c=Gc();__c<32||__c>126||__c==' ';)__c=Gc();for(;__c>31&&__c<127&&__c!=' '&&__c!='\n'&&__c!='\r';++s,__c=Gc())*s=__c;*s=0;}template<class I>inline bool gi(I&x){_eof=0;for(__f=1,__c=Gc();(__c<'0'||__c>'9')&&!_eof;__c=Gc()){if(__c=='-')__f=-1;_eof|=__c==EOF;}for(x=0;__c<='9'&&__c>='0'&&!_eof;__c=Gc())x=x*10+(__c&15),_eof|=__c==EOF;x*=__f;return!_eof;}template<class I>inline void print(I x){if(!x)pc('0');if(x<0)pc('-'),x=-x;while(x)qu[++qr]=x%10+'0',x/=10;while(qr)pc(qu[qr--]);}struct Flusher_{~Flusher_(){flush();}}io_flusher_;}using io::pc;using io::gc;using io::pstr;using io::gstr;using io::gi;using io::print;

template<typename T>ostream&operator<<(ostream&os,const vector<T>&v){os<<"{ ";string sep;for(const auto&x:v)os<<sep<<x,sep=", ";return os<<" }";}
template<typename T,size_t size>ostream&operator<<(ostream&os,const array<T,size>&arr){os<<"{ ";string sep;for(const auto&x:arr)os<<sep<<x,sep=", ";return os<<" }";}
template<typename A,typename B>ostream&operator<<(ostream&os,const pair<A,B>&p){return os<<'('<<p.first<<","<<p.second<<')';}
template<typename K,typename V>ostream&operator<<(ostream&os,const map<K,V>&m){os<<"{ ";string sep;for(const auto&p:m)os<<sep<<p.first<<":"<<p.second,sep=", ";return os<<" }";}
template<typename T>ostream&operator<<(ostream&os,const set<T>&s){os<<"{ ";string sep;for(const auto&x:s)os<<sep<<x,sep=", ";return os<<" }";}
template<typename T>ostream&operator<<(ostream&os,const multiset<T>&s){os<<"{ ";string sep;for(const auto&x:s)os<<sep<<x,sep=", ";return os<<" }";}

namespace detail{template<typename T>constexpr bool is_string_type_v=std::is_same_v<std::decay_t<T>,std::string>||std::is_same_v<std::decay_t<T>,const char*>||std::is_same_v<std::decay_t<T>,char*>;template<typename T>void print_val(const T&val){if constexpr(is_string_type_v<T>){std::cerr<<'"'<<val<<'"';}else{std::cerr<<val;}}inline std::string_view trim(std::string_view sv){sv.remove_prefix(std::min(sv.find_first_not_of(" \t"),sv.size()));size_t end=sv.find_last_not_of(" \t");if(end!=std::string_view::npos){sv.remove_suffix(sv.size()-end-1);}return sv;}template<typename...Args>void dbgg_impl(int line,const char*msg,const char*raw_names,Args&&...args){std::cerr<<"Line "<<line<<": "<<msg;if constexpr(sizeof...(Args)>0){if(strlen(msg)>0)std::cerr<<" | ";std::string_view names(raw_names);size_t arg_idx=0;([&]{if(arg_idx>0)std::cerr<<", ";size_t comma_pos=names.find(',');std::string_view current_name=(comma_pos==std::string_view::npos)?names:names.substr(0,comma_pos);std::cerr<<trim(current_name)<<"=";print_val(args);if(comma_pos!=std::string_view::npos){names.remove_prefix(comma_pos+1);}arg_idx++;}(),...);}std::cerr<<std::endl;}}
#ifdef LOCAL_ZCZ
#define dbg(Msg,...)detail::dbgg_impl(__LINE__,Msg,#__VA_ARGS__,##__VA_ARGS__)
#else
#define dbg(...)
#endif

#define int long long
mt19937 rnd(time(0));

namespace Zhchz{
	constexpr int N=2000010,inf=0x3f3f3f3f,base=389,mod=998244353;
	constexpr ll INF=0x3f3f3f3f3f3f3f3f,INFF=0x7f7f7f7f7f7f7f7f;
	int n;
	int a[N],sum[N];
	
	int t[N];
#define lowbit(x) ((x)&(-(x)))
	void add(int x,int v){
		x+=600001;
		while(x<=1200002){
			dbg("",x);
			t[x]+=v;
			x+=lowbit(x);
		}
	}
	int query(int x){
		x+=600001;
		int res=0;
		while(x){
			res+=t[x];
			x-=lowbit(x);
		}
		return res;
	}
	
	signed main(){
#ifndef LOCAL_ZCZ
		ios::sync_with_stdio(0);
		cin.tie(0);
#endif
		cin>>n;
		for(int i=1;i<=n;i++){
			char ch;cin>>ch;
			if(ch=='A') a[i]=1;
			else if(ch=='B') a[i]=-1;
		}
		add(0,1);
		int ans=0;
		for(int i=1;i<=n;i++){
			sum[i]=sum[i-1]+a[i];
			dbg("",sum[i]);
			ans+=query(sum[i]-1);
			add(sum[i],1);
		}
		cout<<ans;
		return 0;
	}
}
signed main(){return Zhchz::main();}

Submission Info

Judge Result