QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#356523#7901. Basic Substring Structureucup-team1198#WA 23ms4436kbC++206.4kb2024-03-17 22:03:232024-03-17 22:03:23

Judging History

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

  • [2024-03-17 22:03:23]
  • 评测
  • 测评结果:WA
  • 用时:23ms
  • 内存:4436kb
  • [2024-03-17 22:03:23]
  • 提交

answer

#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

vector<int> get_z(vector<int> A) {
    vector<int> z(A.size());
    int j = 0;
    for (int i = 1; i < A.size(); ++i) {
        if (j + z[j] > i)
            z[i] = min(j + z[j] - i, z[i - j]);
        while (i + z[i] < A.size() && A[i + z[i]] == A[z[i]])
            ++z[i];
        if (i + z[i] > j + z[j])
            j = i;
    }
    return z;
}

vector<int> get_pi(vector<int> A) {
    vector<int> pi(A.size());
    for (int i = 1; i < A.size(); ++i) {
        int j = pi[i - 1];
        while (j != -1 && A[j] != A[i])
            j = (j == 0 ? -1 : pi[j - 1]);
        pi[i] = j + 1;
    }
    return pi;
}

const int MAXN = 200200;
const int K = 20;
int lg[MAXN];
int table[MAXN][K];

void solve() {
    int n;
    cin >> n;
    vector<int> A(n);
    for (int i = 0; i < n; ++i)
        cin >> A[i];

    // suff mass
    A.emplace_back(-1);
    int N = n + 1;
    vector<int> order(N);
    vector<int> classes(N);
    vector<int> new_order(N);
    vector<int> new_classes(N);
    vector<int> cnt(N);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&A](int a, int b) {
        return A[a] < A[b];
    });
    classes[order[0]] = 0;
    for (int i = 1; i < N; ++i)
        classes[order[i]] = classes[order[i - 1]] + (A[order[i]] == A[order[i - 1]] ? 0 : 1);
    auto safe_add = [](int a, int b, int c) {
        if (a + b < c)
            return a + b;
        return a + b - c;
    };
    for (int l = 1; l < N; l *= 2) {
        fill(cnt.begin(), cnt.end(), 0);
        for (int i = 0; i < N; ++i)
            ++cnt[classes[i]];
        for (int i = 1; i < N; ++i)
            cnt[i] += cnt[i - 1];
        for (int j = N - 1; j >= 0; --j) {
            int cur = order[j] - l;
            if (cur < 0)
                cur += N;
            --cnt[classes[cur]];
            new_order[cnt[classes[cur]]] = cur;
        }
        new_classes[new_order[0]] = 0;
        for (int i = 1; i < N; ++i) {
            new_classes[new_order[i]] = new_classes[new_order[i - 1]] + 
            (make_pair(classes[new_order[i]], classes[safe_add(new_order[i], l, N)]) ==
                make_pair(classes[new_order[i - 1]], classes[safe_add(new_order[i - 1], l, N)]) ? 0 : 1);
        }
        swap(classes, new_classes);
        swap(order, new_order);
    }
    vector<int> lcp(N);
    vector<int> id(N);
    for (int i = 0; i < N; ++i)
        id[order[i]] = i;
    int tmp = 0;
    for (int i = 0; i < N; ++i) {
        if (id[i] == N - 1) {
            tmp = 0;
            continue;
        }
        int j = order[id[i] + 1];
        while (i + tmp < N && j + tmp < N && A[i + tmp] == A[j + tmp])
            ++tmp;
        lcp[id[i]] = tmp;
        tmp = max(tmp - 1, 0);
    }
    for (int i = 0; i < N; ++i)
        table[i][0] = lcp[i];
    for (int j = 1; j < K; ++j) {
        for (int i = 0; i + (1 << j) <= N; ++i)
            table[i][j] = min(table[i][j - 1], table[i + (1 << (j - 1))][j - 1]);
    }
    auto get_lcp = [&](int a, int b) {
        if (a == n || b == n) return 0;
        a = id[a];
        b = id[b];
        if (a > b)
            swap(a, b);
        if (a == b)
            return N;
        int k = lg[b - a];
        return min(table[a][k], table[b - (1 << k)][k]);
    };
    

    A.pop_back();
    vector<int> pi1 = get_pi(A);
    vector<int> p(n + 1);
    p[0] = -1;
    for (int i = 0; i < n; ++i) {
        p[i + 1] = pi1[i];
    }
    vector<int> z = get_z(A);
    int64_t f0 = n;
    for (int i = 1; i < n; ++i) {
        f0 += z[i];
    }
    vector<int64_t> val(n);
    vector<int64_t> dk(n), db(n);
    for (int i = 1; i < n; ++i) {
        dk[i + z[i] - 1] += 1;
        dk[i - 1] -= 1;
        db[i - 1] -= z[i];
        if (z[i] != 0) {
            dk[z[i] - 1] += 1;
        }
        if (z[i] > i) {
            dk[z[i] - 1] -= 1;
            dk[i - 1] += 1;
            db[i - 1] += z[i] - i;
        }
    }
    int64_t cur = 0;
    int64_t k = 0;
    for (int i = n - 1; i >= 0; --i) {
        k += dk[i];
        cur += k;
        cur += db[i];
        val[i] = cur;
    }
    /**for (int i = 0; i < n; ++i) {
        cerr << val[i] << " ";
    }
    cerr << "\n";*/

    vector<int> pp(n + 1);
    for (int i = 2; i <= n; ++i) {
        if (p[i] == p[i - 1] + 1) {
            pp[i] = pp[p[i]];
        } else {
            pp[i] = i;
        }
    }
    vector<int64_t> ans(n);
    vector<map<int, int64_t>> mp(n);
    for (int i = 2; i <= n; ++i) {
        /// doing ans[i - 1]
        int v = pp[i];
        while (v != 0) {
            int v1 = p[v - 1];
            int v2 = p[v] - 1;
            while (v1 != v2) {
                int res = get_lcp(i, v1 + 1);
                mp[v1][A[i - 1]] += res + 1;
                if (res >= i - v1 - 2) {
                    res = i - v1 - 2;
                    if (i + res < n && A[i + res] == A[v1]) {
                        ++res;
                        res += get_lcp(i + res, i);
                    }
                }
                mp[i - 1][A[v1]] += res + 1;
                v1 = p[v1];
            }
            v = pp[p[v]];
        }
    }

    mp[0].clear();
    for (int i = 1; i < n; ++i) {
        mp[0][A[i]] += get_lcp(i + 1, 1) + 1;
    }
    int64_t mx = 0;
    for (auto elem : mp[0]) {
        if (elem.first != A[0]) {
            mx = max(mx, elem.second);
        }
    }
    ans[0] = mx + n;
    for (int i = 1; i < n; ++i) {
        int64_t mx = 0;
        for (auto elem : mp[i]) {
            mx = max(mx, elem.second);
        }
        ans[i] = f0 - val[i] + mx;
        /// cerr << ans[i] << " ";
    }
    /// cerr << endl;
    int64_t out = 0;
    for (int i = 0; i < n; ++i) {
        /// cerr << ans[i] << " ";
        out += (ans[i] ^ (i + 1));
    }
    cout << out << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    lg[0] = -1;
    for (int i = 1; i < MAXN; ++i)
        lg[i] = lg[i / 2] + 1;

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

