QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#720311#9406. TriangleDaiRuiChen007WA 2ms5848kbC++177.4kb2024-11-07 11:47:552024-11-07 11:47:57

Judging History

你现在查看的是最新测评结果

  • [2024-11-07 11:47:57]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:5848kb
  • [2024-11-07 11:47:55]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
struct SuffixArray {
    int n;
    std::vector<int> sa, rk, lc;
    SuffixArray(const std::vector<int> &s) {
        n = s.size();
        sa.resize(n);
        lc.resize(n - 1);
        rk.resize(n);
        std::iota(sa.begin(), sa.end(), 0);
        std::sort(sa.begin(), sa.end(),
            [&](int a, int b) {
                return s[a] < s[b];
            });
        rk[sa[0]] = 0;
        for (int i = 1; i < n; i++) {
            rk[sa[i]] = rk[sa[i - 1]] + (s[sa[i]] != s[sa[i - 1]]);
        }
        int k = 1;
        std::vector<int> tmp, cnt(n);
        tmp.reserve(n);
        while (rk[sa[n - 1]] < n - 1) {
            tmp.clear();
            for (int i = 0; i < k; i++) {
                tmp.push_back(n - k + i);
            }
            for (auto i : sa) {
                if (i >= k) {
                    tmp.push_back(i - k);
                }
            }
            std::fill(cnt.begin(), cnt.end(), 0);
            for (int i = 0; i < n; i++) {
                cnt[rk[i]]++;
            }
            for (int i = 1; i < n; i++) {
                cnt[i] += cnt[i - 1];
            }
            for (int i = n - 1; i >= 0; i--) {
                sa[--cnt[rk[tmp[i]]]] = tmp[i];
            }
            std::swap(rk, tmp);
            rk[sa[0]] = 0;
            for (int i = 1; i < n; i++) {
                rk[sa[i]] = rk[sa[i - 1]] + (tmp[sa[i - 1]] < tmp[sa[i]] || sa[i - 1] + k == n || tmp[sa[i - 1] + k] < tmp[sa[i] + k]);
            }
            k *= 2;
        }
        for (int i = 0, j = 0; i < n; i++) {
            if (rk[i] == 0) {
                j = 0;
            } else {
                for (j -= (j > 0); i + j < n && sa[rk[i] - 1] + j < n && s[i + j] == s[sa[rk[i] - 1] + j]; j++)
                    ;
                lc[rk[i] - 1] = j;
            }
        }
    }
};

constexpr int N = 1E6 + 2;

int trie[N][26];
int tot;
int num;
int id[N];

int newNode() {
    int x = ++tot;
    std::fill(trie[x], trie[x] + 26, 0);
    id[x] = -1;
    return x;
}

int add(const std::string &s) {
    int p = 1;
    for (auto c : s) {
        int i = c - 'a';
        int &q = trie[p][i];
        if (!q) {
            q = newNode();
        }
        p = q;
    }
    if (id[p] == -1) {
        id[p] = num++;
    }
    return id[p];
}
template <typename T>
struct Fenwick {
    int n;
    std::vector<T> a;
    
    Fenwick(int n_ = 0) {
        init(n_);
    }
    
    void init(int n_) {
        n = n_;
        a.assign(n, T{});
    }
    
    void add(int x, const T &v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] = a[i - 1] + v;
        }
    }
    
    T sum(int x) {
        T ans{};
        for (int i = x; i > 0; i -= i & -i) {
            ans = ans + a[i - 1];
        }
        return ans;
    }
    
    T rangeSum(int l, int r) {
        return sum(r) - sum(l);
    }
    
    int select(const T &k) {
        int x = 0;
        T cur{};
        for (int i = 1 << std::__lg(n); i; i /= 2) {
            if (x + i <= n && cur + a[x + i - 1] <= k) {
                x += i;
                cur = cur + a[x - 1];
            }
        }
        return x;
    }
};

std::vector<int> Z(std::string s) {
    int n = s.size();
    std::vector<int> z(n + 1);
    z[0] = n;
    for (int i = 1, j = 1; i < n; i++) {
        z[i] = std::max(0, std::min(j + z[j] - i, z[i - j]));
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            z[i]++;
        }
        if (i + z[i] > j + z[j]) {
            j = i;
        }
    }
    return z;
}

