QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#392892#6419. Baby's First Suffix Array ProblemDiuTL 4315ms15484kbC++144.1kb2024-04-17 21:53:222024-04-17 21:53:23

Judging History

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

  • [2024-04-17 21:53:23]
  • 评测
  • 测评结果：TL
  • 用时：4315ms
  • 内存：15484kb
查看
  • [2024-04-17 21:53:22]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e4+10;
int _,n,m;
int rk[N],sa[N],hei[N];
char s[N];
namespace SA{
	int m,x[N],y[N],c[N],mn[N][18],lg[N];
	bool cmp(int i,int j){
		while(i<=n&&j<=n){
			if(s[i]!=s[j])return s[i]<s[j];
			++i,++j;
		}
		return i>j;
	}
	void get_sa(){
		for(int i=1;i<=n;i++)sa[i]=i;
		sort(sa+1,sa+n+1,cmp);
//		m=131;
//		memset(sa,0,(n+1)*sizeof(int));
//		memset(y,0,(n+1)*sizeof(int));
//		memset(x,0,(n+1)*sizeof(int));
//		memset(c,0,max(m+1,n+1)*sizeof(int));
//		for(int i=1;i<=n;i++)c[x[i]=s[i]]++;
//		int l=0;
//		for(int i=1;i<=m;i++)c[i]+=c[i-1];
//		for(int i=n;i>=1;i--)sa[c[s[i]]--]=i;
//		for(int k=1;k<=n;k<<=1){
//			int num=0;
//			for(int i=n-k+1;i<=n;i++)y[++num]=i;
//			for(int i=1;i<=n;i++)if(sa[i]>k)y[++num]=sa[i]-k;
//			for(int i=1;i<=m;i++)c[i]=0;
//			for(int i=1;i<=n;i++)c[x[i]]++;
//			for(int i=2;i<=m;i++)c[i]+=c[i-1];
//			for(int i=n;i>=1;i--)sa[c[x[y[i]]]--]=y[i],y[i]=0;
//			swap(x,y);
//			num=1,x[sa[1]]=1;
//			for(int i=2;i<=n;i++){
//				if(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])x[sa[i]]=num;
//				else x[sa[i]]=++num; 
//			}
//			if(num==n)break;
//			m=num;
//		}
		for(int i=1;i<=n;i++)rk[sa[i]]=i;
		for(int i=1,k=0;i<=n;i++){
			int j=sa[rk[i]-1];k-=(k!=0);
			while(s[i+k]==s[j+k])++k;
			hei[rk[i]]=k;
		}
		for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;
		for(int i=1;i<=n;i++){
			mn[i][0]=hei[i];
			for(int j=1;i>>j;j++)mn[i][j]=min(mn[i][j-1],mn[i-(1<<j-1)][j-1]);
		}
	}
	int lcp(int l,int r){
		l=rk[l],r=rk[r];
		if(l>r)swap(l,r);++l;
		int d=lg[r-l+1];
		return min(mn[r][d],mn[l+(1<<d)-1][d]);
	}
}
using SA::lcp;
struct Bit{
	int vis[N],st[N],tp,c[N];
	void ins(int i,int v){
		for(;i<=n;i+=i&-i){
			if(!vis[i])vis[i]=1,st[++tp]=i;
			c[i]+=v;
		}
	}
	int qry(int i){
		int s=0;
		for(;i;i&=i-1)s+=c[i];
		return s;
	}
	void clr(){
		for(;tp;--tp)vis[st[tp]]=c[st[tp]]=0;
	}
}T;
struct que{
	int l,r,i;
	bool operator<(const que h)const{return r<h.r;}
}ql[N],qr[N];
vector<que> q1[N],q2[N];
int ans[N];
namespace Conquer{
	int s[N];
	void solve(int l,int r){
		if(l==r)return;
		int mid=l+r>>1;solve(l,mid),solve(mid+1,r);
		s[mid]=s[mid+1]=hei[mid+1];
		for(int i=mid-1;i>=l;i--)s[i]=min(s[i+1],hei[i+1]);
		for(int i=mid+2;i<=r;i++)s[i]=min(s[i-1],hei[i]);
		for(int i=l;i<=mid;i++)for(que t:q1[i]){
			for(int j=mid+1;j<=r;j++){
				if(sa[j]>t.l&&sa[j]<=t.r&&min(s[i],s[j])>=t.r-sa[j]+1)++ans[t.i];
			}
		}
		return;
		int tl=0,tr=0;
		for(int i=mid;i>=l;i--){
			for(que t:q1[i]){
				int L=max(t.l+1,t.r-s[i]+1),R=t.r;
				if(L<=R)ql[++tl]={L,R,t.i};
			}
		}
		for(int i=mid+1;i<=r;i++)qr[++tr]={sa[i],sa[i]+s[i],i};
		sort(ql+1,ql+tl+1),sort(qr+1,qr+tr+1);
		int p=tr;
		for(int i=tl;i>=1;i--){
			while(p&&qr[p].r>ql[i].r)T.ins(qr[p].l,1),--p;
			ans[ql[i].i]+=T.qry(ql[i].r)-T.qry(ql[i].l-1);
		}
		T.clr();
	}
}
signed main(){
//	freopen("str.in","r",stdin);
//	freopen("str.out","w",stdout);
	scanf("%d",&_);
	for(;_--;){
		scanf("%d%d\n%s",&n,&m,s+1);
		SA::get_sa();
//		for(int i=1;i<=n;i++)printf("%d ",sa[i]);puts("");
//		for(int i=1;i<=n;i++)printf("%d ",rk[i]);puts("");
//		for(int i=1;i<=n;i++)printf("%d ",hei[i]);puts("");
		for(int i=1;i<=n;i++)q1[i].clear(),q2[i].clear(); 
		for(int i=1,l,r,k;i<=m;i++){
			scanf("%d%d%d",&l,&r,&k),ans[i]=1;
			int L=0,R=rk[k];
			while(L+1<R){
				int mid=L+R>>1;
				if(lcp(k,sa[mid])>=r-k+1)R=mid;
				else L=mid;
			}
			if(k>l)q2[L].push_back({l,k-1,i});
			if(k<r)q2[rk[k]].push_back({k+1,r,i}),q1[rk[k]].push_back({k,r,i});
			for(int j=l;j<k;j++)if(rk[j]<rk[k]&&lcp(j,k)<r-k+1)++ans[i];
			for(int j=k+1;j<=r;j++)if(rk[j]<rk[k])++ans[i];
			for(int j=k+1;j<=r;j++)if(rk[j]>rk[k]&&lcp(j,k)>=r-j+1)++ans[i];
		}
//		for(int i=1;i<=n;i++){
//			T.ins(sa[i],1);
//			for(que t:q2[i])ans[t.i]+=T.qry(t.r)-T.qry(t.l-1);
//		}
//		T.clr();
//		Conquer::solve(1,n);
		for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
	}
}
/*
1
10 1
abaabbaabb
6 9 6
2 8 3
1 8 5
9 9 9
5 10 7
5 7 7
7 8 7
5 6 6
1 9 9
3 9 5
*/
源文件, 语言: C++14

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 7488kb

