QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#233951 | #5022. 【模板】线段树 | FISHER_ | 8 | 4ms | 6040kb | C++14 | 2.0kb | 2023-11-01 10:34:15 | 2023-11-01 10:34:15 |
answer
#include <bits/stdc++.h>
using namespace std;
const int maxn = 250000, B = 511, C = 500;
int a[maxn + 5];
int ed[C + 5][B + 5];
int tg[C + 5];
int bg[C + 5][B + 5];
int bl[maxn + 5];
int lp[C + 5], rp[C + 5];
int t[B + 5];
void rebuild(int id) {
for (int j = 0; j <= 2; j++)
if ((tg[id] >> j) & 1)
for (int i = rp[id]; i >= lp[id]; i--) a[i] ^= a[i - (1 << j)];
memset(t, 0, sizeof(t));
for (int i = 1; i <= tg[id]; i++) t[tg[i] - i] = bg[id][i];
for (int i = 1; i <= B; i <<= 1)
for (int j = 0; j <= B; j += (i << 1))
for (int k = 0; k < i; k++) t[j + k] ^= t[i + j + k];
for (int i = lp[id]; i <= rp[id]; i++) a[i] ^= t[i - lp[id]];
tg[id] = 0;
}
void upded(int id) {
memset(t, 0, sizeof(t));
for (int i = lp[id]; i <= rp[id]; i++) t[rp[id] - i] = a[i];
for (int i = 1; i <= B; i <<= 1)
for (int j = 0; j <= B; j += (i << 1))
for (int k = 0; k < i; k++) t[i + j + k] ^= t[j + k];
memcpy(ed[id], t, sizeof(t));
}
int main() {
int n, q;
scanf("%*d%d%d", &n, &q);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i++) bl[i] = (i - 1) / B + 1;
int c = bl[n];
for (int i = 1; i <= c; i++) {
lp[i] = (i - 1) * B + 1, rp[i] = min(i * B, n);
upded(i);
}
for (int i = 1; i <= q; i++) {
int op, x, y;
scanf("%d%d", &op, &x);
if (op == 1) {
scanf("%d", &y);
int lb = bl[x], rb = bl[y];
if (lb == rb) {
rebuild(bl[x]);
for (int j = y; j > x; j--) a[j] ^= a[j - 1];
upded(bl[x]);
} else {
rebuild(lb), rebuild(rb);
for (int j = y; j > lp[rb]; j--) a[j] ^= a[j - 1];
a[lp[rb]] ^= ed[rb - 1][tg[rb - 1]];
for (int j = rb - 1; j > lb; j--) {
bg[j][++tg[j]] = ed[j - 1][tg[j - 1]];
if (tg[j] == B) rebuild(j), upded(j);
}
for (int j = rp[lb]; j > x; j--) a[j] ^= a[j - 1];
upded(lb), upded(rb);
}
} else {
rebuild(bl[x]);
printf("%d\n", a[x]);
}
}
for (int i = 1; i <= c; i++) rebuild(i);
for (int i = 1; i <= n; i++) printf("%d\n", a[i]);
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 8
Accepted
Test #1:
score: 8
Accepted
time: 1ms
memory: 5924kb
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: 6040kb
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: 4ms
memory: 3824kb
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: 4ms
memory: 5984kb
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: 1ms
memory: 5988kb
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
Runtime Error
Test #6:
score: 0
Runtime Error
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
Runtime Error
Test #10:
score: 0
Runtime Error
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
Runtime Error
Test #14:
score: 0
Runtime Error
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: 0
Runtime Error
Test #18:
score: 0
Runtime Error
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:
result:
Subtask #6:
score: 0
Skipped
Dependency #5:
0%
Subtask #7:
score: 0
Skipped
Dependency #5:
0%
Subtask #8:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%