F2. Promising String (hard version)_BIT正序对+离散化+同余分组

题目大意：

给一串由+-构成的序列，两个-可以合并成一个+。一个串+-数量相等就称其为好串，若一个串可以通过若干次合并变成好串那么我们称其为P串。现在给定一个串，问其中有多少的子串是P串。

思路和代码：

首先，一个子串的'-'的数量num0和'+'的数量num1之差为三的倍数即可（num0>=num1）。

考虑维护f数组，fi表示[1，i]区间中num0和num1的差值。对于区间[l,r]，只要满足以下条件即可对答案产生贡献

1）f[r]>=f[l-1]

2）(f[r] - f[l - 1]) % 3 == 0

对于条件2，我们变化一下式子可得：

(f[r] % 3 - f[l - 1] % 3) % 3 == 0

也就是说f[r] % 3要和 f[l - 1] % 3相等。于是我们可以对其模3，对同余的进行分组。然后对012三种余数维护一个“正序数”即可。

当然，f数组会出现负数，但是BIT只能维护正数，所以我们可以对f数组进行离散化。

int n , m , k ;

void add(int x , int val , vct &tr){
	while(x <= n + 2){
		tr[x] += val ;
		x += (x & -x) ;
	}
}

ll query(int x , vct &tr){
	ll res = 0 ;
	while(x){
		res += tr[x] ;
		x -= (x & -x) ;
	}
	return res ;
}

int getid(int x , vct &d){
	return lower_bound(all(d) , x) - d.begin() + 1 ;
}

void solve(){
	string s ; cin >> n >> s ;
	
	vct f(n + 1 , 0) ;
	rep(i , 1 , n) f[i] = f[i - 1] + (s[i - 1] == '-' ? 1 : -1) ;
	
	vct d(1 , 0) ;
	rep(i , 1 , n) d.pb(f[i]) ;
	sort(all(d)) ;
	
	d.erase(unique(all(d)) , d.end()) ;
	
	vct > tr(3 , vct (n + 2 , 0)) ;

	ll ans = 0 ;
	rep(i , 0 , n){
		int p = getid(f[i] , d) ;
		ans += query(p , tr[p % 3]) ;
		add(p , 1 , tr[p % 3]) ;
		
	}
	cout << ans << "\n" ;
	
}//code_by_tyrii 

小结：