AcWing 2003. 找到牛!树状数组
原题链接
简单
作者:
K_cccc
,
2022-04-28 10:29:23
,
所有人可见
,
阅读 141
import java.io.*;
public class Main {
private static final int N = 50010;
private static int[] c = new int[N];
private static int n;
private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
String s = reader.readLine();
n = s.length();
for (int i = 0; i < n - 1; i++) {
if (s.charAt(i) == '(' && s.charAt(i + 1) == '(') {
add(i + 1, 1);
}
}
int ans = 0;
for (int i = 0; i < n - 1; i++) {
if (s.charAt(i) == ')' && s.charAt(i + 1) == ')') {
ans += ask(i + 1);
}
}
writer.write(ans + "\n");
writer.flush();
}
private static int ask(int x) {
int res = 0;
for (int i = x; i != 0; i -= lowbit(i)) res += c[i];
return res;
}
private static void add(int x, int k) {
for (int i = x; i <= n; i += lowbit(i)) c[i] += k;
}
private static int lowbit(int x) {
return x & -x;
}
}