void solve() {
    int n;
    std::cin >> n;
    
    tot = 0;
    num = 0;
    newNode();
    
    std::vector<std::string> s;
    std::vector<int> st;
    std::vector<int> cnt;
    std::vector<int> T;
    for (int i = 0; i < n; i++) {
        std::string a;
        std::cin >> a;
        int p = add(a);
        if (p >= s.size()) {
            st.push_back(T.size());
            for (auto c : a) {
                T.push_back(c);
            }
            T.push_back(-st.size());
            s.push_back(a);
            cnt.push_back(1);
        } else {
            cnt[p]++;
        }
    }
    
    n = s.size();
    
    std::vector<std::vector<int>> z(n);
    for (int i = 0; i < n; i++) {
        z[i] = Z(s[i]);
    }
    
    auto cmp = [&](int i, int j) -> int {
        int c = 1;
        if (s[i].size() > s[j].size()) {
            c *= -1;
            std::swap(i, j);
        }
        int t = z[j][s[i].size()];
        if (s[i].size() + t < s[j].size()) {
            return s[j][t] < s[j][t + s[i].size()] ? -c : c;
        }
        t = z[j][s[j].size() - s[i].size()];
        if (t == s[i].size()) {
            return 0;
        }
        return s[j][s[j].size() - s[i].size() + t] < s[i][t] ? -c : c;
    };
    
    std::vector<int> ord(n);
    std::iota(ord.begin(), ord.end(), 0);
    std::sort(ord.begin(), ord.end(),
        [&](int i, int j) {
            auto &a = s[i], &b = s[j];
            for (int l = 0; l < std::min(a.size(), b.size()); l++) {
                if (a[l] != b[l]) {
                    return a[l] < b[l];
                }
            }
            return cmp(i, j) == -1;
        });
    
    std::vector<int> w(n);
    for (int i = 0; i < n; i++) {
        w[ord[i]] = i;
    }
    
    SuffixArray sa(T);
    
    i64 ans = 0;
    std::vector<std::array<i64, 4>> qry;
    for (int x = 0; x < n; x++) {
        int p = 1;
        for (int j = 0; j < s[x].size(); j++) {
            int c = s[x][j] - 'a';
            p = trie[p][c];
            if (!p) {
                break;
            }
            if (id[p] != -1) {
                int y = id[p];
                int u = w[y];
                int l = sa.rk[st[x] + j + 1];
                int r = sa.rk[st[x]];
                if (l > r) {
                    continue;
                }
                if (y != x) {
                    qry.push_back({u, l, r, 1LL * cnt[x] * cnt[y]});
                    if (l < sa.rk[st[y]] && sa.rk[st[y]] < r) {
                        ans += 1LL * cnt[x] * cnt[y] * (cnt[y] - 1) / 2;
                    }
                    if (w[x] < u && l < sa.rk[st[x]]) {
                        ans += 1LL * cnt[x] * (cnt[x] - 1) / 2 * cnt[y];
                    }
                } else {
                    qry.push_back({u, l, r, 1LL * cnt[x] * (cnt[x] - 1) / 2});
                    ans += 1LL * cnt[x] * (cnt[x] - 1) * (cnt[x] - 2) / 6;
                }
            }
        }
    }
    
    std::vector<int> p(n);
    std::iota(p.begin(), p.end(), 0);
    std::sort(p.begin(), p.end(),
        [&](int i, int j) {
            return w[i] < w[j];
        });
    std::sort(qry.begin(), qry.end());
    
    Fenwick<int> fen(T.size());
    for (int i = 0; auto [u, l, r, v] : qry) {
        while (i < n && w[p[i]] < u) {
            int j = p[i];
            fen.add(sa.rk[st[j]], cnt[j]);
            i++;
        }
        ans += v * fen.rangeSum(l + 1, r);
    }
    
    std::cout << ans << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t;
    std::cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5656kb

input:

3
6
cbaa
cb
cb
cbaa
ba
ba
3
sdcpc
sd
cpc
1
ccpc

output:

16
0
0

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 1ms
memory: 5680kb

input:

14
1
lfpbavjsm
2
pdtlkfwn
mbd
3
dvqksg
dvqksg
uhbhpyhj
4
ombwb
ombwb
ombwb
ombwb
5
oztclz
oztclz
oztclz
oztclz
kul
6
vco
vco
vco
dtktsqtinm
vco
vco
7
tb
tb
kowbsu
ygkfphcij
tb
uvei
tb
8
vxxtxssht
abnsxbf
bydaae
bydaae
udalyvmcef
bydaae
bydaae
bydaae
9
aaze
zvyonw
qjfv
mmhkef
qjfv
qjfv
qjfv
mmhkef
qj...

output:

0
0
0
4
10
20
10
20
41
14
63
74
18
11081

result:

ok 14 lines

Test #3:

score: 0
Accepted
time: 1ms
memory: 5676kb

input:

11
10
bppzfsncq
bppzfsncq
vcqxgcehdx
bppzfsncq
bppzfsncq
muwrcvt
w
aanwhqmync
aanwhqmync
bppzfsncq
10
t
jkky
t
z
t
t
z
z
z
t
10
qidkyca
uhqubvbo
kosyvh
gsj
gsj
gsj
duo
jrro
gsj
jrro
10
lhktb
lhktb
lhktb
uohl
lhktb
r
lhktb
lhktb
wruim
lhktb
10
e
gqvdmpvxb
gqvdmpvxb
gqvdmpvxb
sttirbhz
gqvdmpvxb
zdfpm
...

output:

30
60
15
35
20
20
23
12
38
44
8047

result:

ok 11 lines

Test #4:

score: -100
Wrong Answer
time: 2ms
memory: 5848kb

input:

11
100
kalgqjh
mdszzwe
qxn
kalgqjh
hy
kalgqjh
suplvp
r
kkeoxmx
tcoise
suplvp
suplvp
y
kalgqjh
vrwniyici
jmnyrradyq
kalgqjh
kalgqjh
suplvp
rkg
xzevyk
zc
suplvp
hcupv
kalgqjh
qakyahjaoi
mum
pbg
u
ip
kalgqjh
kalgqjh
jngc
ylr
suplvp
qxn
kalgqjh
bzwodm
e
kalgqjh
kalgqjh
evmm
kbymvbccs
kalgqjh
suplvp
kalg...

output:

12478
6722
9220
6668
4934
11233
7950
5470
4525
5743
1586294

result:

wrong answer 11th lines differ - expected: '1586066', found: '1586294'