题目链接:https://atcoder.jp/contests/agc029/tasks/agc029_a
数据范围:略。
题解:
假设黑色是$1$,白色是$0$的话,不难发现每次操作会恰好使得整个序列的逆序对数- - 。
故此考虑怎么求逆序对。
其实不用树状数组,因为只有两个数,只需要记录一下即可。
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define N 200010
using namespace std;
typedef long long ll;
char *p1, *p2, buf[100000];
#define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ )
int rd() {
int x = 0, f = 1;
char c = nc();
while (c < 48) {
if (c == ‘-‘)
f = -1;
c = nc();
}
while (c > 47) {
x = (((x << 2) + x) << 1) + (c ^ 48), c = nc();
}
return x * f;
}
int b[2];
char s[N];
int main() {
scanf("%s", s + 1);
int n = strlen(s + 1);
ll ans = 0;
for (int i = 1; i <= n; i ++ ) {
int c = ((s[i] == ‘B‘) ? 1 : 0);
// cout << c << endl ;
if (!c) {
ans += b[1];
}
b[c] ++ ;
}
cout << ans << endl ;
return 0;
}
[Agc029A]Irreversible operation_逆序对
原文:https://www.cnblogs.com/ShuraK/p/11734592.html