input:

2
10 4
baaabbabba
2 8 3
1 1 1
2 3 2
2 5 4
20 3
cccbccbadaacbbbcccab
14 17 16
3 20 17
17 20 18

output:

2
1
2
3
4
15
3

result:

ok 7 numbers

Test #2:

score: 0
Accepted
time: 15ms
memory: 8968kb

input:

8994
10 10
abaabbaabb
2 8 3
1 8 5
6 9 6
9 9 9
5 10 7
5 7 7
7 8 7
5 6 6
1 9 9
3 9 5
2 1
ab
1 2 1
8 6
bbabaabb
3 7 7
5 7 7
1 5 1
1 4 3
3 5 3
5 5 5
10 3
aababbaaab
3 4 4
6 9 8
4 6 6
7 3
babbaab
5 6 5
3 6 6
1 6 6
9 3
baaaabbba
2 5 2
8 9 8
1 4 4
9 2
babaababa
2 4 4
2 6 3
2 3
ba
1 2 2
1 2 1
2 2 2
10 2
aba...

output:

3
8
4
1
1
1
2
1
6
7
1
4
3
5
1
2
1
1
2
2
2
1
1
4
2
1
1
5
1
2
1
5
2
3
1
1
1
4
3
2
1
1
3
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
3
1
1
1
1
1
1
1
3
2
1
2
1
1
2
3
1
1
1
2
1
1
1
1
1
1
1
1
2
1
1
2
2
1
2
2
2
2
1
2
2
1
1
5
1
1
3
2
4
1
2
1
2
1
1
1
4
2
2
2
6
1
1
2
2
1
2
1
4
4
1
1
1
1
1
1
1
2
1
4
2
3
2
2
1
4
2
2
2
2
1
2
...

result:

ok 50000 numbers

Test #3:

score: 0
Accepted
time: 17ms
memory: 7376kb

input:

