您提到的D003 偏序问题 顺序对 ABC441E A似乎是一个特定的编码或标识，可能来源于某个系统、课程或项目。由于缺乏上下文，我无法直接给出具体的解答。不过，我可以尝试解释一下偏序问题和顺序对这两个概念：1. **偏序问题**：在数学中，偏序关系是一种
摘要：ABC441E A > B substring - AtCoder 给一个只含字符 ABC 的字符串，问有多少个子串中 A 的数量大于 B 的数量。令 (A=1,B=-1,C=0) 求前缀和数组 (a) 可知子
ABC441E A > B substring - AtCoder
给一个只含字符 ABC 的字符串，问有多少个子串中 A 的数量大于 B 的数量。令 \(A=1,B=-1,C=0\) 求前缀和数组 \(a\) 可知子串应该满足的条件为
\(i<j\)
\(a_j-a_i>0\) 即 \(a_i<a_j\)
不难看出为二维偏序问题，转化为求顺序对的数量。
因为 \(N\) 最大为 \(5\times10^5\) 所以 \(a_i\) 的范围为 \((-5\times10^5,5\times10^5)\) ，考虑离散化一下。
从左往右枚举 \(a_i\) ，查询比 \(a_i\) 小的值的个数，即查询 \(rank[a_i]-1\) 。
答案就是所有比 \(a_i\) 小的的个数和
import sys
from math import inf
if 1:
inp = lambda: sys.stdin.readline().strip()
II = lambda: int(inp())
MII = lambda: map(int, inp().split())
LII = lambda: list(MII())
Max = lambda x, y: x if x > y else y
Min = lambda x, y: x if x < y else y
class BIT:
def __init__(self, n):
self.tree = [0] * (n + 1)
def add(self, i, val):
while i < len(self.tree):
self.tree[i] += val
i += i & -i
def pf(self, i):
s = 0
while i > 0:
s += self.tree[i]
i -= i & -i
return s
def main():
n = II()
s = inp()
a = [0]
cur = 0
for c in s: # 预处理前缀和数组
if c == "A":
cur += 1
elif c == 'B':
cur -= 1
a.append(cur)
sa = sorted(list(set(a)))
rank = {val: i + 1 for i, val in enumerate(sa)}
bit = BIT(len(sa))
ans = 0
for x in a:
r = rank[x]
ans += bit.pf(r - 1) # 小于r的数量
bit.add(r, 1)
print(ans)
if __name__ == "__main__":
main()