QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#807694#7901. Basic Substring Structurejuan_123WA 38ms24520kbC++143.9kb2024-12-10 10:28:342024-12-10 10:28:34

Judging History

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

  • [2024-12-10 10:28:34]
  • 评测
  • 测评结果:WA
  • 用时:38ms
  • 内存:24520kb
  • [2024-12-10 10:28:34]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define double long double
#define lowbit(x) (x&(-x))
#define int long long
#define ull unsigned long long
const ull base = 998244353;
int p[200005];
int n;
int a[200005]; 
int k[200005],b[200005],c[200005];
int ans[200005];
//答案表示为 ki+b 
int r[200005],pos[200005],rr[200005];
ull pre[200005],pw[200005];
vector<pair<int,int> >s[200005];
//从 i 位置开始匹配能到哪里
//第一个不一样的位置
//不考虑第一个不一样的位置后能匹配到哪里 
ull calc(int l,int r,int pos =0){
	if(l>r)return 0;
	if(!pos)return pre[r]-pre[l-1]*pw[r-l+1];
	if(l<=pos and pos<=r){
		ull x1 = calc(l,pos-1),x2 = calc(pos+1,r);
		ull x = (x1*base+a[pos])*pw[r-pos]+x2;
		return x;
	}
	return calc(l,r);
}
void add(int l,int r,int K,int C,int id){
	if(l>r)return;
//	if(l<=3 and r>=3)cout << l << " " << r << " " << id << " " << K << " " << C << endl; 
	k[l]+=K,k[r+1]-=K;
	c[l]+=C,c[r+1]-=C;
}
int query(int pos,int c,int i){
	int l  =i,r = n;
//	cout << " " << pos << " " << c << " " << i << endl;
	swap(a[pos],c);
//	cout << a[pos] << endl;
	while(l<r){
		int mid = l+r+1>>1;
		int len = mid-i+1;
//		cout << len << " " << calc(1,len,pos) << " " << calc(i,mid,pos) << endl;
		if(calc(1,len,pos) == calc(i,mid,pos))l = mid;
		else r = mid-1;
	}
	swap(a[pos],c);
	return l;
}
void solve(){
	cin >> n;
	for(int i = 1;i<=n;i++)p[i] = i;random_shuffle(p+1,p+1+n);
	for(int i = 1;i<=n;i++)cin >> a[i];
	for(int i = 1;i<=n;i++)a[i] = p[a[i]];
	for(int i =0;i<=n+1;i++)s[i].clear(),k[i]=b[i]=c[i]=0; 
	for(int i = 1;i<=n;i++)pre[i] = pre[i-1]*base+a[i];
	r[1]=n,pos[1]=n+1,rr[1]=n;
	for(int i = 2;i<=n;i++){
		int* xx = r;
		int l = 0,r = n-i+1;
		while(l<r){
			int mid = l+r+1>>1;
			if(calc(1,mid) == calc(i,i+mid-1)){
				l = mid;
			}else r = mid-1;
		}
		xx[i] = i+l-1;
	//	cout << " " << r;
		pos[i] = i+l;
		if(pos[i]>=n){
			rr[i] = n;
			continue;
		}
//		cout << "  " << pos[i] << " " << a[l+1] << endl;
		rr[i] = query(pos[i],a[l+1],i);
	}
//	cout << endl;
//	for(int i = 1;i<=n;i++)cout << r[i] << " ";cout << endl;
	c[1]=n;
//	for(int i = 1;i<=n;i++)cout << "  " << r[i] << " " << pos[i] << " " << rr[i] << endl;
	for(int i = 2;i<=n;i++){
		//如果在前面改则原串有可能发生变化
		// [L,R]
		// 在 [1,R-L+1] 改一个 
		// 如果 R-L+1>=R 则后面的串也会被改
		// 对 1 特判
		// 然后就是在 [1,min(L-1,R-L+1)] 改一个,贡献是 i-1 
		// 在 [R-L+2,L-1] 改一个,贡献是 R-L+1
		// 如果在 R-L+2 改了一个,答案会增加当且仅当 R-L+2 < L
		// 如果把 a_{R-L+2} 变成 a_{R+1} 答案增大 rri-ri 
		// 在 [L,R] 改一个,贡献是 i-L+1
		// 在 [R+1,n] 改一个贡献是 R-L+1 
		// 如果在 R+1 改了一个
		// 如果把 a_{R+1} 变成 a_{R-L+2} 答案增大 rri-ri
		int L = i,R = r[i];
		add(1,min(L-1,R-L+1),1,-1,i);
		add(R-L+2,L-1,0,R-L+1,i);
		if(R-L+2<=L-1)s[R-L+2].push_back({a[R+1],query(R-L+2,a[R+1],i)-r[i]});
		add(L,R,1,-L,i);
		add(R+1,n,0,R-L+1,i);
		s[R+1].push_back({a[R-L+2],query(R+1,a[R-L+2],i)-r[i]});
	}
	for(int i = 1;i<=n;i++){
		int mx =0;
		sort(s[i].begin(),s[i].end());
		int lst = 0;
		ans[i] = 0;
		for(auto x:s[i]){
			if(lst!=x.first){
				mx = x.second,lst = x.first;
			}else mx += x.second;
			ans[i] = max(ans[i],mx);
		}
		k[i]+=k[i-1],c[i]+=c[i-1];
		for(auto x:s[i]){
	//		cout << x.first << " " << x.second << endl;
		}
	//	cout << " " << ans[i] << " " << k[i] << " " << c[i] << endl;
		ans[i] += k[i]*i+c[i];
	}
	int res = 0;
	for(int i = 1;i<=n;i++)res+=ans[i]^i;
//	for(int i = 1;i<=n;i++)cout << " " << ans[i];cout << endl;
	cout << res << endl; 
}
signed main(){
	srand(time(0));
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	pw[0] = 1;for(int i = 1;i<=200000;i++)pw[i]=pw[i-1]*base;
	int t;cin >> t;
	while(t--)solve();
	return 0;
}/*

1
15
1 1 1 1 1 2 1 1 1 1 1 1 1 1 1

2
4
2 1 1 2
1
12
1 1 4 5 1 4 1 9 1 9 8 10
*/

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 24016kb

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: 0
Accepted
time: 18ms
memory: 24520kb

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
347
3
211
9
265
363
278
15
95
114
58
348
225
3
335
364
377
316
3
19
122
66
15
83
36
258
11
63
28
90
85
103
252
191
21
48
303
63
102
20
24
68
316
362
266
309
355
281
326
281
231
312
3
330
54
328
3
69
32
147
322
39
338
90
242
3
165
346
245
20
155
3
404
393
392
81
269
360
20
54
21
279
3
17
351
3...

