QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#720311 | #9406. Triangle | DaiRuiChen007 | WA | 2ms | 5848kb | C++17 | 7.4kb | 2024-11-07 11:47:55 | 2024-11-07 11:47:57 |
Judging History
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'