#878646 (C) No.2361 Many String Compare Queries

提出ソース

結果

問題	No.2361 Many String Compare Queries
ユーザー	👑 ygussany
提出日時	2023-06-07 22:39:32
言語	C (gcc 12.3.0)
結果	AC
実行時間	327 ms / 2,500 ms
コード長	6,108 bytes
コンパイル時間	1,200 ms
コンパイル使用メモリ	34,748 KB
実行使用メモリ	43,112 KB
最終ジャッジ日時	2023-09-13 11:18:28
合計ジャッジ時間	5,966 ms
ジャッジサーバーID （参考情報）	judge13 / judge15

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	4 ms 16,720 KB
testcase_01	AC	4 ms 15,256 KB
testcase_02	AC	4 ms 12,956 KB
testcase_03	AC	3 ms 17,184 KB
testcase_04	AC	4 ms 17,088 KB
testcase_05	AC	4 ms 15,176 KB
testcase_06	AC	4 ms 15,212 KB
testcase_07	AC	4 ms 16,852 KB
testcase_08	AC	324 ms 43,032 KB
testcase_09	AC	315 ms 43,084 KB
testcase_10	AC	327 ms 42,924 KB
testcase_11	AC	249 ms 43,080 KB
testcase_12	AC	282 ms 42,968 KB
testcase_13	AC	263 ms 43,112 KB
testcase_14	AC	207 ms 42,892 KB
testcase_15	AC	223 ms 43,092 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
} 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;
	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;
	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;
}

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);
	}
}

typedef struct {
	int left, right, la;
	long long sum, lb;
} lazy_seg_node;

// Initialize a lazy-update segment tree between l (>= 0) to r (k = 1 for use)
void init_node_lazy(lazy_seg_node v[], int k, int l, int r)
{
	v[k].left = l;
	v[k].right = r;
	v[k].sum = 0;
	v[k].la = 1;
	v[k].lb = 0;
	if (l < r) {
		init_node_lazy(v, k << 1, l, (l + r) / 2);
		init_node_lazy(v, (k << 1) ^ 1, (l + r) / 2 + 1, r); 
	}
}

// Update the max values from v[k] to the root
void update_max_to_root(lazy_seg_node v[], int k)
{
	int j;
	for (j = k >> 1; j > 0; k = j, j >>= 1) v[j].sum = v[k].sum + v[k^1].sum;
}

// Push the lazy update from v[k] to just below (if exists)
void push_update_below(lazy_seg_node v[], int k)
{
	int j;
	if (v[k].left == v[k].right || (v[k].la == 1 && v[k].lb == 0)) return;
	j = k << 1;
	v[j].sum = v[j].sum * v[k].la + v[k].lb * (v[j].right - v[j].left + 1);
	v[j].la *= v[k].la;
	v[j].lb = v[j].lb * v[k].la + v[k].lb;
	j ^= 1;
	v[j].sum = v[j].sum * v[k].la + v[k].lb * (v[j].right - v[j].left + 1);
	v[j].la *= v[k].la;
	v[j].lb = v[j].lb * v[k].la + v[k].lb;
	v[k].la = 1;
	v[k].lb = 0;
}

// Update the max values x between l and r to x * a + b (k = 1 for use)
void update_segment(lazy_seg_node v[], int k, int l, int r, int a, long long b)
{
	if (r < v[k].left || v[k].right < l) return;
	else if (l <= v[k].left && v[k].right <= r) {
		v[k].sum = v[k].sum * a + b * (v[k].right - v[k].left + 1);
		v[k].la *= a;
		v[k].lb = v[k].lb * a + b;
		update_max_to_root(v, k);
	} else {
		push_update_below(v, k);
		update_segment(v, k << 1, l, r, a, b);
		update_segment(v, (k << 1) ^ 1, l, r, a, b);
	}
}

// Get the sum between l and r (k = 1 for use)
long long get_sum(lazy_seg_node v[], int k, int l, int r)
{
	if (r < v[k].left || v[k].right < l) return 0;
	else if (l <= v[k].left && v[k].right <= r) return v[k].sum;
	else {
		push_update_below(v, k);
		return get_sum(v, k << 1, l, r) + get_sum(v, (k << 1) ^ 1, l, r);
	}
}

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");
	*/
	
	data d[100001];
	for (i = 1; i <= Q; i++) {
		d[i-1].key = as[L[i]];
		d[i-1].id = i;
	}
	radix_sort(d, Q);
	
	int j, k, l, r;
	long long ans[100001], sum[200001];
	seg_node v[524288];
	lazy_seg_node vv[524288];
	init_node(v, 1, 0, N - 1);
	init_node_lazy(vv, 1, 0, N - 1);
	for (i = 0; i < N; i++) update_node(v, i, lcp[i]);
	for (i = 0, sum[0] = 0; i < N; i++) sum[i+1] = sum[i] + N - sa[i];
	for (i = N - 1, j = Q - 1; i >= 0; i--) {
		while (j >= 0 && d[j].key == i) {
			l = L[d[j].id];
			r = R[d[j].id];
			k = BS_right(v, 1, 0, as[l] - 1, r - l);
			ans[d[j].id] = (long long)(r - l) * (as[l] - k) + sum[k+1];
			k = BS_left(v, 1, as[l], N - 1, r - l);
			ans[d[j].id] += (long long)(r - l) * (k - as[l]) + get_sum(vv, 1, k + 1, N - 1);
			j--;
		}
		if (i > 0) {
			k = BS_left(v, 1, i - 1, N - 1, lcp[i-1] - 1);
			update_segment(vv, 1, i, k, 0, lcp[i-1]);
		}
	}
	for (i = 1; i <= Q; i++) printf("%lld\n", ans[i]);
	fflush(stdout);
	return 0;
}

yukicoder

結果

テストケース

ソースコード