3349
12 39
ccccaabbacac
7 11 10
2 11 2
2 6 4
8 10 9
4 7 4
6 12 8
5 10 10
10 12 10
1 8 8
8 10 8
1 3 3
8 10 8
7 7 7
9 11 10
2 9 6
1 2 1
10 12 10
5 6 5
2 11 2
7 11 7
4 4 4
3 4 3
11 12 11
1 7 4
3 12 6
6 8 7
6 12 11
1 9 6
5 11 5
4 5 4
3 8 8
2 9 3
6 10 8
1 3 3
1 11 11
6 11 6
8 11 11
6 9 6
3 9 4
20 2
accba...

output:

5
10
3
1
4
4
6
3
3
2
1
2
1
3
3
2
3
2
10
4
1
2
1
4
2
3
2
3
2
2
3
7
3
1
1
2
1
2
6
5
9
1
6
3
1
1
2
3
3
2
2
5
4
2
8
1
2
5
1
3
6
3
5
5
1
2
3
1
4
4
2
5
2
3
2
3
2
1
3
1
1
5
7
4
5
6
7
4
1
4
1
7
14
2
3
4
1
4
3
1
1
1
9
2
3
3
7
2
7
8
4
7
4
3
3
3
6
1
3
2
1
2
2
2
5
3
3
3
1
4
8
6
3
1
1
5
1
1
2
1
4
2
10
1
6
1
4
1
...

result:

ok 50000 numbers

Test #4:

score: 0
Accepted
time: 40ms
memory: 8224kb

input:

333
130 121
cdbcacbdbcaccccdbabadddbccbcadbadbcdddcbdcdcaddcaccdbaaadcbdbadabddaddadccdbadbbbaabdadabcbadacaabcabdaddbdaacbccbdddddcaacbcdcdab
81 115 82
22 81 24
49 95 57
22 101 26
66 71 66
90 98 92
31 118 98
70 70 70
33 77 64
61 126 99
11 34 14
9 89 70
17 101 94
5 56 34
47 83 54
2 10 6
63 68 64
47 ...

output:

2
21
44
46
6
4
32
1
4
37
17
59
11
19
3
7
2
35
21
16
2
38
25
23
3
40
1
53
17
72
64
11
4
20
11
25
10
56
13
8
98
37
8
43
16
3
34
9
91
36
10
22
2
15
11
3
4
21
85
17
2
32
1
6
1
26
2
79
1
4
7
2
4
10
16
2
19
3
39
7
32
66
4
2
22
67
2
16
34
25
11
1
30
44
32
6
32
26
25
1
36
39
44
46
5
11
29
14
10
7
3
26
20
30...

result:

ok 50000 numbers

Test #5:

score: 0
Accepted
time: 144ms
memory: 8308kb

input:

32
1618 204
bdbcacdcecbeaabdcebdcedeacbaeadadbaaceebaeccacdadcabaaebeabdabdcbabaececbeccddbdeabcebebdcdcbbcccebdcecbbadbebbcacacecbbbaddebcaecadccdadccdddaaabaeacebbcaddacaabcbdccabedccbebbcebeeadcdecbbdaabecebeaddaadaeeecbcadeaaeeaedbddceabadcbdbcabbbedcabaacaddcbccdcdeebdadbeeeaebbbdeebbaebdbecadc...

output:

17
33
74
113
19
7
83
262
25
118
47
42
106
144
91
225
64
443
21
68
100
21
152
524
511
74
49
3
642
544
23
123
59
547
45
459
37
718
99
22
140
234
847
127
4
115
921
64
173
296
148
192
96
115
3
5
594
377
936
510
7
84
39
268
89
19
78
252
938
297
45
57
429
992
1160
23
3
47
526
609
30
30
1
1116
364
355
64
4...

result:

ok 50000 numbers

Test #6:

score: 0
Accepted
time: 1191ms
memory: 12492kb

input:

3
14322 3266
ahdmjrtnnkvotzitfqctsisxdlevjmdpocarqibnvfgpmlwkeuynawqzhnjwvtzxlckeawjwmaobieqaflnnlovlpxnjtafikqhvviqmkcyhiljgsohiqkxrpajshiighwhtglkrnbofakpqlxuwiruddxvntsvhgmwzitrtznsydvmyfhqltgtuoakvyxezwpkfwgurykrsekcaapjrvfmtljtxnvraisnvybuzveqvfglnhhqgrecvwiyzgerkwzeayvdhkfdmiwdgvxpyqajevefzzxn...

output:

