Scribd
Upload
2 views2 pages

Problem - D - Codeforces

The document describes Dura, a Palestinian city with a population of 39,336 as of 2017, and outlines its historical significance. It also presents a programming problem involving an array and two types of queries: range sum and range update, with specific input and output requirements. The problem requires efficient processing of up to 100,000 queries on an array of size up to 100,000.

Uploaded by

riaa1xx
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2 views2 pages

Problem - D - Codeforces

The document describes Dura, a Palestinian city with a population of 39,336 as of 2017, and outlines its historical significance. It also presents a programming problem involving an array and two types of queries: range sum and range update, with specific input and output requirements. The problem requires efficient processing of up to 100,000 queries on an array of size up to 100,000.

Uploaded by

riaa1xx
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Mariamm | Logout

PROBLEMS SUBMIT CODE MY SUBMISSIONS STATUS STANDINGS CUSTOM INVOCATION

D. Dura
time limit per test: 4.5 seconds
memory limit per test: 1024 megabytes

Dura is a Palestinian city located eleven kilometers southwest of Hebron, in the southern West Bank, in the Hebron
Governorate of the State of Palestine. According to the Palestinian Central Bureau of Statistics, the town had a population of
39,336 in 2017. The current mayor is Ahmad Salhoub. Dura is identified with the ancient town of Adoraim, a city of Judah that,
according to the Bible, was fortified by Rehoboam. The town is also mentioned in other ancient texts such as the Amarna
Letters, the Anastasi Papyrus, and the Zenon Papyri. During the Hellenistic period, the town, then also known as Adora.

Let a = [a1 , a2 , … , an ] denote an array of size n .

Let's define f(x, y) = 2(x | y) − (x + y) where | represents the bitwise OR operation.

You are required to process the following types of queries:

1. Range Sum Query: Given indices l and r , compute the sum of the array elements in the segment [l, r]
2. Range Update Query: Given indices l , r , and an integer b , for each i(l ≤ i ≤ r) assign ai := f(ai , b) .

Input
The first line contains integer n(1 ≤ n ≤ 105 ) — the size of the array.
9
The second line contains n space-separated integers a1 , a2 , . . . , an (0 ≤ ai ≤ 10 ) — the original array.

The third line contains an integer q(1 ≤ q ≤ 105 ) — the number of queries, followed by q lines.

The beginning of each of the next q lines contains an integer type(1 ≤ type ≤ 2)

If type = 1 , two intergers l, r(1 ≤ l ≤ r ≤ n) will follow separated by whitespaces.


If type = 2 , three integers l, r, b(1 ≤ l ≤ r ≤ n, 0 ≤ b ≤ 109 ) will follow separated by whitespaces.

Output
For each query of type 1 (Range Sum Query) print in a single line the sum of numbers within the given segment. Print the answers to
the queries in the order in which the queries go in the input.

Examples
input Copy

5
4 10 3 13 7
8
1 2 4
2 1 3 3
1 2 4
1 3 3
2 2 5 5
1 1 5
2 1 2 10
1 2 3

output Copy

26
22
0
34
11

input Copy

10
26 6 27 28 28 19 14 8 0 24

[Link] 11/07/2026, 4 58 AM
Page 1 of 2
:
3
2 7 8 16
1 4 7
2 6 9 10

output Copy

105

Codeforces (c) Copyright 2010-2026 Mike Mirzayanov


The only programming contests Web 2.0 platform
Server time: Jul/11/2026 04:58:17 (f1).
Mobile version, switch to desktop version.
Privacy Policy | Terms and Conditions

Supported by

[Link] 11/07/2026, 4 58 AM
Page 2 of 2
:

You might also like