結果

問題 No.2361 Many String Compare Queries
ユーザー 👑 ygussany
提出日時 2023-06-04 21:06:48
言語 C
(gcc 13.3.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 4,192 bytes
コンパイル時間 376 ms
コンパイル使用メモリ 33,152 KB
実行使用メモリ 47,960 KB
最終ジャッジ日時 2024-06-30 20:41:26
合計ジャッジ時間 6,716 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 12 TLE * 1 -- * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <stdio.h>
typedef struct {
    unsigned long long key;
    int id;
} data;
const unsigned long long mask = 65535;
void radix_sort(data x[], int n)
{
    static data y[200001];
    static int z[200001];
    int i, j, k, l[65536], m[65536];
    for (j = 0, k = 0; j < 4; j++, k += 16) {
        for (i = 0; i <= mask; i++) m[i] = 0;
        for (i = 0; i < n; i++) {
            z[i] = (x[i].key >> k) & mask;
            m[z[i]]++;
        }
        if (m[0] == n) break;
        for (i = 0, l[0] = 0; i < mask; i++) l[i+1] = l[i] + m[i];
        for (i = 0; i < n; i++) y[l[z[i]]++] = x[i];
        for (i = 0; i < n; i++) x[i] = y[i];
    }
}
int suffix_array(char S[], int sa[])
{
    int i, j, k, l, cur, prev;
    unsigned long long m;
    data d[2][200001];
    for (i = 0; S[i] != 0; i++) {
        d[0][i].key = S[i] - 'a' + 1;
        d[0][i].id = i;
    }
    l = i;
    radix_sort(d[0], l);
    for (k = 1, cur = 1, prev = 0; k < l; k *= 2, cur ^= 1, prev ^= 1) {
        for (i = 0; i < l; i++) {
            d[cur][i].key = 0;
            d[cur][i].id = i;
        }
        for (i = 0, m = 1; i < l; i++) {
            if (i > 0 && d[prev][i].key > d[prev][i-1].key) m++;
            d[cur][d[prev][i].id].key += m * (l + 1);
            if (d[prev][i].id >= k) d[cur][d[prev][i].id - k].key += m;
        }
        radix_sort(d[cur], l);
    }
    for (i = 0; i < l; i++) sa[i] = d[prev][i].id;
    
    return l;
}
void LCP(char S[], int sa[], int as[], int lcp[])
{
    int i, j, k, l;
    for (i = 0; S[i] != 0; i++) as[sa[i]] = i;
    l = i;
    
    for (i = 0, k = 0; i < l; i++) {
        if (k > 0) k--;
        if (as[i] == 0) continue;
        else j = as[i] - 1;
        for (; i + k < l && sa[j] + k < l; k++) if (S[i+k] != S[sa[j]+k]) break;
        lcp[j] = k;
    }
}
const int sup = 1 << 20;
int leaf[200001];
typedef struct {
    int left, right, min;
    long long sum;
} seg_node;
void init_node(seg_node v[], int k, int l, int r)
{
    v[k].left = l;
    v[k].right = r;
    v[k].min = sup;
    v[k].sum = (long long)sup * (r - l + 1);
    if (l < r) {
        init_node(v, k << 1, l, (l + r) / 2);
        init_node(v, (k << 1) ^ 1, (l + r) / 2 + 1, r);
    } else leaf[l] = k;
}
void update_node(seg_node v[], int k, int x)
{
    int i, j = leaf[k];
    v[j].min = x;
    v[j].sum = x;
    for (i = j >> 1; i > 0; j = i, i >>= 1) {
        v[i].min = (v[j].min < v[j^1].min)? v[j].min: v[j^1].min;
        v[i].sum = v[j].sum + v[j^1].sum;
    }
}
 
long long get_sum(seg_node v[], int k, int l, int r)
{
    if (v[k].right < l || v[k].left > r) return 0;
    else if (v[k].left >= l && v[k].right <= r) return v[k].sum;
    else return get_sum(v, k << 1, l, r) + get_sum(v, (k << 1) ^ 1, l, r);
}
int BS_left(seg_node v[], int k, int l, int r, int x)
{
    int tmp;
    if (v[k].min > x || v[k].right < l || v[k].left > r) return r + 1;
    else if (v[k].left == v[k].right) return v[k].left;
    else {
        tmp = BS_left(v, k << 1, l, r, x);
        if (tmp <= r) return tmp;
        else return BS_left(v, (k << 1) ^ 1, l, r, x);
    }
}
int BS_right(seg_node v[], int k, int l, int r, int x)
{
    int tmp;
    if (v[k].min > x || v[k].right < l || v[k].left > r) return l - 1;
    else if (v[k].left == v[k].right) return v[k].left;
    else {
        tmp = BS_right(v, (k << 1) ^ 1, l, r, x);
        if (tmp >= l) return tmp;
        else return BS_right(v, k << 1, l, r, x);
    }
}
int main()
{
    int i, N, Q, L[100001], R[100001];
    char S[200001];
    scanf("%d %d", &N, &Q);
    scanf("%s", S);
    for (i = 1; i <= Q; i++) {
        scanf("%d %d", &(L[i]), &(R[i]));
        L[i]--;
        R[i]--;
    }
    
    int sa[200001], as[200001], lcp[200001];
    suffix_array(S, sa);
    LCP(S, sa, as, lcp);
    /*
    printf("%s\n", S);
    for (i = 0; i < N; i++) printf("%d ", sa[i]);
    printf("\n");
    for (i = 0; i < N; i++) printf("%d ", as[i]);
    printf("\n");
    for (i = 0; i < N; i++) printf("%d ", lcp[i]);
    printf("\n");
    */
    
    int j, k, l;
    long long ans;
    seg_node v[524288], vv[524288];
    init_node(v, 1, 0, N - 1);
    init_node(vv, 1, 0, N - 1);
    for (i = 0; i < N; i++) update_node(v, i, lcp[i]);
    for (i = 0; i < N; i++) update_node(vv, i, N - sa[i]);
    for (i = 1; i <= Q; i++) {
        ans = 0;
        k = as[L[i]];
        j = BS_right(v, 1, 0, k - 1, R[i] - L[i]);
        ans += (long long)(R[i] - L[i]) * (k - j) + get_sum(vv, 1, 0, j);
        // printf("%d %d %lld\n", j, k, ans);
        for (l = R[i] - L[i]; l > 0; ) {
            j = BS_left(v, 1, k, N - 1, l - 1);
            ans += (long long)l * (j - k);
            l = lcp[j];
            k = j;
        }
        printf("%lld\n", ans);
    }
    fflush(stdout);
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0