結果

問題 No.2361 Many String Compare Queries
ユーザー ygussanyygussany
提出日時 2023-06-04 21:14:31
言語 C
(gcc 12.3.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 4,188 bytes
コンパイル時間 216 ms
コンパイル使用メモリ 32,768 KB
実行使用メモリ 48,032 KB
最終ジャッジ日時 2024-06-30 20:41:32
合計ジャッジ時間 6,586 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
15,668 KB
testcase_01 AC 3 ms
8,600 KB
testcase_02 AC 3 ms
6,940 KB
testcase_03 AC 4 ms
10,644 KB
testcase_04 AC 4 ms
12,676 KB
testcase_05 AC 4 ms
12,680 KB
testcase_06 AC 3 ms
10,632 KB
testcase_07 AC 4 ms
10,628 KB
testcase_08 AC 416 ms
41,204 KB
testcase_09 AC 519 ms
41,196 KB
testcase_10 AC 445 ms
41,136 KB
testcase_11 AC 139 ms
41,136 KB
testcase_12 AC 186 ms
41,148 KB
testcase_13 AC 184 ms
41,192 KB
testcase_14 TLE -
testcase_15 -- -
権限があれば一括ダウンロードができます

ソースコード

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';
		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;
}
0