QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#424844 | #5022. 【模板】线段树 | APJifengc | 31 | 2613ms | 15392kb | C++14 | 2.3kb | 2024-05-29 18:53:35 | 2024-05-29 18:53:35 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 250005;
const int B = 600;
int id;
int n, q, a[MAXN], b[MAXN], c[MAXN];
int qc, qt[MAXN], ql[MAXN], qr[MAXN], qx[MAXN], qid[MAXN];
int qq;
int bl[MAXN], L[MAXN], R[MAXN];
void update(int i, int cc) {
for (int j = 1; j <= cc; j <<= 1) if (cc & j) {
for (int k = R[i]; k - j >= max(1, L[i - 1]); k--) b[k] ^= b[k - j];
}
}
int ans[MAXN];
void rebuild() {
for (int i = (bl[n] == 1 ? 1 : 2); i <= bl[n]; i++) {
int ll = (i == 2 ? 1 : L[i]), rr = R[i];
for (int j = L[i - 1]; j <= R[i]; j++) b[j] = a[j];
int cc = 0;
for (int j = 1; j <= qc; j++) {
if (qt[j] == 1) {
if (qr[j] < L[i - 1] || ql[j] > R[i]) continue;
if (ql[j] <= L[i - 1] && R[i] <= qr[j]) {
cc++;
continue;
}
update(i, cc), cc = 0;
for (int k = min(R[i], qr[j]); k > max(L[i - 1], ql[j]); k--) b[k] ^= b[k - 1];
} else {
update(i, cc), cc = 0;
if (qx[j] < ll || qx[j] > rr) continue;
ans[qid[j]] = b[qx[j]];
}
}
update(i, cc);
for (int j = ll; j <= rr; j++) c[j] = b[j];
}
for (int i = 1; i <= n; i++) a[i] = c[i];
// for (int i = 1; i <= n; i++) printf("%d ", a[i]);
// printf("\n");
qc = 0;
}
int main() {
// freopen("xor.in", "r", stdin);
// freopen("xor.out", "w", stdout);
scanf("%d%d%d", &id, &n, &q);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int l = 1, r, i = 1; l <= n; l = r + 1, i++) {
r = min(n, l + B - 1);
L[i] = l, R[i] = r;
for (int j = l; j <= r; j++) bl[j] = i;
}
for (int i = 1; i <= q; i++) {
int op; scanf("%d", &op);
++qc;
if (op == 1) {
int l, r; scanf("%d%d", &l, &r);
qt[qc] = 1, ql[qc] = l, qr[qc] = r;
} else {
int x; scanf("%d", &x);
qt[qc] = 2, qx[qc] = x, qid[qc] = ++qq;
}
if (qc == B) rebuild();
}
rebuild();
for (int i = 1; i <= qq; i++) printf("%d\n", ans[i]);
for (int i = 1; i <= n; i++) printf("%d\n", a[i]);
return 0;
}
詳細信息
Subtask #1:
score: 8
Accepted
Test #1:
score: 8
Accepted
time: 0ms
memory: 14032kb
input:
1 6 6 1 1 5 1 9 4 2 5 1 2 5 2 4 1 3 6 2 6 1 1 6
output:
9 4 12 1 0 5 4 12 0
result:
ok 9 numbers
Test #2:
score: 0
Accepted
time: 2ms
memory: 12104kb
input:
1 999 997 898798734 979577086 45974352 1013270193 1053191143 533594258 372426673 947830633 122319874 368651315 866424479 109724831 427664962 558099346 764830489 326451620 322471751 525780385 746941281 670254345 586958579 979544209 743892216 436404384 291681381 979530194 998929567 367716728 909076993...
output:
1015342581 962986689 965094083 871356796 835210392 172023195 63088572 606096781 569607283 436055720 154605892 663158209 154605892 776365236 281312240 62398687 182713417 604764772 816533315 793514230 325061861 806973284 91749226 283750235 198953311 170342298 432592070 809908556 683302450 40932811 669...
result:
ok 1996 numbers
Test #3:
score: 0
Accepted
time: 2ms
memory: 12084kb
input:
1 999 997 89872218 906651903 120274311 490547919 291584020 755757065 24942887 707247173 763024744 68250332 114193028 999245166 140381610 171802205 399965713 299821903 907998064 906075056 427270276 335420206 708713870 492555323 359637714 197212814 35225369 1011322274 912003632 633998134 1026276199 85...
output:
89872218 860962725 120274311 490547919 978745892 924706625 610771729 524956121 105748312 139294727 866385688 729638611 92178006 1037482711 80194776 277477501 592738191 694314356 733017733 701758468 65199929 983529101 717179143 542164040 444291361 439952700 147939819 276321083 1012586084 166061298 30...
result:
ok 999 numbers
Test #4:
score: 0
Accepted
time: 0ms
memory: 14192kb
input:
1 998 997 802301789 913975794 256883306 462593698 958614999 708264636 114045898 622336472 273146091 1035403087 151608039 853195969 670449389 1967248 347890740 88419426 272759411 668812195 315110503 54515201 11283025 183682542 149656693 916299553 345162140 626592021 633508243 201443721 191882154 4200...
output:
654798390 720797824 232736065 90537128 467468783 391542471 410387328 970043816 199400953 691327788 183682542 543340459 435746483 305146388 967107550 72899382 419833683 273367829 1062016570 511549763 893866015 137019003 177123936 524992882 462306449 1057090504 72525968 344810664 332588248 94524245 57...
result:
ok 1491 numbers
Test #5:
score: 0
Accepted
time: 2ms
memory: 13996kb
input:
1 10 64 178 181 183 184 188 189 190 191 192 195 1 3 5 2 10 2 8 1 4 9 2 10 2 2 1 1 5 2 5 2 3 2 3 1 2 7 2 3 1 3 9 2 7 1 1 8 1 2 8 2 7 2 7 2 5 2 2 2 7 2 5 1 2 7 1 8 10 1 2 3 1 6 10 1 5 6 1 5 7 2 4 1 5 10 1 2 5 2 3 1 4 7 2 5 1 2 10 1 3 10 1 2 5 2 3 1 1 3 1 2 7 2 10 1 2 9 2 4 1 2 6 2 10 1 4 6 1 2 9 2 4 2...
output:
195 191 195 181 4 2 2 5 7 1 1 3 181 1 3 15 2 12 2 6 189 6 186 7 9 6 125 13 13 189 189 183 178 181 183 10 4 14 189 179 122 6
result:
ok 42 numbers
Subtask #2:
score: 0
Time Limit Exceeded
Test #6:
score: 0
Time Limit Exceeded
input:
2 249998 99999 1048488450 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
result:
Subtask #3:
score: 0
Time Limit Exceeded
Test #10:
score: 0
Time Limit Exceeded
input:
3 250000 99999 1 1 1 1 1 0 1 0 1 1 0 1 0 1 1 1 1 1 1 0 1 0 1 0 1 1 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 1 0 0 1 0 0 1 1 1 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 1 1 0 1 1 0 1 1 1 0 0 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 0 1 0 0 1 0 1 1 1 0 1 1 0 1 1 0 1 0 0 1 1...
output:
result:
Subtask #4:
score: 0
Time Limit Exceeded
Test #14:
score: 0
Time Limit Exceeded
input:
4 249996 99997 309331355 195839266 912372930 57974187 363345291 954954162 650621300 389049294 821214285 263720748 231045308 844370953 768579771 664766522 681320982 124177317 32442094 297873605 743179832 1073656106 443742270 235746807 1054294813 974443618 422427461 307448375 1018255356 20105813 36821...
output:
result:
Subtask #5:
score: 12
Accepted
Test #18:
score: 12
Accepted
time: 285ms
memory: 15308kb
input:
5 249997 99997 860563869 428592873 58576739 761578583 47999879 294581118 988847649 569566599 640106250 440172702 178219106 966598261 763325707 846927552 877923116 145156535 246778542 25949847 507939778 116507169 555239769 259969305 328955819 171606729 535970481 121608060 4437163 370976515 713807003 ...
output:
860563869 717285236 452329866 773393204 485721677 965902221 831024341 890990738 455498944 92913689 556500009 102303365 264515518 445496274 654612933 988537886 165104807 364103659 952755344 576499197 775866335 1003839403 606880290 1006459039 1005979559 588810854 592470517 765610807 123827263 86327854...
result:
ok 249997 numbers
Test #19:
score: 0
Accepted
time: 283ms
memory: 14396kb
input:
5 249998 100000 1055401468 532211763 131695513 214363867 831955115 452049333 729606869 69161863 428100767 90941242 729034740 90774107 332674212 930394013 601735907 104187221 1017052616 31513597 868964816 1054507185 926990168 75998133 1039482150 781325037 680316641 471310435 780674964 330142918 10271...
output:
1055401468 532211763 131695513 214363867 831955115 452049333 729606869 69161863 428100767 90941242 729034740 90774107 332674212 930394013 601735907 104187221 1017052616 31513597 868964816 1054507185 926990168 75998133 1039482150 781325037 680316641 471310435 780674964 330142918 1027184688 750941669 ...
result:
ok 249998 numbers
Test #20:
score: 0
Accepted
time: 185ms
memory: 14416kb
input:
5 249999 65535 206222027 1038492265 248834236 84032585 981309757 273118313 589015947 1002433231 482381717 342803573 48417408 196676553 50772773 199061806 637191822 974252922 289297532 48985206 415073252 593023329 9193325 632026989 55397875 918843456 476033799 664362612 383124333 926156312 133237149 ...
output:
206222027 833392802 1064859678 981091415 515434 272673027 861602440 149219399 337930194 4891559 44591399 152134382 169335243 30058725 607153771 505513233 253743469 234136859 357115647 907147166 916304115 322324382 276499053 650082861 987810090 494507870 196056115 1016828459 996842422 602075803 53081...
result:
ok 249999 numbers
Subtask #6:
score: 0
Time Limit Exceeded
Dependency #5:
100%
Accepted
Test #21:
score: 16
Accepted
time: 2613ms
memory: 14516kb
input:
6 249999 99998 234899190 294042590 622374272 592723113 719234312 350081074 842293736 684699037 330659123 145765638 707972395 212219898 665588169 1002656251 377046330 569400576 515159132 246671859 367313733 436193585 1056439739 889727758 441186237 802117710 672761337 1013893805 760105556 959623512 10...
output:
416342969 682608684 897388094 564167584 723521403 277032360 571217154 804968920 345689708 20430886 2669323 397914023 682539746 743678615 902811241 79705781 117866215 29290630 463835109 948618157 996425135 333840809 879030503 756069154 651860206 62844241 563208222 473841643 306068071 945671265 755499...
result:
ok 340922 numbers
Test #22:
score: -16
Time Limit Exceeded
input:
6 249999 100000 440794180 373448998 924631752 1029747555 1025197824 772227211 39885098 362601933 28836613 109487897 1065155159 170512808 1054469991 504110707 412993411 172546234 861597564 320825471 551313957 607675657 108258007 713412450 183442416 266654936 968422736 230720896 824830683 653610670 10...
output:
result:
Subtask #7:
score: 11
Accepted
Dependency #5:
100%
Accepted
Test #28:
score: 11
Accepted
time: 1007ms
memory: 14572kb
input:
7 249999 99998 1028875149 290751586 85260062 527433830 11253389 381520904 163374626 882045937 328797576 362761070 107207247 721987314 848366187 492948114 913994419 980121735 553555299 238308272 517289115 493658637 535863518 18389830 59694996 328276770 970756488 409396240 782649706 568544673 92874299...
output:
1028875149 738715631 944215187 442824568 301937391 208850429 326346711 949048384 530229817 360046897 113798338 662976437 1038450827 77462178 408152765 715534355 971679612 157215891 311073633 592050299 123595235 1003261179 822447669 966766090 711357766 488633610 854837708 587478280 758571291 10388445...
result:
ok 249999 numbers
Test #29:
score: 0
Accepted
time: 284ms
memory: 15392kb
input:
7 250000 99998 68776396 519381483 967158007 157650177 569513143 170186723 329178420 121791809 611207883 4984898 668763787 598163713 1067063994 73036043 445005646 777536482 1071223412 711474045 512588044 150106310 84537131 583523355 991697048 704428493 1040325967 695429796 248804866 405113944 8955700...
output:
68776396 451694631 1035786555 707556817 636183931 825922419 265294008 354815728 544684807 1053690542 1041110395 175499474 1042232586 785949259 696187148 979469550 1002496952 257816878 484979267 702731538 523966500 54856010 277941363 600194134 564966460 1007604812 797742414 138134944 262931849 730450...
result:
ok 250000 numbers
Test #30:
score: 0
Accepted
time: 861ms
memory: 15368kb
input:
7 249997 99997 597183909 680101817 292954814 211421060 322240152 582982668 261783670 350567227 690037262 665337267 214181897 200518471 817281670 553043840 562097559 36896281 153617858 166007682 919116929 500935009 642844867 876022540 147528553 447604240 272016329 28978861 747757614 112386136 5414641...
output:
597183909 185715228 292954814 895853187 37936166 553467946 21126100 720689625 165437988 548176949 1033516728 268911522 245848164 42031800 496986717 505377734 115080393 320037524 8447838 84209644 692547061 135333692 103154939 331647431 65501326 604960963 472833001 216393214 560453260 514521781 346023...
result:
ok 249997 numbers
Test #31:
score: 0
Accepted
time: 1065ms
memory: 14436kb
input:
7 250000 99998 448881889 860688996 573487325 501725480 82207547 365466204 111713682 265756761 150179737 873496281 847554992 121243005 493490008 335806025 1054184887 221928483 98453014 993533271 264435810 650583574 54232494 956669682 151684782 650423140 503351870 451693638 335380441 476842585 5789527...
output:
448881889 860688996 573487325 1070137845 62963442 1065638443 962698343 265756761 926584428 53145781 844631389 833680312 919444669 819251611 228216850 901320877 843271188 844229702 45197181 338940316 983349996 314621672 700949658 149399591 825587888 238508532 189693444 327451919 176433288 354458160 6...
result:
ok 250000 numbers
Test #32:
score: 0
Accepted
time: 1064ms
memory: 15108kb
input:
7 249998 99997 547007742 509093478 92080843 368117206 919862472 375917150 424662519 525029880 440047984 1025000696 932314846 285515394 164841215 390692110 6412328 797713131 944025279 534448825 1023285696 692312046 260461368 55543634 834032845 662470531 736141364 551086449 346792889 100321507 4569228...
output:
547007742 509093478 455421101 277614365 589494558 60362632 424662519 179983406 753493432 82601881 786311977 240111482 899879636 162894114 46530214 751948231 587497894 611222719 1026063420 125323473 32643939 995589495 63389116 1005201515 695130788 1060664077 838309277 40305139 166274187 452500877 727...
result:
ok 249998 numbers
Test #33:
score: 0
Accepted
time: 1054ms
memory: 14848kb
input:
7 250000 99997 562413573 834049947 408675594 795659456 400823146 935313070 432349725 73792611 423917761 783162558 61472281 339796225 536937096 1066637142 869886618 188301639 797581692 319235651 259285887 328309280 181691545 398762900 995340004 494956219 1050273053 15601556 606224678 500209796 359266...
output:
562413573 834049947 408675594 517626715 550714016 255287556 966692825 623378900 423917761 177229081 882317931 157377955 122626377 582095860 957581519 367511930 394479318 94512312 1044965919 348268657 188270399 6795561 604484142 833487752 762204463 132792750 505784013 308519604 831637499 71789851 216...
result:
ok 250000 numbers
Test #34:
score: 0
Accepted
time: 318ms
memory: 13620kb
input:
7 249999 100000 302448361 57136927 811790644 140050867 771930139 171529339 881027903 513211210 928072261 592513846 652835668 567734554 205221274 834498580 943482823 606941191 693560976 855105562 944712493 451533111 932510172 251195533 549703772 454765070 1016453234 239382258 181843560 562871347 6850...
output:
302448361 291580406 576983005 693819761 1006913266 895141270 954588409 661955940 626506924 90267781 870069964 979704396 124676397 484217195 492498869 366750743 995104889 180367228 863879776 274542049 583424446 395823693 1051408580 482845431 815039054 739315855 344364395 451514887 233614746 76085943 ...
result:
ok 249999 numbers
Subtask #8:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%