从CF1660F2看同余分组

https://codeforces.com/contest/1660/problem/F2

同余分组，树状数组维护逆序对

先承继F1的做法，维护一个前缀和数组，让 s[i] == '+' 为 (1)，s[i] == '-' 为 (-1)。

那么要满足两个条件：

  • (pre_r - pre_l \leq 0)
    • 要么加减号相同，要么减号更多（只有减号能减少）
  • (pre_r - pre_l \equiv 0 \pmod{3})
    • 两个减号变成一个加号，相差为三的倍数。

其中第二个条件可以同余转化为

[pre_r\equiv pre_l\pmod 3
]

而第一个条件显然 (l < r)​，那么第一个条件等效于求逆序对。

而要求的逆序对还要满足 (pre_r\equiv pre_l\pmod 3)，可以发现三的余数极少，所以对于三的每个余数分别开树状数组来维护逆序对就能满足两个条件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void solve()
{
    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;
    std::vector<int> pre(n + 1);
    for (int i = 0; i < n; i++) {pre[i + 1] = pre[i] + (s[i] == '+' ? 1 : -1);}
    //对%3的余数分组开Fenwick
    //0, 1, 2

    std::vector fenwicks(3, Fenwick<int>(n * 2 + 1));
    auto get = [&](int x) {return (x % 3 + 3) % 3;};
    i64 ans = 0;
    for (int i = n; i >= 0; i--) {
        ans += fenwicks[get(pre[i])].sum(pre[i] + n + 1);//用pre[i] % 3 的余数来分组，在组内求逆序对。
        fenwicks[get(pre[i])].add(pre[i] + n, 1);
    }
    std::cout << ans << '\n';
}