QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#424844#5022. 【模板】线段树APJifengc31 2613ms15392kbC++142.3kb2024-05-29 18:53:352024-05-29 18:53:35

Judging History

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

  • [2024-05-29 18:53:35]
  • 评测
  • 测评结果:31
  • 用时:2613ms
  • 内存:15392kb
  • [2024-05-29 18:53:35]
  • 提交

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%