QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#382388#7901. Basic Substring StructureEBeasonWA 38ms84088kbC++207.4kb2024-04-08 13:23:572024-04-08 13:23:58

Judging History

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

  • [2024-04-08 13:23:58]
  • 评测
  • 测评结果:WA
  • 用时:38ms
  • 内存:84088kb
  • [2024-04-08 13:23:57]
  • 提交

answer

#pragma GCC optimize(1, 2, 3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
// #define int ll
#define ls p << 1
#define rs p << 1 | 1
#define lowbit(x) ((x) & (-x))
#define endl '\n'
#define ld long double
#define MULTI_CASES
const int MaxN = 1e6 + 100;
const int INF = 1e9;
int T, N, M, K;
int ans[MaxN];
vector<int> a;
struct SA {
	int sa[MaxN], rk[MaxN], oldrk[MaxN << 1], id[MaxN], key1[MaxN], cnt[MaxN], height[MaxN];
	int st[MaxN][25], logn[MaxN];
	int n;
	vector<int> s;
	void init(int _n) {
		n = _n;
		for (int i = 0; i <= n + 1; i++) {
			sa[i] = 0;
			rk[i] = 0;
			oldrk[i] = 0;
			cnt[i] = 0;
			key1[i] = 0;
			id[i] = 0;
			height[i] = 0;
		}
		getsa();
		getheight();
	}
	bool cmp(int x, int y, int w) {
		return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
	}
	inline void getsa() {
		int i, m = n + 1, p, w;
		// sa[i]表示后缀排序第i小的编号
		// rk[i]表示后缀i的排名
		for (i = 1; i <= n; ++i) ++cnt[rk[i] = s[i]];
		for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
		for (i = n; i >= 1; --i) sa[cnt[rk[i]]--] = i;

		for (w = 1;; w <<= 1, m = p) { // m=p 就是优化计数排序值域
			for (p = 0, i = n; i > n - w; --i) id[++p] = i;
			for (i = 1; i <= n; ++i) 
				if (sa[i] > w) id[++p] = sa[i] - w;
			memset(cnt, 0, m * sizeof(int));
			for (i = 1; i <= n; ++i) ++cnt[key1[i] = rk[id[i]]];
			// 注意这里px[i] != i,因为rk没有更新,是上一轮的排名数组

			for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
			for (i = n; i >= 1; --i) sa[cnt[key1[i]]--] = id[i];
			memcpy(oldrk + 1, rk + 1, n * sizeof(int));
			for (p = 0, i = 1; i <= n; ++i) rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
			if (p == n) break;
		}
	}
	inline void getheight(){
		// height[i]=lcp(sa[i],sa[i-1])
		int i, k;
		for (i = 1, k = 0; i <= n; ++i) {
			if (rk[i] == 0) continue;
			if (k) --k;
			while (i + k <= n && s[i + k] == s[sa[rk[i] - 1] + k]) ++k;
			height[rk[i]] = k;
		}
	}
	inline void pre() {
		logn[0] = -1;
		int LogN = log2(n) + 1;
		for (int i = 1; i <= n; i++) logn[i] = logn[i / 2] + 1;
		for (int i = 1; i <= n; i++) st[i][0] = height[i];
		for (int j = 1; j <= LogN; j++) {
			int pj = 1 << (j - 1);
			for (int i = 1; i <= n; i++) {
				if (i + pj <= n)
					st[i][j] = min(st[i][j - 1], st[i + pj][j - 1]);
				else
					st[i][j] = st[i][j - 1];
			}
		}
	}
	inline int lcp(int l, int r) {
		if (l == r) return n - l + 1;
		l = rk[l];
		r = rk[r];
		if (l > r) swap(l, r);
		l++;
		int lp = r - l + 1;
		int n = 1 << logn[lp];
		return min(st[l][logn[lp]], st[r - n + 1][logn[lp]]);
	}
} SA;
struct TT {
	int a[MaxN];
	struct Point {
		ll sum, lan;
	} tree[MaxN << 2], ts;
	void js(int p, int x, int y, int z) {
		tree[p].sum += (y - x + 1) * z;
		tree[p].lan += z;
	}
	void pushdown(int p,int l, int r) {
		if (tree[p].lan) {
			int mid = (l + r) >> 1;
			js(ls, l, mid, tree[p].lan);
			js(rs, mid + 1, r, tree[p].lan);
		}
	}
	inline Point pushup(Point L, Point R) {
		Point now = Point();
		now.sum = L.sum + R.sum;
		return now;
	}
	void build(int p, int l, int r) {
		if (l == r) {
			tree[p].sum = a[l];
			tree[p].lan = 0;
			return;
		}
		pushdown(p, l, r);
		int mid = (l + r) >> 1;
		build(ls, l, mid);
		build(rs, mid + 1, r);
		tree[p] = pushup(tree[ls], tree[rs]);
	}
	void change(int p, int l, int r, int x, int y, int z) {
		if (x > y || l > N) return;
		if (l >= x && r <= y) {
			js(p, l, r, z);
			return;
		}
		pushdown(p, l, r);
		int mid = (l + r) >> 1;
		if (mid >= x) change(ls, l, mid, x, y, z);
		if (mid < y) change(rs, mid + 1, r ,x ,y, z);
		tree[p] = pushup(tree[ls], tree[rs]);
	}
	Point query(int p, int l, int r, int x, int y) {
		if (l >= x && r <= y) {
			return tree[p];
		}
		pushdown(p, l, r);
		int mid = (l + r) >> 1;
		if (mid >= x && mid < y) {
			return pushup(query(ls, l, mid, x, y), query(rs, mid + 1, r, x, y));
		}
		if (mid >= x) return query(ls, l, mid, x, y);
		if (mid < y) return query(rs, mid + 1, r, x, y);
		return Point();
	}
} TT;
ll g[MaxN], b[MaxN];
void updata(int l, int r, int k, int d) {
// 	cerr << l << ' ';
// 	cerr << r << ' ';
// 	cerr << k << ' ';
// 	cerr << d << endl;
	if (l > r) return;
	TT.change(1, 1, N, l + 1, r, 1);
	TT.change(1, 1, N, l, l, k);
	TT.change(1, 1, N, r + 1, r + 1, -k - d * (r - l));
}
struct my_hash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }

  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
};
unordered_map<int ,ll, my_hash> mp[MaxN];
int js(int x, int y) {
	// if (a[x] == a[1]) return 0;
	int t = SA.lcp(x + 1, y + 1) + 1;
	if (x + t >= y) {
		int len = y - x;
		t = len;
		if (x <= N && y + len <= N && a[x] == a[y + len]) {
			t += SA.lcp(x + len + 1, y + len + 1) + 1;
		}
		return t;
	} else { 
		return t;
	}
}
inline void Solve() {
	cin >> N;
	a.assign(N + 1, 0);
	for (int i = 1; i <= N; i++) {
		cin >> a[i];
		mp[i].clear();
	}
	SA.s = a;
	SA.init(N);
	SA.pre();
	for (int i = 1; i <= N; i++) {
		g[i] = SA.lcp(1, i);
		// cerr << g[i] << ' ';
	}
	int sum = 0;
	for (int i = 1; i <= N; i++) {
		sum += g[i];
		TT.a[i] = 0;
	}

	TT.a[1] = sum;
	TT.build(1, 1, N);
	for (int i = 1; i <= N; i++) {
		int l = 1, r = g[i];
		int x = i, y = x + g[i] - 1;
		if (i == 1) continue;
		if (r < x) {
			updata(l, r, -g[i], 1);
			updata(x, y, -g[i], 1);
		} else if (x <= r) {
			updata(l, x - 1, -g[i], 1);
			updata(x, y, -g[i], 1);
		}
		// for (int i = 1; i <= N; i++) {
		// 	b[i] = b[i - 1];
		// 	b[i] += TT.query(1, 1, N, i, i).sum;
		// 	cerr << b[i] << ' ';
		// } cerr << endl;
	}
	// updata(1, 2, -2, 1);
	for (int i = 1; i <= N; i++) {
		b[i] = b[i - 1];
		b[i] += TT.query(1, 1, N, i, i).sum;
		// cerr << b[i] << ' ';
	}
	// cerr << endl;
	for (int i = 1; i <= N; i++) {
		int x = g[i] + 1, y = i + g[i];
		if (y <= N && x <= N) {
			if (x >= i) {
				
			} else {
				mp[x][a[y]] += SA.lcp(x + 1, y + 1) + 1;
			}
			
			mp[y][a[x]] += js(x, y);
			// cerr << x << ' ';
			// cerr << a[y] << ' ';
			// cerr << y << ' ';
			// cerr << a[x] << endl;
		}

	}
	ll jg = 0;
	for (int i = 1; i <= N; i++) {
		ans[i] = b[i];
		// int id = 0;
		for (auto it : mp[i]) {
			int ts = b[i] + it.second;
			if (it.first == a[i]) continue;
			if (ts > ans[i]) {
				ans[i] = ts;
				// id = it.first;
			}
			ans[i] = max(ans[i], ts);
			// cerr << i << ' ';
			// cerr << it.first << ' ';
			// cerr << it.second << endl;
		}
		jg += (1ll * ans[i]) ^ i;
		// cerr << id << ' ';
	}
	// cerr << endl;
	// for (int i = 1; i <= N; i++) {
	// 	cerr << b[i] << ' ';
	// } cerr << endl;
	// for (int i = 1; i <= N; i++) {
	// 	cerr << ans[i] << ' '; 
	// }
	// cerr << endl;
	cout << jg << endl;
}
signed main() {
	// ld be, ed;
	// be = clock();
	// freopen("1.in", "r", stdin);
	// freopen("1.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	srand(time(NULL));
#ifdef MULTI_CASES
	int T;
	cin >> T;
	while (T--)
#endif
		Solve();
	// ed = clock();
	// cerr << (ed - be) / CLOCKS_PER_SEC << endl;
}

詳細信息

Test #1:

score: 100
Accepted
time: 8ms
memory: 83540kb

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: 38ms
memory: 84088kb

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
560
4
218
12
294
313
269
18
98
148
77
388
202
3
484
392
350
463
8
19
125
77
22
103
59
268
11
63
50
161
81
116
289
207
29
64
367
74
126
21
24
68
343
470
406
465
337
309
530
472
237
321
3
369
55
299
3
61
49
147
385
49
465
127
312
4
165
549
247
20
171
6
503
602
390
104
266
352
20
57
21
432
3
28
...

result:

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