ამოხსნების სტატუსი

ამ გვერდზე თქვენ იხილავთ გაგზავნილი ამოხსნების სტატუსს.


გაგზავნის თარიღი: 26.03.2020 22:22:25

ამოცანა: ლუწკენტობა ინტერვალზე

მომხმარებელი: jolskey

ვერდიქტი: სრული ამოხსნა

შეფასება: 100.0 ქულა







#include <bits/stdc++.h>
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
//typedef tree<int,null_type,less_equal<int>,rb_tree_tag,
//tree_order_statistics_node_update> indexed_multiset;
#define all(x) (x).begin(),(x).end()
#define endl '\n'
//#define int long long


array<int, 2> t[(int)1e6 + 5];
void update(int v, int l, int h, int p, int val) {
        if (l == h) {
                t[v][val % 2] = 1;
                t[v][1 - (val % 2)] = 0;
        } else {
                int m = (l + h) / 2;
                if (p <= m)
                        update(2 * v, l, m, p, val);
                else
                        update(2 * v + 1, m + 1, h, p, val);

                t[v][0] = t[2 * v][0] + t[2 * v + 1][0];
                t[v][1] = t[2 * v][1] + t[2 * v + 1][1];
        }
}


array<int, 2> que(int v, int l, int h, int ql, int qh) {
        if (ql > h || qh < l)
                return {0, 0};

        if (l >= ql && h <= qh)
                return t[v];

        int m = (l + h) / 2;
        array<int, 2> a = que(2 * v, l, m, ql, qh);
        array<int, 2> b = que(2 * v + 1, m + 1, h, ql, qh);
        a[0] += b[0]; a[1] += b[1];
        return a;
}

signed main() { //[J][O][L][S][K][E][Y]
        ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//        freopen("input.txt", "r", stdin);
        int n; cin >> n;
        for (int i = 1; i <= n; i++) {
                int a; cin >> a;
                update(1, 1, n, i, a);
        }

        int q; cin >> q;
        while (q--) {
                int ty, l, h; cin >> ty >> l >> h;
                if (ty == 0) {
                        update(1, 1, n, l, h);
                } else {
                        ty--;
                        cout << que(1, 1, n, l, h)[ty] << ' ';
                }
        }
        return 0;
}

/*

*/

ტესტები

