QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#698883#7901. Basic Substring StructureDeltaxWA 23ms118604kbC++144.5kb2024-11-01 22:54:062024-11-01 22:54:06

Judging History

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

  • [2024-11-01 22:54:06]
  • 评测
  • 测评结果:WA
  • 用时:23ms
  • 内存:118604kb
  • [2024-11-01 22:54:06]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mkp make_pair
#define pb push_back
typedef pair <int, int> pii;
typedef long long LL;

inline int read() {
	int x = 0, f = 0;
	char c = getchar();
	while (!isdigit(c)) {if (c == '-') f = 1; c = getchar();}
	while (isdigit(c)) x = (x << 1) + (x << 3) + (c & 15), c = getchar();
	return f? -x : x;
}

const int MAXN = 2e5;
namespace ST {
	const int MAXST = MAXN*2;
	template <class T1>
		struct ST {
			T1 mn[21][MAXST];
			void build(T1 *a, int n) {
				for (int i = 1; i <= n; ++i) mn[0][i] = a[i - 1];
				for (int j = 1; j <= 20; ++j)
					for (int i = 1; i + (1 << j - 1) <= n; ++i)
						mn[j][i] = min(mn[j - 1][i], mn[j - 1][i + (1 << j - 1)]);
			}
			T1 query(int l, int r) {
				int k = 31 - __builtin_clz(r - l + 1);
				return min(mn[k][l], mn[k][r - (1 << k) + 1]);
			}
		};
}

namespace SAM {
	const int MAXS = MAXN*2;
	struct SAM {
		vector <int> G[MAXS];
	//	int ch[MAXS][28];
		map <int, int> ch[MAXS];
		int len[MAXS], siz[MAXS], fa[MAXS], last, tot;
		int extend(int c) {
			int np = ++tot, p = last; last = np;
			len[np] = len[p] + 1; siz[np] = 1;
			for (; p && ch[p].find(c) == ch[p].end(); p = fa[p]) ch[p][c] = np;
			if (ch[p].find(c) == ch[p].end()) {
				ch[p][c] = np;
				fa[np] = p;
				return np;
			}
			int q = ch[p][c];
			if (len[q] > len[p] + 1) {
				int nq = ++tot; len[nq] = len[p] + 1; fa[nq] = fa[q];
				//for (int i = 0; i < 26; ++i) ch[nq][i] = ch[q][i];
				ch[nq] = ch[q];
				fa[np] = fa[q] = nq;
				for (; ch[p].find(c) != ch[p].end() && ch[p][c] == q; p = fa[p]) ch[p][c] = nq;
			}
			else fa[np] = q;
			return np;
		}

		ST :: ST<pii> st;
		int dfn[MAXS], tt;
		void dfs(int x, int dep) {
			dfn[x] = ++tt;
			for (auto v : G[x]) {
				dfs(v, dep + 1);
				siz[x] += siz[v];
			}
		}
		pii a_[MAXS];
		void build() {
			for (int i = 1; i <= tot; ++i)
				G[fa[i]].pb(i);
			dfs(0, 0);
			for (int i = 0; i <= tot; ++i) a_[dfn[i]] = mkp(dfn[fa[i]], fa[i]);
			st.build(a_ + 1, tot + 1);
		}
		void clear() {
	//		st.clear();
			for (int i = 0; i <= tot + 1; ++i) {
				//memset(ch[i], 0, sizeof(ch[i]));
				ch[i].clear();
				len[i] = siz[i] = fa[i] = 0;
				G[i].clear();
			}
			tt = last = tot = 0;
		}
		int LCA(int x, int y) {
			if (x == y) return x;
			if (dfn[x] > dfn[y]) swap(x, y);
			return st.query(dfn[x] + 1, dfn[y]).se;
		}
		inline int LCP(int x, int y) {return len[LCA(x, y)];} //front
	};
}
SAM :: SAM s1;
int pos[MAXN + 10], s[MAXN + 10], len[MAXN + 10];

unordered_map <int, int> mp;
map <int, LL> exc[MAXN + 10];
vector <int> vec[MAXN + 10];

LL c1[MAXN + 10], v1[MAXN + 10], res[MAXN + 10], ans[MAXN + 10];
int main() {
	int T = read();
	while (T--) {
		int n = read();
		for (int i = 1; i <= n; ++i) s[i] = read();
		for (int i = n; i >= 1; --i) {
			pos[i] = s1.extend(s[i]);
		}
		s1.build();
		LL ans = 0, sum = 0, cnt = 0;
		for (int i = 2; i <= n; ++i) {
			len[i] = s1.LCP(pos[1], pos[i]);
			ans += len[i];

			c1[1]++;
			c1[min(len[i] + 1, i)]--;
			res[1] -= len[i]; 
			res[min(len[i] + 1, i)] += len[i];

			c1[i]++;
			c1[i + len[i]]--;
			v1[i] -= i - 1;
			v1[i + len[i]] += i - 1;
			res[i] -= len[i];
			res[len[i] + i] += len[i];
			//vec[i + len[i]].pb(i);
			int l1 = s1.LCP(pos[i + len[i] + 1], pos[1 + len[i] + 1]) + 1;
		//	cerr << l1 << " ";
			if (1 + len[i] < i)
				exc[1 + len[i]][s[i + len[i]]] += l1;
			if (l1 + len[i] >= i + len[i]) {
				//l1 + len[i] ->  i + len[i];
				l1 = i - 1;
			}
			else {
				int tmp = s[i + len[i]]; s[i + len[i]] = s[1 + len[i]];
				if (l1 + len[i] == i + len[i] - 1 && s[1 + l1 + len[i]] == s[i + len[i] + l1]) {
					l1 += 1 + s1.LCP(pos[l1 + len[i] + 2], pos[i + len[i] + l1 + 1]);
				}
				s[i + len[i]] = tmp;
			}
	//		cerr << l1 << endl;
			exc[i + len[i]][s[1 + len[i]]] += l1;
/*
			if (i + len[i] == 5) {
				cerr << "sss";
			}*/
			/*
			if (i + len[i] == 4 && s[1 + len[i]] == 1) {
				cout << i << " " << l1 << endl;
			}*/
		}
	//	cerr << ans << endl;
		LL rnm = 0; ans += n;
		for (int i = 1; i <= n; ++i) {
			sum += res[i];
			cnt += c1[i];
			sum += v1[i];
			LL mx = 0;
			for (auto v : exc[i])
				mx = max(mx, v.se);
			::ans[i] = mx + ans + sum + cnt * (i - 1);
	//		cerr << ::ans[i] << " ";
			rnm += ::ans[i] ^ i;
		}
	//	cerr << endl;
	//	cerr << endl;
		printf("%lld\n", rnm);
		for (int i = 1; i <= n + 1; ++i) {
			exc[i].clear();
			c1[i] = v1[i] = res[i] = 0;
		}
		s1.clear();
	}
	return 0;
}


詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 118340kb

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: 118604kb

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
354
3
209
9
262
359
278
21
93
112
58
348
233
3
335
364
377
316
3
19
132
64
13
94
36
261
10
77
34
91
85
101
254
191
21
48
303
64
100
20
24
68
316
362
294
313
353
281
328
281
231
312
3
334
59
326
6
73
32
147
334
40
345
105
242
3
165
346
245
20
177
3
404
393
392
82
273
360
20
59
21
273
6
18
351
...

result:

wrong answer 3rd lines differ - expected: '347', found: '354'