ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#183208 | #3291. 外星生物 | CodingShark | 100 | 7992ms | 317748kb | C++11 | 1.9kb | 2023-08-08 10:52:01 | 2023-08-08 12:37:34 |
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 2e5 + 5, mod = 1e9 + 7;
ll n, m, q, idx, base[N], rt[N];
struct node {
ll l, r, ls, rs, val;
} t[20000005];
char s[N];
void pushup(ll p) {
ll ls = t[p].ls, rs = t[p].rs;
t[p].val = (t[ls].val * base[t[rs].r - t[rs].l + 1] + t[rs].val) % mod;
}
int build(ll p, ll l, ll r) {
p = ++idx;
t[p].l = l, t[p].r = r;
if (l == r) {
t[p].val = s[l] - 'a' + 1;
} else {
int mid = (l + r) >> 1;
t[p].ls = build(t[p].ls, l, mid);
t[p].rs = build(t[p].rs, mid + 1, r);
pushup(p);
}
return p;
}
void update(ll u, ll v, ll l, ll r) {
if (l <= t[u].l && t[u].r <= r) {
swap(t[u], t[v]);
} else {
int mid = (t[u].l + t[u].r) >> 1;
if (l <= mid) update(t[u].ls, t[v].ls, l, r);
if (r > mid) update(t[u].rs, t[v].rs, l, r);
pushup(u), pushup(v);;
}
}
ll query(ll p, ll r) {
if (t[p].r <= r) {
return t[p].val;
}
else {
ll mid = (t[p].l + t[p].r) >> 1;
if (r <= mid) return query(t[p].ls, r);
else return (t[t[p].ls].val * base[r - mid] + query(t[p].rs, r)) % mod;
}
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
base[0] = 1;
for (int i = 1; i <= n; i++) base[i] = base[i - 1] * 1000000 % mod;
for (int i = 1; i <= m; i++) {
cin >> s + 1;
reverse(s + 1, s + n + 1);
rt[i] = build(1, 1, n);
}
cin >> q;
while (q--) {
ll op, x, y, l, r;
cin >> op >> x >> y >> l >> r;
ll tl = n - r + 1, tr = n - l + 1;
if (op & 1) {
update(rt[x], rt[y], tl, tr);
} else {
cout << ((query(rt[x], tr) - query(rt[x], tl - 1) * base[tr - tl + 1]) % mod + mod) % mod << "\n";
}
}
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 20
Accepted
Test #1:
score: 20
Accepted
time: 1ms
memory: 4228kb
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: 2ms
memory: 5024kb
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: 0ms
memory: 5008kb
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: 1ms
memory: 4976kb
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: 412ms
memory: 160588kb
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: 369ms
memory: 82352kb
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: 525ms
memory: 317732kb
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: 455ms
memory: 161268kb
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: 532ms
memory: 317688kb
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: 493ms
memory: 317588kb
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: 523ms
memory: 317684kb
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: 503ms
memory: 317728kb
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: 464ms
memory: 317696kb
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: 763ms
memory: 317652kb
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: 666ms
memory: 317648kb
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: 811ms
memory: 317728kb
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: 890ms
memory: 317748kb
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: 582ms
memory: 317728kb
input:
200000 20 xeywyxpvwiencehqsybcnfgjkwtvrkhoommnbwlafymsiftcmhvcuionwlbkmobmwqeeprptduomoalpnpnfwmebbk...
output:
578444277 339488611 542893896 848835729 560973493 870747288 432002378 88944032 344048776 706323425 6...
result:
ok 190000 numbers