詳細信息

Test #1:

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

input:

2
4
2 1 1 2
12
1 1 4 5 1 4 1 9 1 9 8 10

output:

15
217

result:

ok 2 lines

Test #2:

score: -100
Wrong Answer
time: 23ms
memory: 4436kb

input:

10000
8
2 1 2 1 1 1 2 2
9
2 2 1 2 1 2 1 2 1
15
2 1 2 1 1 1 1 2 2 1 2 1 2 2 1
2
1 1
10
2 1 1 1 2 2 1 1 2 2
3
2 1 2
11
1 2 2 1 1 2 1 2 2 1 1
14
2 1 1 1 1 2 1 1 1 2 2 1 2 1
12
2 2 2 1 2 2 2 1 1 2 1 2
4
2 1 1 2
8
1 2 2 2 1 2 1 1
8
1 1 2 1 2 1 1 1
6
2 1 1 1 2 2
14
2 2 1 1 1 1 2 2 2 1 2 2 1 1
10
1 2 2 1 1...

output:

100
133
352
3
211
9
265
363
287
15
95
111
58
352
225
3
344
362
374
316
3
17
129
72
15
92
36
257
16
63
28
94
90
104
249
196
21
47
317
63
102
20
24
65
314
362
264
307
360
281
328
295
232
312
3
330
57
328
3
69
35
146
323
45
351
91
245
3
162
356
246
20
154
3
419
393
387
81
268
369
20
57
21
279
3
17
351
...

result:

wrong answer 1st lines differ - expected: '94', found: '100'