UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#183168#3291. 外星生物ddh1231008332ms321580kbC++111.7kb2023-08-08 09:53:492023-08-08 12:34:33

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mod 1000000007
int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
		x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x*f;
}
int n,m,rt[25],pos,pw[200005],q,op,x,y,l,r;
char s[22][200005];
struct f{
	int l,r,ls,rs,val;
}tr[8000005];
void pushup(int p){
	tr[p].val=(tr[tr[p].ls].val+tr[tr[p].rs].val*pw[tr[tr[p].ls].r-tr[tr[p].ls].l+1]%mod)%mod;
}
void build(int &p,int idx,int l,int r){
	p=++pos;
	tr[p]={l,r,0,0,0};
	if(l==r){
		tr[p].val=s[idx][l]-'a'+1;
		return;
	}
	int mid=l+r>>1;
	build(tr[p].ls,idx,l,mid),build(tr[p].rs,idx,mid+1,r);
	pushup(p);
}
void update(int &p1,int &p2,int l,int r){
	if(tr[p1].l>r||tr[p1].r<l)
		return;
	if(l<=tr[p1].l&&tr[p1].r<=r){
		swap(p1,p2);
		return;
	}
	update(tr[p1].ls,tr[p2].ls,l,r),update(tr[p1].rs,tr[p2].rs,l,r);
	pushup(p1),pushup(p2);
}
f query(int p,int l,int r){
	if(l<=tr[p].l&&tr[p].r<=r)
		return tr[p];
	int mid=tr[p].l+tr[p].r>>1;
	if(r<=mid)
		return query(tr[p].ls,l,r);
	if(l>mid)
		return query(tr[p].rs,l,r);
	f L=query(tr[p].ls,l,r),R=query(tr[p].rs,l,r),ans;
	ans.l=L.l,ans.r=R.r;
	ans.val=(L.val+R.val*pw[L.r-L.l+1]%mod)%mod;
	return ans;
}
signed main(){
	n=read(),m=read(),pw[0]=1;
	for(int i=1;i<=n;i++)
		pw[i]=pw[i-1]*1000000%mod;
	for(int i=1;i<=m;i++)
		scanf("%s",s[i]+1);
	for(int i=1;i<=m;i++)
		build(rt[i],i,1,n);
	q=read();
	while(q--){
		op=read(),x=read(),y=read(),l=read(),r=read();
		if(op==1)
			update(rt[x],rt[y],l,r);
		else 
			printf("%lld\n",query(rt[x],l,r).val);
	}
	return 0;
}

详细

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 20
Accepted

Test #1:

score: 20
Accepted
time: 1ms
memory: 4344kb

input:

1000 10
xeywyxpvwiencehqsybcnfgjkwtvrkhoommnbwlafymsiftcmhvcuionwlbkmobmwqeeprptduomoalpnpnfwmebbkcf...

output:

1930551
570830628
957081628
156256878
781204819
573694445
368158384
537385521
478545748
841171642
71...

result:

ok 500 numbers

Test #2:

score: 0
Accepted
time: 1ms
memory: 5176kb

input:

1000 20
xeywyxpvwiencehqsybcnfgjkwtvrkhoommnbwlafymsiftcmhvcuionwlbkmobmwqeeprptduomoalpnpnfwmebbkcf...

output:

435002533
229472556
101117353
612719458
463264624
188021309
179914369
219237806
648671195
851246301
...

result:

ok 500 numbers

Test #3:

score: 0
Accepted
time: 4ms
memory: 5136kb

input:

1000 20
xeywyxpvwiencehqsybcnfgjkwtvrkhoommnbwlafymsiftcmhvcuionwlbkmobmwqeeprptduomoalpnpnfwmebbkcf...

output:

800136814
435002533
460554091
229472556
644905715
628989288
875485546
612719458
958824462
463264624
...

result:

ok 900 numbers

Test #4:

score: 0
Accepted
time: 4ms
memory: 5176kb

input:

1000 20
xeywyxpvwiencehqsybcnfgjkwtvrkhoommnbwlafymsiftcmhvcuionwlbkmobmwqeeprptduomoalpnpnfwmebbkcf...

output:

612719458
179914369
619571421
171336107
523078611
559004210
988184383
423091652
950804760
319933768
...

result:

ok 100 numbers

Subtask #2:

score: 20
Accepted

Test #5:

score: 20
Accepted
time: 433ms
memory: 162568kb

input:

100000 20
xeywyxpvwiencehqsybcnfgjkwtvrkhoommnbwlafymsiftcmhvcuionwlbkmobmwqeeprptduomoalpnpnfwmebbk...

output:

202741126
992785280
37791900
239942038
329997172
680484602
510195310
544644168
1874542
34997721
5472...

result:

ok 199900 numbers

Test #6:

score: 0
Accepted
time: 374ms
memory: 83484kb

input:

100000 10
xeywyxpvwiencehqsybcnfgjkwtvrkhoommnbwlafymsiftcmhvcuionwlbkmobmwqeeprptduomoalpnpnfwmebbk...

output:

551798668
481144323
566395931
722909131
887864197
899114360
396512095
946284189
285195734
738410204
...

result:

ok 199900 numbers

Test #7:

score: 0
Accepted
time: 599ms
memory: 321544kb

input:

200000 20
xeywyxpvwiencehqsybcnfgjkwtvrkhoommnbwlafymsiftcmhvcuionwlbkmobmwqeeprptduomoalpnpnfwmebbk...

output:

578444277
339488611
542893896
848835729
560973493
870747288
432002378
88944032
344048776
706323425
6...

result:

ok 199900 numbers

Test #8:

score: 0
Accepted
time: 452ms
memory: 163356kb

input:

200000 10
xeywyxpvwiencehqsybcnfgjkwtvrkhoommnbwlafymsiftcmhvcuionwlbkmobmwqeeprptduomoalpnpnfwmebbk...

output:

618199892
67146077
37791900
125309264
495514930
908674504
836301886
880815994
391673061
693896029
30...

result:

ok 199900 numbers

Subtask #3:

score: 25
Accepted

Test #9:

score: 25
Accepted
time: 544ms
memory: 321484kb

input:

200000 20
xeywyxpvwiencehqsybcnfgjkwtvrkhoommnbwlafymsiftcmhvcuionwlbkmobmwqeeprptduomoalpnpnfwmebbk...

output:

313690002
722680141
526488400
870747288
432002378
88944032
344048776
552519703
131676088
906930577
2...

result:

ok 100000 numbers

Test #10:

score: 0
Accepted
time: 475ms
memory: 321508kb

input:

200000 20
xeywyxpvwiencehqsybcnfgjkwtvrkhoommnbwlafymsiftcmhvcuionwlbkmobmwqeeprptduomoalpnpnfwmebbk...

output:

560973493
688023878
907382464
793429235
539052280
582406193
92631656
831744136
289881319
398460264
1...

result:

ok 50000 numbers

Test #11:

score: 0
Accepted
time: 574ms
memory: 321484kb

input:

200000 20
xeywyxpvwiencehqsybcnfgjkwtvrkhoommnbwlafymsiftcmhvcuionwlbkmobmwqeeprptduomoalpnpnfwmebbk...

output:

539813063
253352162
603953303
722680141
795453635
760417951
611996691
93976071
124343135
206974182
7...

result:

ok 150000 numbers

Test #12:

score: 0
Accepted
time: 558ms
memory: 321484kb

input:

200000 20
xeywyxpvwiencehqsybcnfgjkwtvrkhoommnbwlafymsiftcmhvcuionwlbkmobmwqeeprptduomoalpnpnfwmebbk...

output:

578444277
339488611
542893896
848835729
560973493
870747288
432002378
88944032
344048776
706323425
6...

result:

ok 190000 numbers

Test #13:

score: 0
Accepted
time: 515ms
memory: 321528kb

input:

200000 20
xeywyxpvwiencehqsybcnfgjkwtvrkhoommnbwlafymsiftcmhvcuionwlbkmobmwqeeprptduomoalpnpnfwmebbk...

output:

834470482
131373140
672252697
338771275
897162517
252369650
744208143
819135787
239412394
28660770
1...

result:

ok 10000 numbers

Subtask #4:

score: 35
Accepted

Test #14:

score: 35
Accepted
time: 766ms
memory: 321456kb

input:

200000 20
xeywyxpvwiencehqsybcnfgjkwtvrkhoommnbwlafymsiftcmhvcuionwlbkmobmwqeeprptduomoalpnpnfwmebbk...

output:

848835729
560973493
709203343
88944032
344048776
706323425
612851753
840618781
142513794
629827561
3...

result:

ok 100000 numbers

Test #15:

score: 0
Accepted
time: 684ms
memory: 321576kb

input:

200000 20
xeywyxpvwiencehqsybcnfgjkwtvrkhoommnbwlafymsiftcmhvcuionwlbkmobmwqeeprptduomoalpnpnfwmebbk...

output:

339488611
542893896
848835729
560973493
870747288
432002378
88944032
344048776
706323425
612851753
8...

result:

ok 150000 numbers

Test #16:

score: 0
Accepted
time: 819ms
memory: 321528kb

input:

200000 20
xeywyxpvwiencehqsybcnfgjkwtvrkhoommnbwlafymsiftcmhvcuionwlbkmobmwqeeprptduomoalpnpnfwmebbk...

output:

709203343
747864822
629827561
797228779
601251182
511455936
986974650
933153790
935375524
289273517
...

result:

ok 50000 numbers

Test #17:

score: 0
Accepted
time: 888ms
memory: 321544kb

input:

200000 20
xeywyxpvwiencehqsybcnfgjkwtvrkhoommnbwlafymsiftcmhvcuionwlbkmobmwqeeprptduomoalpnpnfwmebbk...

output:

747864822
918735353
430140683
743491944
288154457
6277957
289046620
5199589
98581861
884869571
93498...

result:

ok 10000 numbers

Test #18:

score: 0
Accepted
time: 641ms
memory: 321580kb

input:

200000 20
xeywyxpvwiencehqsybcnfgjkwtvrkhoommnbwlafymsiftcmhvcuionwlbkmobmwqeeprptduomoalpnpnfwmebbk...

output:

578444277
339488611
542893896
848835729
560973493
870747288
432002378
88944032
344048776
706323425
6...

result:

ok 190000 numbers