QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#339565#7901. Basic Substring StructuregoodierWA 17ms25320kbC++144.6kb2024-02-27 15:54:272024-02-27 15:54:28

Judging History

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

  • [2024-02-27 15:54:28]
  • 评测
  • 测评结果:WA
  • 用时:17ms
  • 内存:25320kb
  • [2024-02-27 15:54:27]
  • 提交

answer

#include <bits/stdc++.h>

#define x first
#define y second
#define mp make_pair

using namespace std;
const int N = 2e5 + 10, INF = 1e8;
typedef long long ll;
typedef pair<int,ll> PIL;

ll s1[N], s2[N], ans;
int s[N], slen[N], s3[N], s4[N], c[N], x[N], y[N], sa[N], rk[N], height[N], f[N][19], len[N], n;
map <int, ll> mp1[N];

void get_sa()
{
    int m = n;
    for(int i = 1; i <= m; i++) c[i] = 0;
    for(int i = 1; i <= n; i++) c[x[i] = s[i]]++;
    for(int i = 1; i <= m; i++) c[i] += c[i - 1];;
    for(int i = n; i; i--) sa[c[x[i]]--] = i;

    for(int k = 1; k <= n; k <<= 1)
    {
        int num = 0;
        for(int i = n - k + 1; i <= n; i++) y[++num] = i;
        for(int i = 1; i <= n; i++)
        {
            if(sa[i] > k)
            {
                y[++num] = sa[i] - k;
            }
        }

        for(int i = 1; i <= m; i++) c[i] = 0;
        for(int i = 1; i <= n; i++) c[x[i]]++;
        for(int i = 1; i <= m; i++) c[i] += c[i - 1];
        for(int i = n; i; i--) sa[c[x[y[i]]]--] = y[i], y[i] = 0;

        for(int i = 1; i <= n; i++) swap(x[i], y[i]); m = 0;
        for(int i = 1; i <= n; i++)
        {
            x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? m : ++m;
        }
        if(m == n) break;
    }
}

void get_height()
{
    for(int i = 1; i <= n; i++) rk[sa[i]] = i;
    for(int i = 1, k = 0; i <= n; i++)
    {
        if(rk[i] == 1) continue;
        if(k) k--;
        int j = sa[rk[i] - 1];
        while(i + k <= n && j + k <= n && s[i + k] == s[j + k]) k++;
        height[rk[i]] = k;
    }
}

void init()
{
    for(int i = 2; i <= n; i++) len[i] = len[i >> 1] + 1;
    for(int i = 1; i <= n; i++) f[i][0] = height[i];
    for(int j = 1; j <= len[n]; j++)
    {
        for(int i = 1; i + (1 << j) - 1 <= n; i++)
        {
            f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int querymn(int l, int r)
{
    if(l > r) return INF;
    int t = len[r - l + 1];
    return min(f[l][t], f[r - (1 << t) + 1][t]);
}

int lcp(int i, int j)
{
    if(i == j) return n - i + 1;
    if(i > n || j > n) return 0;
    if(rk[i] > rk[j]) swap(i, j);
    return querymn(rk[i] + 1, rk[j]);
}

int getlcp(int i, int j, int x, int y)
{
    if(i > n || j > n) return 0;
    if(i == j) return n - i + 1;
    int len = lcp(i, j);
    if(i + len - 1 >= x - 1)
    {
        len = x - i;
        if(y == s[j + len])
        {
            len++;
            len += lcp(i + len, j + len);
        }
    }
    return len;
}

void add(int x, int y)
{
    x++;
    for(; x <= n + 1; x += x & -x) c[x] += y;
}

int ask(int x)
{
    x++;
    int res = 0;
    for(; x; x -= x & -x) res += c[x];
    return res;
}

int main()
{
    //freopen("data.in", "r", stdin);
    int T;
    scanf("%d", &T);
    for(int TT = 1; TT <= T; TT++)
    {
        scanf("%d", &n);
        ans = 0;
        for(int i = 1; i <= n; i++)
        {
            scanf("%d", &s[i]);
        }
        get_sa(), get_height(), init();
        for(int i = 0; i <= n + 1; i++) c[i] = 0;
        for(int j = 2; j <= n; j++)
        {
            slen[j] = lcp(1, j);
            int l1 = 1, r1 = slen[j], l2 = j, r2 = j + slen[j] - 1;
            s2[l2] += j, s2[r2 + 1] -= j; s3[l2]++, s3[r2 + 1]--;
            if(r1 >= l2)
            {
                s1[r2 + 1] += slen[j];
            }
            else
            {
                s1[r1 + 1] += slen[j], s1[l2] -= slen[j], s1[r2 + 1] += slen[j];
            }
            add(slen[j], 1);
            if(r2 < n)
			{
                if(r1 + 1 < l2) mp1[r1 + 1][s[r2 + 1]] = mp1[r1 + 1][s[r2 + 1]] + 1 + lcp(r1 + 2, r2 + 2);
                mp1[r2 + 1][s[r1 + 1]] = mp1[r2 + 1][s[r1 + 1]] + 1 + getlcp(r1 + 2, r2 + 2, r2 + 1, s[r1 + 1]);
            }
        }

        ll sum1 = 0, sum3 = 0; int sum2 = 0;
        for(int i = 1; i <= n; i++)
        {
            add(slen[i], -1);
            sum1 += s2[i], sum2 += s3[i], sum3 += s1[i];
            ll ans1 = 0, ans2 = 0;
            ans1 = (ll)(ask(n) - ask(i - 1)) * (i - 1) + (ll)i * sum2 - sum1 + n + sum3;
            for(auto it = mp1[i].begin(); it != mp1[i].end(); it++)
            {
                ans2 = max(ans2, (*it).y);
            }
            //cout << ans1 + ans2 << " ";
            ans = ans + ((ans1 + ans2) ^ i);
        }
        //cout << endl;
        printf("%lld\n", ans);

        for(int i = 1; i <= n + 1; i++)
        {
            s1[i] = s2[i] = s3[i] = s4[i] = y[i] = 0, mp1[i].clear();
            sa[i] = x[i] = rk[i] = height[i] = 0;
        }
    }
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 24948kb

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: 17ms
memory: 25320kb

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:

94
128
347
3
211
9
265
363
278
15
95
114
58
348
225
3
335
364
377
316
3
19
122
65
15
83
36
261
11
64
28
90
85
104
252
191
21
48
303
63
102
20
24
68
316
362
266
309
354
281
326
281
231
312
3
330
54
328
3
69
32
147
322
39
338
89
242
3
165
346
245
20
155
3
404
393
392
81
269
360
20
54
21
279
3
17
351
3...

result:

wrong answer 24th lines differ - expected: '66', found: '65'