-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path1310_XORQueriesSubarray.py
More file actions
127 lines (123 loc) · 12.3 KB
/
Copy path1310_XORQueriesSubarray.py
File metadata and controls
127 lines (123 loc) · 12.3 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
"""
Given the array arr of positive integers and the array queries where queries[i] = [Li, Ri], for each query i compute the
XOR of elements from Li to Ri (that is, arr[Li] xor arr[Li+1] xor ... xor arr[Ri] ). Return an array containing the
result for the given queries.
"""
from typing import List, Tuple
def xorQueries(arr: List[int], queries: List[Tuple[int, int]]) -> List[int]:
"""
:param arr: array of positive integers
:param queries: list of queries of form [Li, Ri]
:return: return arr[Li] xor arr[Li+1] xor .... xor arr[Ri]
"""
# pre_compute[i] = arr[0] ^ ... ^ arr[i - 1]
# and pre_compute[0] = 0
pre_compute = [0] * (len(arr) + 1)
for i, arr_i in enumerate(arr):
pre_compute[i + 1] = pre_compute[i] ^ arr_i
return [pre_compute[Ri + 1] ^ pre_compute[Li] for Li, Ri in queries]
test_cases = [([1, 3, 4, 8], [(0, 1), (1, 2), (0, 3), (3, 3)], [2, 7, 14, 8]),
([4, 8, 2, 10], [(2, 3), (1, 3), (0, 0), (0, 3)], [8, 0, 4, 4]),
([123590368, 887039577, 950326013, 848125275, 42974945, 201779811, 257304363, 843437225, 630064054,
452059902, 173967478, 124079655, 484159445, 179726595, 731100115, 259223062, 170665637, 798870803,
907332142, 110417326, 467188111, 977925843, 406172122, 865959215, 582961757, 976270471, 878696742,
315705417, 590782505, 272097063, 764086436, 512185692, 337648577, 107512856, 222924498, 700133576,
340823202, 42541888, 29272941, 11280895, 844884439, 993859379, 317344241, 780055968, 640562856,
343867186, 483016894, 420121952, 336382767, 427945350, 67607931, 68925611, 980747211, 340751466,
645798692, 489473791, 119574376, 268502913, 231062011, 843032950, 663365081, 835284838, 956928808,
582948604, 931593268, 738938178, 503499127, 710639308, 382066319, 278191472, 196733926, 581541006,
223163180, 329983542, 213906448, 264549796, 387044831, 87369044, 880443655, 301492451, 96008417,
808835417, 480931370, 97161221, 700090977, 616710306, 690916441, 363873691, 244197059, 419273145,
329407130, 44079526, 351372795, 200588773],
[(40, 90), (74, 83), (31, 52), (12, 81), (78, 80), (31, 45), (2, 33), (51, 55), (34, 69), (9, 18),
(2, 83), (1, 38), (45, 76), (60, 69), (12, 76), (41, 45), (65, 86), (22, 44), (19, 37), (40, 59),
(13, 78), (77, 86), (16, 42), (18, 87), (92, 92), (40, 92), (79, 91), (86, 89), (22, 60), (55, 89),
(20, 26), (91, 93), (31, 47), (8, 65), (55, 90), (32, 66), (56, 90), (58, 58), (50, 71), (21, 54),
(62, 63), (82, 88), (73, 73), (7, 52), (74, 78), (75, 79), (17, 50), (35, 60), (72, 84), (22, 33),
(29, 91), (0, 22), (67, 77), (64, 92), (83, 90), (87, 92), (93, 93), (30, 70), (63, 84), (61, 75),
(91, 92), (43, 78), (78, 86), (82, 85), (6, 15), (65, 85), (47, 57), (65, 89), (26, 65), (38, 82),
(38, 92), (70, 81), (21, 80), (76, 78), (15, 92), (65, 83), (48, 59), (19, 51), (54, 67), (72, 73),
(63, 84), (50, 90), (44, 68), (65, 92), (21, 90), (93, 93), (67, 69), (32, 72), (12, 46), (10, 27),
(78, 80), (56, 71), (48, 75), (50, 60), (41, 69), (16, 78), (27, 42), (55, 93), (68, 81), (15, 52),
(35, 50), (48, 83), (0, 24), (67, 81), (74, 74), (3, 83), (77, 84), (33, 46), (22, 58), (18, 87),
(25, 59), (39, 76), (32, 85), (87, 90), (21, 90), (45, 76), (53, 60), (26, 75), (26, 62), (13, 16),
(15, 87), (1, 70), (37, 80), (92, 92), (9, 73), (47, 83), (39, 66), (64, 85), (45, 93), (67, 77),
(0, 15), (56, 84), (44, 63), (69, 81), (43, 93), (93, 93), (14, 62), (48, 61), (71, 71), (35, 75),
(76, 92), (25, 84), (76, 92), (52, 71), (89, 90), (57, 90), (25, 71), (67, 67), (86, 92), (74, 87),
(51, 72), (79, 88), (93, 93), (63, 86), (31, 71), (83, 87), (80, 80), (52, 92), (19, 69), (34, 88),
(22, 31), (77, 77), (44, 60), (90, 93), (87, 91), (38, 47), (59, 75), (62, 72), (59, 91), (5, 39),
(65, 68), (75, 88), (8, 53), (8, 92), (56, 57), (21, 85), (90, 91), (88, 88), (51, 91), (88, 90),
(77, 86), (26, 93), (26, 56), (42, 59), (8, 17), (89, 93), (84, 89), (59, 91), (71, 72), (21, 59),
(83, 91), (34, 56), (78, 85), (50, 85), (51, 62), (61, 77), (78, 88), (91, 91), (33, 72), (90, 91),
(84, 84), (79, 85), (40, 67), (31, 81), (34, 46), (9, 89), (93, 93), (74, 88), (74, 78), (77, 85),
(58, 91), (20, 37), (17, 73), (46, 65), (51, 66), (14, 40), (91, 93), (39, 43), (13, 42), (50, 70),
(63, 92), (12, 35), (5, 12), (76, 76), (27, 31), (63, 85), (67, 93), (92, 93), (43, 85), (35, 42),
(78, 83), (12, 40), (51, 65), (63, 77), (48, 58), (29, 59), (36, 65), (70, 88), (49, 62), (57, 73),
(42, 73), (75, 78), (27, 37), (5, 6), (0, 61), (40, 64), (74, 83), (25, 76), (20, 39), (3, 4), (49, 58),
(85, 93), (7, 79), (48, 64), (16, 26), (59, 78), (1, 5), (68, 69), (67, 93), (16, 21), (35, 84),
(15, 70), (11, 35), (3, 66), (81, 83), (35, 78), (24, 81), (49, 70), (80, 84), (33, 74), (81, 84),
(31, 34), (75, 93), (22, 66), (54, 92), (89, 93), (81, 89), (7, 52), (70, 83), (68, 74), (91, 93),
(54, 58), (91, 92), (78, 80), (32, 43), (12, 31), (7, 33), (54, 56), (6, 87), (11, 76), (60, 92),
(47, 53), (40, 42), (16, 84), (4, 60), (85, 87), (50, 78), (3, 70), (34, 39), (32, 83), (41, 46),
(38, 40), (49, 52), (93, 93), (40, 87), (16, 49), (48, 55), (86, 90), (12, 66), (31, 63), (71, 77),
(42, 63), (65, 90), (50, 87), (61, 67), (16, 73), (67, 84), (92, 92), (37, 84), (20, 45), (47, 71),
(66, 76), (12, 64), (44, 52), (73, 75), (5, 43), (83, 91), (40, 66), (38, 58), (45, 62), (41, 88),
(66, 82), (1, 68), (15, 34), (40, 86), (41, 91), (41, 77), (8, 65), (35, 65), (58, 81), (48, 53),
(74, 75), (17, 23), (67, 82), (73, 81), (31, 75), (73, 83), (46, 87), (47, 72), (39, 68), (76, 86),
(68, 84), (21, 24), (18, 50), (87, 88), (72, 76), (14, 37), (52, 91), (6, 18), (69, 90), (34, 79),
(13, 39), (33, 37), (80, 89), (67, 87), (10, 19), (27, 49), (65, 92), (55, 56), (75, 86), (62, 80),
(28, 53), (76, 91), (30, 84), (57, 80), (69, 75), (61, 65), (32, 58), (25, 26), (68, 92), (48, 80),
(62, 66), (51, 90), (65, 90), (74, 92), (54, 56), (45, 74), (0, 24), (38, 82), (88, 93), (0, 69),
(15, 53), (65, 93), (40, 89), (69, 89), (73, 90), (36, 69), (52, 86), (66, 79), (77, 86), (57, 76),
(16, 80), (56, 93), (17, 87), (20, 52), (81, 81), (54, 90), (4, 51), (53, 78), (36, 78), (85, 85),
(11, 22), (0, 49), (34, 63), (34, 84), (47, 87), (61, 82), (49, 78), (14, 75), (45, 54), (53, 62),
(2, 24), (33, 56), (16, 91)],
[230817296, 405833548, 175134636, 309248930, 540676357, 945068736, 171356585, 292754129, 621373093,
920788516, 16331314, 226241893, 644890571, 611371609, 122957482, 905519864, 361978530, 654946584,
314742117, 843069334, 717235500, 671897021, 469338490, 768921129, 351372795, 462479949, 193120307,
720205496, 555718474, 433376647, 652846165, 497394104, 1033131806, 612649966, 175544093, 457933903,
391795170, 231062011, 818916095, 153819867, 464946644, 638114797, 329983542, 125816975, 623194168,
945990859, 28419561, 733612023, 795613239, 132914799, 220979674, 644738725, 178499198, 606411440,
838694628, 103857190, 200588773, 267669346, 222723217, 930597958, 374414429, 527374480, 758739177,
337130732, 1037750152, 1019074299, 382905482, 374382659, 600506017, 1026425446, 444754143, 916855569,
507464785, 643723660, 345420340, 835001400, 807547239, 472062591, 833129497, 518395162, 222723217,
36625992, 861282826, 329508484, 56462790, 200588773, 738884915, 320650552, 697347821, 515884392,
540676357, 633021781, 551540984, 438645271, 610997272, 76976618, 673306905, 399718053, 821500142,
981489210, 899197083, 999562752, 927979991, 447505954, 213906448, 945676495, 635476294, 775525603,
883563493, 768921129, 260191291, 889203241, 369088129, 274833531, 56462790, 644890571, 541856780,
625961251, 452483371, 612012643, 118901641, 274274995, 322475605, 351372795, 83140206, 580817760,
982950147, 188426959, 62417845, 178499198, 184083477, 181878114, 172489288, 640861793, 199813309,
200588773, 966725035, 643922904, 581541006, 483249073, 959265860, 764318013, 959265860, 819171119,
190825251, 276487818, 48400650, 710639308, 790507647, 701924429, 965018792, 41783990, 200588773,
11186282, 14080840, 875336452, 96008417, 342091717, 98624056, 900179545, 363102646, 87369044, 540545274,
235404066, 314653149, 57707619, 583155945, 376358050, 253688150, 833166212, 244786294, 736581278,
561344588, 455925800, 388073705, 974299620, 285393724, 244197059, 76143253, 97641952, 671897021,
395765890, 441030576, 992397682, 628676540, 385507995, 664124539, 253688150, 803516322, 1021068352,
861794114, 780319728, 68680880, 996274794, 383931170, 626212045, 906433457, 44079526, 121415417,
285393724, 700090977, 812481975, 274857520, 526432049, 676401403, 995206489, 200588773, 660120206,
623194168, 19061220, 47923373, 341197003, 731875191, 597328548, 835861983, 382601853, 497394104,
895361866, 900677052, 308688497, 110758988, 624099340, 529174829, 387044831, 316435135, 696532019,
710860628, 520435742, 788686119, 637313709, 158283379, 10734763, 802223272, 764657795, 35493905,
806007290, 871591163, 279888124, 191112159, 1014873895, 681599321, 698008616, 851436702, 55627080,
781100883, 137561289, 405833548, 141428859, 356829785, 805495738, 370234174, 2673976, 669127082,
173081144, 869814371, 77345125, 813694333, 105972735, 710860628, 882948970, 775718696, 311379536,
576081451, 999389378, 693446518, 982759997, 1072410414, 199744503, 89609718, 405304543, 15707415,
25576535, 1025324037, 250545657, 978948196, 385507995, 247503629, 125816975, 801563966, 1025021341,
497394104, 565636297, 374414429, 540676357, 344131078, 327754191, 29380006, 1014125235, 901769751,
3235981, 701552091, 983693752, 462206741, 272215295, 653047594, 408717664, 185372637, 472051223,
859413354, 411507778, 691233350, 860447557, 602459037, 200588773, 135273456, 261758519, 419014915,
961489954, 146974080, 4434194, 756037803, 919799321, 99810009, 134167464, 95153279, 565420498,
712381036, 351372795, 332872514, 317063542, 608698678, 294928989, 986390965, 7603446, 282093442,
73079089, 861794114, 976912636, 23925874, 248961564, 885380324, 402964863, 192162853, 829834689,
497049195, 1027247713, 46319445, 612649966, 440949811, 757907909, 598439128, 58409396, 354701626,
101058568, 318463829, 491491302, 194748794, 263377119, 688206362, 101187904, 1058898018, 2976928,
861827195, 774662394, 457073496, 176980337, 629631288, 9593406, 780135952, 191225519, 639785996,
774081193, 876844512, 192439276, 841653004, 713501044, 1010978388, 329508484, 437012887, 819541446,
882918062, 11883628, 769440191, 36817883, 219684637, 605683382, 837966788, 554605139, 242183585,
200350845, 314653046, 507117013, 103367475, 99810009, 978746864, 1014125235, 1051025328, 927979991,
1026425446, 410272856, 482158517, 785326672, 408378209, 509846666, 415728693, 1068255131, 33282239,
307452899, 824413933, 671897021, 672607052, 282460648, 184545370, 38339386, 549637146, 808835417,
738757689, 1020633325, 828746182, 321424117, 616710306, 427646852, 90372642, 210527127, 594872826,
326668385, 704027323, 311255643, 103300515, 342580496, 680323138, 80554350, 686440424, 252991961]), ]
for test_arr, test_queries, expected_output in test_cases:
assert xorQueries(test_arr, test_queries) == expected_output