QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#298219#7901. Basic Substring Structureucup-team266#WA 22ms8196kbC++144.4kb2024-01-05 20:32:252024-01-05 20:32:26

Judging History

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

  • [2024-01-05 20:32:26]
  • 评测
  • 测评结果:WA
  • 用时:22ms
  • 内存:8196kb
  • [2024-01-05 20:32:25]
  • 提交

answer

/*
Things to notice:
1. do not calculate useless values
2. do not use similar names
 
Things to check:
1. submit the correct file
2. time (it is log^2 or log)
3. memory
4. prove your naive thoughts 
5. long long
6. corner case like n=0,1,inf or n=m
7. check if there is a mistake in the ds or other tools you use
8. fileio in some oi-contest

9. module on time 
10. the number of a same divisor in a math problem
11. multi-information and queries for dp and ds problems
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pii pair<long long,long long>
#define mp make_pair
#define pb push_back
int n,s[200005];
struct BIT
{
	int t[200005];
	void init()
	{
		for(int i=1;i<=n;i++) t[i]=0; 
	}
int lowbit(int x)
{
	return x&(-x);	
} 
void update(int x,int d)
{
	for(int i=x;i<=n;i+=lowbit(i)) t[i]+=d;
}
int query(int x)
{
	int res=0;
	for(int i=x;i>=1;i-=lowbit(i)) res+=t[i];
	return res;
}
}bt,bt2; 
int upd_pos,upd_val;
struct Hashing
{
	int mod,bse;
	int pw[200005];
	int H1[200005];
	void init(int M,int B)
	{
		mod=M,bse=B;
		pw[0]=1;
		for(int i=1;i<=n;i++) pw[i]=1LL*pw[i-1]*bse%mod;
		for(int i=1;i<=n;i++) H1[i]=1LL*bse*H1[i-1]%mod+(s[i]),H1[i]%=mod;
	}
	int query(int l,int r)
	{
		int re=(H1[r]-1LL*H1[l-1]*pw[r-l+1]%mod+mod)%mod;
		if(l<=upd_pos&&upd_pos<=r) 
		{
			int wei=r-upd_pos;
			re=(re-pw[wei]*s[upd_pos]%mod+mod)%mod;
			re=(re+pw[wei]*upd_val)%mod;
		}
		return re;
	}
}h1,h2;
int chkequ(int l1,int r1,int l2,int r2)
{
	if(h1.query(l1,r1)!=h1.query(l2,r2)) return 0;
	return h2.query(l1,r1)==h2.query(l2,r2);
}
int ans[200005];
vector <pii > buc[200005]; 
void solve()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>s[i],ans[i]=0,buc[i].clear();
	h1.init(998244853,19260817);
	h2.init(1e9+7,1919810);
	bt.init();
	for(int i=2;i<=n;i++)
	{
		int l=1,r=n-i+1,res=0;
		upd_pos=0;
		while(l<=r)
		{
			int mid=(l+r)>>1;
			if(chkequ(1,mid,i,i+mid-1)) res=mid,l=mid+1;
			else r=mid-1;
		}
//		cout<<"z: "<<i<<" "<<res<<"\n";
		// case 1: outsize [1,z[i]] and [i,i+z[i]-1]
		if(res+1<=i-1) bt.update(res+1,res),bt.update(i,-res);
//		cout<<"... "<<bt.query(2)<<"\n";
		if(i+res<=n) bt.update(i+res,res); 
		// case 2: i+z[i] or z[i]+1
		if(res<n-i+1)
		{
			int j=i+res+1;
			l=1,r=n-j+1;
			int res2=0;
			upd_pos=j-1,upd_val=s[res+1];
			while(l<=r)
			{
				int mid=(l+r)>>1;
				if(chkequ(res+2,res+2+mid-1,j,j+mid-1)) res2=mid,l=mid+1;
				else r=mid-1;
			}
//			cout<<i<<" -> "<<j-1<<"\n";
			buc[j-1].pb(mp(s[res+1],res2+1));
			if(res+1>=i) continue;
			upd_pos=res+1,upd_val=s[i+res];
			l=1,r=n-j+1;
			res2=0;
			while(l<=r)
			{
				int mid=(l+r)>>1;
				if(chkequ(res+2,res+2+mid-1,j,j+mid-1)) res2=mid,l=mid+1;
				else r=mid-1;
			}
//			cout<<i<<" -> "<<res+1<<"\n";
			buc[res+1].pb(mp(s[i+res],res2+1));
		}
		
	}
	for(int i=1;i<=n;i++) ans[i]+=bt.query(i);//,cout<<ans[i]<<" ";
//	cout<<"\n";
	bt.init(),bt2.init();
	// case 3: in [i,i+z[i]-1]
	for(int i=2;i<=n;i++)
	{
		int l=1,r=n-i+1,res=0;
		while(l<=r)
		{
			int mid=(l+r)>>1;
			if(chkequ(1,mid,i,i+mid-1)) res=mid,l=mid+1;
			else r=mid-1;
		}
		if(res)
		{
			bt.update(i,1),bt.update(i+res,-1);
			bt2.update(i,i),bt2.update(i+res,-i); 
		}
	}
	for(int i=1;i<=n;i++) ans[i]+=i*bt.query(i)-bt2.query(i);
	// case 4: in[1,z[i]]
	bt.init(),bt2.init();
	for(int i=2;i<=n;i++)
	{
		int l=1,r=n-i+1,res=0;
		upd_pos=0;
		while(l<=r)
		{
			int mid=(l+r)>>1;
			if(chkequ(1,mid,i,i+mid-1)) res=mid,l=mid+1;
			else r=mid-1;
		}
		if(res<=i)
		{
			bt.update(1,1),bt.update(res+1,-1);
			bt2.update(1,1),bt2.update(res+1,-1);
		}
		else
		{
			bt.update(1,1),bt.update(i,-1);
			bt2.update(1,1),bt2.update(i,-1);
		}
	}
	for(int i=1;i<=n;i++) ans[i]+=i*bt.query(i)-bt2.query(i);
//	for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
//	cout<<"\n";
	int Ans=0;
	
//	cout<<"\n";
	for(int i=1;i<=n;i++)
	{
		sort(buc[i].begin(),buc[i].end());
		int maxx=0;
		for(int j=0;j<buc[i].size();j++)
		{
			int k=j,res=0;
			while(k<buc[i].size()&&buc[i][k].fi==buc[i][j].fi) res+=buc[i][k].se,k++;
//			cout<<i<<": "<<buc[i][j].fi<<" "<<res<<"\n";
			k--,j=k;
			maxx=max(maxx,res);
		}
		ans[i]+=maxx+n;
		Ans+=(ans[i]^i);
//		cout<<i<<": "<<ans[i]<<"\n"; 
	}
	cout<<Ans<<"\n";
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int _=1;
	cin>>_;
	while(_--) solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 22ms
memory: 8196kb

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
166
371
3
211
9
265
369
283
15
95
114
58
334
225
3
367
364
377
316
3
19
124
61
16
81
42
261
11
77
28
90
80
109
225
194
20
42
219
63
112
19
34
71
316
362
291
310
355
281
302
287
231
312
3
330
54
297
3
72
32
141
322
39
338
90
242
3
169
329
204
19
155
3
416
393
392
76
270
365
19
54
20
287
3
17
351
3...

result:

wrong answer 2nd lines differ - expected: '128', found: '166'