Codeforces 1535F 字符串 + 倍增 + BIT

题意

传送门 Codeforces 1535F String Distance

题解

若字符串 $a,b$ 的字符多重集合不相等，则 $f(a,b)=1337$。反之，将 $a,b$ 整个串做排序必然相等，则 $f(a,b)\le 2$。此时只用考虑 $f(a,b)=1$ 的情况。

若仅对 $a$ 进行一次子串 $[l,r)$ 排序使 $a=b$，则字典序意义下 $a>b$；且 $a,b$ 在 $l$ 左侧的前缀与 $r$ 右侧的后缀相等，则字典序意义下 $a,b$ 的反串 $a^{\prime },b^{\prime }$ 满足 $a^{\prime }<b^{\prime }$。可以观察到，只需要考虑 $b$ 中最长的连续单调不减的子串。

一类优雅的实现思路参考自 Comments。首先，将各字符串自身进行排序后，再按照字典序将所有字符串进行排序。此时满足 $f(a,b)$ 的字符串位于连续的区间，划分出这样的字符多重集合相等的等价类依次处理。字符串间的最长前缀和后缀，都可以应用类似于求后缀数组的思路，排序后进行 $RMQ$；此时求后缀用的是反串。

枚举 LCP 的长度，这样的串也是连续的，逆字典序依次处理。当遇到一个最长的连续单调不减的子串，则查找 LCS 长度满足条件的字符串，这样的字符串在反串上也是连续的，可以离线用单调栈配合二分解决，也可以在线地通过倍增求解。最后这样连续区间中满足条件的字符串数量，可以通过 $BIT$ 维护。

设字符产长度为 $m$，总时间复杂度 $O(nm\log n)$。

#include 
using namespace std;
using ll = long long;

struct BIT {
    vector<int> a;
    BIT(int n) : a(n + 1) {}
    int sum(int i) {
        int s = 0;
        while (i > 0) {
            s += a[i];
            i -= i & -i;
        }
        return s;
    }
    void add(int i, int x) {
        ++i;
        while (i < (int)a.size()) {
            a[i] += x;
            i += i & -i;
        }
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<string> s(n);
    for (int i = 0; i < n; ++i) {
        cin >> s[i];
    }
    vector<vector<int>> groups;
    {
        auto ss = s;
        for (auto &a : ss) {
            sort(a.begin(), a.end());
        }
        vector<int> ord(n);
        iota(ord.begin(), ord.end(), 0);
        sort(ord.begin(), ord.end(), [&](int i, int j) { return ss[i] < ss[j]; });
        for (int i = 0; i < n; ++i) {
            if (i == 0 || ss[ord[i]] != ss[ord[i - 1]]) {
                groups.push_back({});
            }
            groups.back().push_back(ord[i]);
        }
    }

    int m = s[0].size();
    ll res = 0, pre = 0;
    for (auto &g : groups) {
        int sz = g.size();
        sort(g.begin(), g.end(), [&](int i, int j) { return s[i] < s[j]; });
        vector<string> ss(sz);
        for (int i = 0; i < sz; ++i) {
            ss[i] = s[g[i]];
        }
        vector<string> rs(sz);
        for (int i = 0; i < sz; ++i) {
            rs[i] = ss[i];
            reverse(rs[i].begin(), rs[i].end());
        }
        vector<int> ord(sz);
        iota(ord.begin(), ord.end(), 0);
        sort(ord.begin(), ord.end(), [&](int i, int j) { return rs[i] < rs[j]; });
        vector<int> rnk(sz);
        for (int i = 0; i < sz; ++i) {
            rnk[ord[i]] = i;
        }

        vector<vector<int>> idx(m, vector<int>(sz));
        for (int i = 0; i + 1 < m; ++i) {
            for (int j = 1; j < sz; ++j) {
                idx[i + 1][j] = idx[i + 1][j - 1];
                if (idx[i][j] != idx[i][j - 1]) {
                    ++idx[i + 1][j];
                    continue;
                }
                if (ss[j][i] != ss[j - 1][i]) ++idx[i + 1][j];
            }
        }

        vector<int> lg(sz);
        lg[0] = -1;
        for (int i = 1; i < sz; ++i) lg[i] = lg[i >> 1] + 1;
        vector<vector<int>> st(sz, vector<int>(lg[sz - 1] + 1, -1));
        {
            for (int i = 1; i < sz; ++i) {
                int j = ord[i], k = ord[i - 1];
                int pos = 0;
                while (pos < m && rs[j][pos] == rs[k][pos]) ++pos;
                st[i][0] = pos;
            }
            for (int i = 0; i < sz; ++i) {
                for (int j = 0; j + 1 <= lg[i]; ++j) {
                    st[i][j + 1] = min(st[i][j], st[i - (1 << j)][j]);
                }
            }
        }

        auto get = [&](int i, int d) {
            for (int k = lg[i]; k >= 0; --k) {
                if (st[i][k] >= d) {
                    i -= 1 << k;
                }
            }
            return i;
        };

        vector<int> nxt(sz);
        BIT bit(sz);
        ll num = 0;
        for (int i = 0; i < m; ++i) {
            for (int l = 0, r = 0; l < sz; l = r) {
                while (r < sz && idx[i][r] == idx[i][l]) ++r;
                for (int j = r - 1; j >= l; --j) {
                    if (nxt[j] == i) {
                        int t = nxt[j] + 1;
                        while (t < m && ss[j][t] >= ss[j][t - 1]) ++t;
                        nxt[j] = t;

                        int rem = m - nxt[j];
                        int k = get(rnk[j], rem);
                        num += bit.sum(rnk[j]) - bit.sum(k);
                    }
                    bit.add(rnk[j], 1);
                }

                for (int j = l; j < r; ++j) {
                    bit.add(rnk[j], -1);
                }
            }
        }

        res += sz * pre * 1337;
        res += (ll)sz * (sz - 1);
        res -= num;
        pre += sz;
    }

    cout << res << '\n';

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146