result:

ok 10000 lines

Test #3:

score: -100
Wrong Answer
time: 38ms
memory: 23644kb

input:

10000
17
1 2 2 2 2 2 2 2 1 1 2 2 1 2 1 2 2
17
2 1 1 1 1 2 2 2 1 1 1 1 1 2 2 2 2
13
2 2 2 1 2 2 2 2 1 1 1 1 1
12
2 2 1 2 1 2 2 1 1 1 1 1
13
2 2 2 1 1 1 1 2 2 2 2 1 1
20
2 1 2 2 1 2 2 2 2 2 2 1 2 2 2 2 1 2 1 1
13
1 2 1 2 2 2 1 2 1 2 1 1 1
20
2 1 1 2 2 1 2 2 1 1 2 1 2 2 2 2 2 1 2 2
12
2 1 2 1 1 2 2 1 2...

output:

392
434
308
252
302
895
343
846
282
249
717
194
252
350
230
427
439
279
340
384
380
292
218
312
271
810
275
211
460
388
365
342
773
203
238
857
720
497
514
443
618
777
372
242
337
232
324
837
289
480
366
681
358
281
320
529
451
309
250
326
315
744
307
841
133
214
411
788
332
365
488
157
760
278
421
...

result:

wrong answer 8th lines differ - expected: '867', found: '846'