შემავალი მონაცემები
10
96 42 61 93 82 86 44 67 41 3
5
2 1 5
2 7 9
0 1 22
1 5 7
1 1 10
გამომავალი მონაცემები
2
2
3
5
თქვენი პასუხი
2 2 3 5 
ჩეკერის პასუხი
YES
შემავალი მონაცემები
30
1 6 29 97 47 6 76 7 51 11 1 69 30 51 48 54 38 33 89 73 45 54 26 11 15 46 39 25 53 14 
10
0 7 5
1 4 16
2 3 25
0 29 23
2 6 13
2 19 25
2 7 15
0 1 25
1 1 16
0 1 24
გამომავალი მონაცემები
4
16
6
5
7
5
თქვენი პასუხი
4 16 6 5 7 5 
ჩეკერის პასუხი
YES
შემავალი მონაცემები
100
259 643 961 593 831 828 219 221 201 501 981 109 668 249 138 91 51 856 217 66 612 871 51 641 799 25 196 859 777 951 181 693 553 561 215 812 585 685 801 79 852 927 246 308 597 431 353 851 466 321 942 41 73 595 461 72 700 465 754 161 301 617 139 997 91 1...
გამომავალი მონაცემები
8
17
2
10
3
6
15
21
14
16
6
4
7
31
12
14
9
26
თქვენი პასუხი
8 17 2 10 3 6 15 21 14 16 6 4 7 31 12 14 9 26 
ჩეკერის პასუხი
YES
შემავალი მონაცემები
1000
273 117 213 926 311 571 721 908 311 883 131 373 896 237 281 327 461 773 434 421 897 489 47 566 641 161 497 371 1 571 873 403 428 257 311 369 201 85 491 759 710 501 237 865 580 58 253 841 141 896 178 776 201 129 67 841 822 825 322 941 123 335 141 313 ...
გამომავალი მონაცემები
204
11
130
143
281
316
276
61
76
174
3
26
116
210
75
184
38
129
655
353
199
301
58
362
1
0
320
51
73
205
148
89
140
100
470
497
137
19
108
220
68
25
133
326
388
15
65
47
65
561
90
189
271
8
193
145
17...
თქვენი პასუხი
204 11 130 143 281 316 276 61 76 174 3 26 116 210 75 184 38 129 655 353 199 301 58 362 1 0 320 51 73 205 148 89 140 100 470 497 137 19 108 220 68 25 133 326 388 15 65 47 65 561 90 189 271 8 193 145 175 41 278 472 122 15 59 116 258 111 55 7 55 20 3 117 29 2...
ჩეკერის პასუხი
YES
შემავალი მონაცემები
5000
4881 9155 2597 9601 5656 5681 2181 8369 9337 6241 3546 9930 4971 8859 6705 2976 6125 5745 6290 2676 4987 6708 9526 1156 6093 9169 683 8771 217 5209 8706 7457 7949 6843 7701 9141 4327 5001 9844 2749 9851 3897 5533 2913 7020 2084 1721 821 2268 9441 202...
გამომავალი მონაცემები
127
155
340
645
318
668
112
1563
1071
202
220
159
3264
100
514
2490
218
745
313
656
493
572
672
710
871
775
317
2414
2436
665
416
948
641
1354
225
299
145
692
907
83
242
659
520
927
1968
260
2276
27
180
144
...
თქვენი პასუხი
127 155 340 645 318 668 112 1563 1071 202 220 159 3264 100 514 2490 218 745 313 656 493 572 672 710 871 775 317 2414 2436 665 416 948 641 1354 225 299 145 692 907 83 242 659 520 927 1968 260 2276 27 180 144 55 745 177 476 2008 1756 455 104 2227 6 815 2220 ...
ჩეკერის პასუხი
YES
შემავალი მონაცემები
15000
65647 3725 8831 98229 36176 92419 19245 36971 96671 3077 24106 63281 94149 44101 53209 60425 88085 65491 48471 66695 44089 71768 93579 95681 99047 48704 42771 88880 87379 61593 39809 66106 61681 321 70697 20921 78276 95991 89087 11821 91274 84795 50...
გამომავალი მონაცემები
125
1481
2651
2381
2216
6168
77
3073
1738
3492
1183
906
3028
823
574
5697
334
5845
1408
564
1639
2414
3863
107
1
1122
7986
7644
1116
353
64
632
2147
4533
4027
3545
4582
1174
3268
2757
207
928
2860
1458
7005
1358...
თქვენი პასუხი
125 1481 2651 2381 2216 6168 77 3073 1738 3492 1183 906 3028 823 574 5697 334 5845 1408 564 1639 2414 3863 107 1 1122 7986 7644 1116 353 64 632 2147 4533 4027 3545 4582 1174 3268 2757 207 928 2860 1458 7005 1358 1186 186 8674 538 176 9505 1971 2717 4604 35...
ჩეკერის პასუხი
YES
შემავალი მონაცემები
35000
95981 51245 98735 52329 22769 14801 16334 37331 63781 51639 97918 43233 82345 2192 21971 41331 38235 2894 90216 26265 20119 29199 6561 74129 33423 5901 99155 55083 43993 30335 19227 65493 95761 44737 76781 11226 97271 54425 97261 29505 17234 67225 9...
გამომავალი მონაცემები
107
231
5899
18020
2035
3159
278
8338
593
306
88
20565
575
15607
97
2091
964
8541
7173
6103
15832
24964
10910
5731
23696
208
16116
3981
3327
4122
3557
507
4004
4264
2086
194
16739
14464
2336
4991
4683
102
3314
133...
თქვენი პასუხი
107 231 5899 18020 2035 3159 278 8338 593 306 88 20565 575 15607 97 2091 964 8541 7173 6103 15832 24964 10910 5731 23696 208 16116 3981 3327 4122 3557 507 4004 4264 2086 194 16739 14464 2336 4991 4683 102 3314 13366 1090 1550 19711 19219 3396 3771 4136 633...
ჩეკერის პასუხი
YES
შემავალი მონაცემები
50000
3374 57409 50031 45033 88537 96107 53103 46980 23161 39197 11534 70001 46975 35501 18157 61247 45441 1026 26433 45637 12633 93969 13361 41533 62241 33953 87837 68225 67521 84679 32676 95073 96057 42321 81219 10440 14177 62765 4186 72467 98348 60816 ...
გამომავალი მონაცემები
304
4023
8758
5422
15257
7973
1
10381
3544
8959
1326
25050
7812
648
24521
21625
13527
8918
681
1238
1246
491
15651
2113
8544
5339
3575
9140
2707
18607
796
4690
13138
2761
24207
8484
3096
5010
10986
1806
8029
4998
9...
თქვენი პასუხი
304 4023 8758 5422 15257 7973 1 10381 3544 8959 1326 25050 7812 648 24521 21625 13527 8918 681 1238 1246 491 15651 2113 8544 5339 3575 9140 2707 18607 796 4690 13138 2761 24207 8484 3096 5010 10986 1806 8029 4998 9625 10264 305 7139 2715 8472 17591 2580 64...
ჩეკერის პასუხი
YES
შემავალი მონაცემები
75000
43731 44565 83494 42011 20441 74441 54337 24645 28401 34485 45792 1311 36661 40233 84851 47591 97201 39222 36895 64769 32832 15015 14907 38607 86972 58892 30433 67041 64437 44061 8703 56571 40401 10136 73926 11581 24665 19225 88137 90449 63945 50049...
გამომავალი მონაცემები
160
6811
3042
4026
10054
17502
7387
6478
5862
14986
15478
9604
16242
21028
13285
5250
2603
710
1284
11473
4265
22992
9008
982
9601
1101
22604
8717
3113
2228
31512
4445
10889
5103
22357
49072
8716
7548
1280
8424
2968
...
თქვენი პასუხი
160 6811 3042 4026 10054 17502 7387 6478 5862 14986 15478 9604 16242 21028 13285 5250 2603 710 1284 11473 4265 22992 9008 982 9601 1101 22604 8717 3113 2228 31512 4445 10889 5103 22357 49072 8716 7548 1280 8424 2968 10815 6584 15887 13110 39215 2889 379 16...
ჩეკერის პასუხი
YES
შემავალი მონაცემები
95000
93910 97665 37949 83593 8661 8611 35501 76876 72411 13291 71043 29381 4691 29973 71287 11961 66513 53717 74014 9053 44356 20721 45209 12384 98619 97251 39342 56713 26538 56641 58445 29655 62337 93321 41367 5921 33603 3386 67817 47353 24769 14958 110...
გამომავალი მონაცემები
3606
13838
3944
51080
1010
5762
54478
1248
2805
2337
32535
49012
647
9763
4028
10734
3001
4729
3808
3152
1910
20754
18094
54115
56109
2715
18212
41263
9806
6158
15926
2665
9058
6049
31036
2477
49237
28602
9637
11262
...
თქვენი პასუხი
3606 13838 3944 51080 1010 5762 54478 1248 2805 2337 32535 49012 647 9763 4028 10734 3001 4729 3808 3152 1910 20754 18094 54115 56109 2715 18212 41263 9806 6158 15926 2665 9058 6049 31036 2477 49237 28602 9637 11262 43698 5165 6509 1230 10356 6601 6143 387...
ჩეკერის პასუხი
YES