{"problem":{"name":"K. Xor and segments","description":{"content":"Дан массив a1, a2, ..., an, каждое ai равняется 0 или 1. Напишите программу, которая умеет выполнять две операции:  В первой строке записаны числа n и q (1 ≤ n, q ≤ 250 000). Во второй строке записа","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10157K"},"statements":[{"statement_type":"Markdown","content":"Дан массив a1, a2, ..., an, каждое ai равняется 0 или 1. Напишите программу, которая умеет выполнять две операции: \n\nВ первой строке записаны числа n и q (1 ≤ n, q ≤ 250 000).\n\nВо второй строке записаны n чисел a1, a2, ..., an, каждое из этих чисел равно 0 или 1.\n\nВ следующих q строках расположены параметры запросов. В i-й из этих строк записаны параметры i-го запроса — числа ti, li и ri, где ti равно 1 для запроса первого типа (замена чисел в массиве) и 2 для запроса второго типа (нахождение суммы), а li и ri, 1 ≤ li ≤ ri ≤ n есть параметры соответствующего запроса.\n\nДля каждого запроса второго типа выведите в отдельной строке единственное число — ответ на соответствующий запрос.\n\n## Входные Данные\n\nВ первой строке записаны числа n и q (1 ≤ n, q ≤ 250 000).Во второй строке записаны n чисел a1, a2, ..., an, каждое из этих чисел равно 0 или 1.В следующих q строках расположены параметры запросов. В i-й из этих строк записаны параметры i-го запроса — числа ti, li и ri, где ti равно 1 для запроса первого типа (замена чисел в массиве) и 2 для запроса второго типа (нахождение суммы), а li и ri, 1 ≤ li ≤ ri ≤ n есть параметры соответствующего запроса.\n\n## Выходные Данные\n\nДля каждого запроса второго типа выведите в отдельной строке единственное число — ответ на соответствующий запрос.\n\n## Пример\n\nВходные данные5 100 0 0 0 01 2 42 2 22 1 12 1 22 2 31 3 52 2 22 3 32 2 42 1 5Выходные данные01111111\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, q \\in \\mathbb{Z} $ with $ 1 \\leq n, q \\leq 250{,}000 $.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a binary sequence where $ a_i \\in \\{0, 1\\} $ for all $ i \\in \\{1, \\dots, n\\} $.  \n\nLet $ Q = \\{(t_j, l_j, r_j) \\mid j \\in \\{1, \\dots, q\\}\\} $ be a sequence of queries, where for each query:  \n- $ t_j \\in \\{1, 2\\} $: type of operation,  \n- $ l_j, r_j \\in \\mathbb{Z} $: range bounds with $ 1 \\leq l_j \\leq r_j \\leq n $.  \n\n**Constraints**  \n1. $ 1 \\leq n, q \\leq 250{,}000 $  \n2. $ a_i \\in \\{0, 1\\} $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. $ 1 \\leq l_j \\leq r_j \\leq n $ for all $ j \\in \\{1, \\dots, q\\} $  \n\n**Objective**  \nFor each query $ j \\in \\{1, \\dots, q\\} $:  \n- If $ t_j = 1 $: update $ a_i \\leftarrow 1 - a_i $ for all $ i \\in \\{l_j, \\dots, r_j\\} $.  \n- If $ t_j = 2 $: compute and output $ \\sum_{i=l_j}^{r_j} a_i $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10157K","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}