AcWing 1884. COW -- 前缀和 + 二分
原题链接
简单
作者:
琦...
,
2022-04-01 21:40:32
,
所有人可见
,
阅读 134
# include <bits/stdc++.h>
# define x first
# define y second
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 1e5+10;
PII c[N], o[N], w[N];
int n, idx, lc, lo, lw;
string s;
LL res;
void op(PII *h, int len)
{
int sum = 0;
for(int i = 1; i <= len; i ++)
{
h[i].second += sum;
sum = h[i].second;
}
}
int find_l(int temp) //查找 判断 求num
{
int l = 1, r = lc;
while(l < r)
{
int mid = l+r+1 >> 1;
if(c[mid].x < temp) l = mid;
else r = mid - 1;
}
if(c[l].x > temp) return 0;
return c[l].y;
}
int find_r(int temp) //查找 判断 求num
{
int l = 1, r = lw;
while(l < r)
{
int mid = l+r >> 1;
if(w[mid].x > temp) r = mid;
else l = mid + 1;
}
if(w[l].x < temp) return 0;
else return w[lw].y - w[l-1].y;
}
int main()
{
cin >> n >> s; s += 'N';
int num = 1; char t = s[0];
for(int i = 1; i <= n; i ++)
{
if(t != s[i])
{
if(t == 'C') c[++ lc] = {idx++,num};
else if(t == 'O') o[++ lo] = {idx++,num};
else w[++ lw] = {idx++,num};
t = s[i];
num = 1;
}
else num ++;
}
op(c,lc); op(w,lw); //对 O 和 W的数量进行前缀和
for(int j = 1; j <= lo; j ++) //枚举O的位置
{
int ido = o[j].x, numo = o[j].y;
int numc = find_l(ido); // 比O位置小的都符合
int numw = find_r(ido); // 比O位置大的都符合
res += (LL)numo*numc*numw;
}
printf("%lld",res);
return 0;
}