题目大意
给定一个只含$+$和$-$两种字符的字符串，可以进行以下操作：
求通过任意次操作后，$+$和$-$数量相等的子串数量。
解题思路
前缀和的思想，$+$加$1$，$-$减$1$，当前值为$0$意味着符合要求。然后有一个简单的性质，如果当前值为负数且为$3$的倍数也可以通过操作使其合法。那么，问题就是求满足：
$\left{\begin{aligned}&0≤l<r≤n\&a_r≤a_l\&a_l≡a_r(mod\ 3)\end{aligned}\right.$
同余分组后求逆序对数即可。
注意树状数组中下标不能为负数，所以可以开两倍空间。然后倒序求逆序对。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include <bits/stdc++.h>
#define maxn 400100
#define lowbit(x) x&(-x)
#define int long long
typedef __int128_t int128;
using namespace std;
const double eps=-1e8;
int tre[3][maxn],n,m,a[maxn];
void add(int t,int x){while(x<=m) tre[t][x]++,x+=lowbit(x);}
int sum(int t,int x){
int res=0;
while(x) res+=tre[t][x],x-=lowbit(x);
return res;
}
void solve(){
cin >> n; m=2*n+10;
int ans=0,base=n+1;
for(int i=0;i<3;++i){
for(int j=0;j<=m;++j){
tre[i][j]=0;
}
}
string s; cin >> s; s=" "+s;
for(int i=1;i<=n;++i) a[i]=a[i-1]+(s[i]=='+'?1:-1);
for(int i=n;i>=0;--i){
int m=(a[i]%3+3)%3;
ans+=sum(m,a[i]+base); add(m,a[i]+base);
}
cout << ans << '\n';
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t; cin >> t;
while(t--){
solve();
}
return 0;
}
|