3188
47
2495
4509
3896
564
619
1537
266
61
1746
148
804
1857
4589
7088
1449
344
937
4533
70
2727
62
5225
3477
341
93
121
5058
1706
1939
2786
98
342
314
4701
2938
1998
466
194
615
975
3044
432
2108
578
302
4645
3201
419
1233
345
907
4760
4944
1707
357
1297
1253
256
18
4371
3859
1029
308
860
3256
2444...

result:

ok 50000 numbers

Test #7:

score: 0
Accepted
time: 4231ms
memory: 15048kb

input:

1
50000 50000
bbbbababaaaabababaaabaabaabbabbabbaaabbbbbbabbbababaaaaabbaaabbbababbbaabaabababababbbabaaaababaababbabbbabbbabaabbbbbaababaaaabaaaaaabaabbaaaabbaaababbbabbaabaababbbaabbbbaabbbbabbaabbabababaaabaababaabaabababbabbbabaaabaaabaabbaabbaabababaaaaabaabbabbbaaaabbbabbabbbaaabaaaabbbbaabbaa...

output:

14106
7199
315
23
21768
4574
19032
9447
1399
4075
4509
3770
22703
9626
11967
39
8208
14885
9810
2885
1501
4344
5191
11468
25450
22059
10473
7168
5765
12478
5895
9215
26023
17780
21556
22347
9214
3076
897
17612
122
79
1237
6864
8620
15374
10972
18213
2633
9313
1003
15871
1814
6148
28475
9887
3248
262...

result:

ok 50000 numbers

Test #8:

score: 0
Accepted
time: 4315ms
memory: 15484kb

input:

1
50000 50000
aacccdaaabbbdcdbbccdddabbcbcacacdaaccaabcdaabcbcccbbbcadbdacabdbdddaddbabdcbcbacaddbdababcdadcbccacbdabcdbcaabcacddccbbdcdcbdcabcdbaadccccbccabbabcdbdcdddcadaddcabcbbdabaacabadcccbaaadbbbaaacdddabdaaabbaacbaaaabcadbacbbaadbbdbadaccdabaabcdddbcbaadaaabbbabbabbdcdadacbdacdbcaccadaccbcbcd...

output:

3461
254
1838
11909
11583
31007
498
649
5860
32819
18923
11053
2374
2864
9971
17207
1809
38307
302
6601
8782
31585
1179
2468
8836
231
578
6954
14984
14872
14214
4800
30011
7393
3173
1337
3929
210
29907
28679
5533
25781
5465
2763
10445
16179
5934
7912
10297
1839
42608
57
2590
12060
355
13200
7015
129...

result:

ok 50000 numbers

Test #9:

score: 0
Accepted
time: 68ms
memory: 15064kb

input:

1
50000 50000
ccccdcabcabababbbdadddabccdbddcbacdcbcaadccdabcbaadccbdddccddccbdabaccbcaddbabbbabaadccacbcbaadbacacdadddacdcbbabacbbcabbddccbbdcdbcbcddaabdaaccddbcaccbcbbcbbbbbdddbaadbdddacaddbcbaacaacbccbccbdcccacbabbdcddaacdacdcdaccbaaacdccbaacdadbbaaaacccdbaaaabaddcabcaadaddbbabdadcdccdabbabcdaaad...

output:

51
4
27
10
41
8
17
78
26
6
24
7
4
10
25
74
28
1
15
27
19
28
54
25
1
33
63
4
1
19
6
48
13
20
44
26
7
1
22
50
10
65
5
5
43
34
4
3
16
8
32
40
16
15
80
7
14
45
22
15
13
7
65
45
64
12
14
16
22
2
10
26
66
30
17
35
19
4
55
17
78
8
14
85
27
2
37
1
2
4
11
3
7
22
55
29
7
33
4
5
15
18
15
8
9
21
73
40
8
51
97
2...

result:

ok 50000 numbers

Test #10:

score: -100
Time Limit Exceeded

input:

1
50000 50000
aadddbddbdcdccdbabcdddaaadadbbaabdcbbbdddbdcdadabdcdadbcccdabdbcabddabbdaadbcccadcbdddabcaacabbdcadccbcaadcbdaddabbaadcdadadaadbcdbbdcaabccbddcddaabdabcbdbbdcadadbabdbbbbbbbcadaaccbbacacbaaccbacddcaaddbcbbbdaadbdadabbcdcabdddcacbbcadbbcabbacddbcacbacdbbbccacdccdccbbcdbacbcadddcdbcccaba...

output:

result:
English 繁體中文 简体中文

服务器时间: 2024-12-03 01:55:47 | 开源项目