Enter | Register
- Home
- Top
- Catalog
- Contests
- Gym
- Problemset
- Groups
- Rating
- Edu
- API
- Calendar
- Help
| Codeforces Round 665 (Div. 2) |
|---|
| Finished |
→ Virtual participation
Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.
→ Problem tags
binary search
bitmasks
data structures
*2400
No tag edit access
→ Contest materials
- Announcement (en)
- Tutorial (en)
- Problems
- Submit
- Status
- Standings
- Custom test
F. Reverse and Swap
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
You are given an array $$$a$$$ of length $$$2^n$$$. You should process $$$q$$$ queries on it. Each query has one of the following $$$4$$$ types:
- $$$Replace(x, k)$$$— change $$$a_x$$$ to $$$k$$$;
- $$$Reverse(k)$$$— reverse each subarray $$$[(i-1) \cdot 2^k+1, i \cdot 2^k]$$$ for all $$$i$$$ ($$$i \ge 1$$$);
- $$$Swap(k)$$$— swap subarrays $$$[(2i-2) \cdot 2^k+1, (2i-1) \cdot 2^k]$$$ and $$$[(2i-1) \cdot 2^k+1, 2i \cdot 2^k]$$$ for all $$$i$$$ ($$$i \ge 1$$$);
- $$$Sum(l, r)$$$— print the sum of the elements of subarray $$$[l, r]$$$.
Write a program that can quickly process given queries.
Input
The first line contains two integers $$$n$$$, $$$q$$$ ($$$0 \le n \le 18$$$; $$$1 \le q \le 10^5$$$)— the length of array $$$a$$$ and the number of queries.
The second line contains $$$2^n$$$ integers $$$a_1, a_2, \ldots, a_{2^n}$$$ ($$$0 \le a_i \le 10^9$$$).
Next $$$q$$$ lines contains queries— one per line. Each query has one of $$$4$$$ types:
- "$$$1$$$ $$$x$$$ $$$k$$$" ($$$1 \le x \le 2^n$$$; $$$0 \le k \le 10^9$$$)— $$$Replace(x, k)$$$;
- "$$$2$$$ $$$k$$$" ($$$0 \le k \le n$$$)— $$$Reverse(k)$$$;
- "$$$3$$$ $$$k$$$" ($$$0 \le k < n$$$)— $$$Swap(k)$$$;
- "$$$4$$$ $$$l$$$ $$$r$$$" ($$$1 \le l \le r \le 2^n$$$)— $$$Sum(l, r)$$$.
It is guaranteed that there is at least one $$$Sum$$$ query.
Output
Print the answer for each $$$Sum$$$ query.
Examples
Input
2 37 4 9 91 2 83 14 2 4
Output
24
Input
3 87 0 8 8 7 1 5 24 3 72 13 24 1 62 31 5 164 8 83 0
Output
29221
Note
In the first sample, initially, the array $$$a$$$ is equal to $$$\{7,4,9,9\}$$$.
After processing the first query. the array $$$a$$$ becomes $$$\{7,8,9,9\}$$$.
After processing the second query, the array $$$a_i$$$ becomes $$$\{9,9,7,8\}$$$
Therefore, the answer to the third query is $$$9+7+8=24$$$.
In the second sample, initially, the array $$$a$$$ is equal to $$$\{7,0,8,8,7,1,5,2\}$$$. What happens next is:
- $$$Sum(3, 7)$$$ $$$\to$$$ $$$8 + 8 + 7 + 1 + 5 = 29$$$;
- $$$Reverse(1)$$$ $$$\to$$$ $$$\{0,7,8,8,1,7,2,5\}$$$;
- $$$Swap(2)$$$ $$$\to$$$ $$$\{1,7,2,5,0,7,8,8\}$$$;
- $$$Sum(1, 6)$$$ $$$\to$$$ $$$1 + 7 + 2 + 5 + 0 + 7 = 22$$$;
- $$$Reverse(3)$$$ $$$\to$$$ $$$\{8,8,7,0,5,2,7,1\}$$$;
- $$$Replace(5, 16)$$$ $$$\to$$$ $$$\{8,8,7,0,16,2,7,1\}$$$;
- $$$Sum(8, 8)$$$ $$$\to$$$ $$$1$$$;
- $$$Swap(0)$$$ $$$\to$$$ $$$\{8,8,0,7,2,16,1,7\}$$$.
"); $(this).append($copy); const clipboard = new Clipboard('#' + cpyId, { text: function (trigger) { const pre = document.querySelector('#' + preId); const lines = pre.querySelectorAll(".test-example-line"); return Codeforces.filterClipboardText(pre.innerText, lines.length); } }); const isInput = $(this).parent().hasClass("input"); clipboard.on('success', function (e) { if (isInput) { Codeforces.showMessage("The example input has been copied into the clipboard"); } else { Codeforces.showMessage("The example output has been copied into the clipboard"); } e.clearSelection(); }); }); $(".test-form-item input").change(function () { addPendingSubmissionMessage($($(this).closest("form")), "You changed the answer, do not forget to submit it if you want to save the changes"); const index = $(this).closest(".problemindexholder").attr("problemindex"); let test = ""; $(this).closest("form input").each(function () { const test_ = $(this).attr("name"); if (test_ && test_.substring(0, 4) === "test") { test = test_; } }); if (index.length > 0 && test.length > 0) { const indexTest = index + "::" + test; window.changedTests.add(indexTest); } }); $(window).on('beforeunload', function () { if (window.changedTests.size > 0) { return 'Dialog text here'; } }); autosize($('.test-explanation textarea')); $(".test-example-line").hover(function() { $(this).attr("class").split(" ").forEach((clazz) => { if (clazz.substr(0, "test-example-line-".length) === "test-example-line-") { let end = clazz.substr("test-example-line-".length); if (end !== "even" && end !== "odd" && end !== "0") { let top = 1E20; let left = 1E20; let problem = $(this).closest(".problemindexholder"); $(this).closest(".input").find("." + clazz).css("background-color", "#FFFDE7").each(function() { top = Math.min(top, $(this).offset().top); left = Math.min(left, $(this).offset().left); }); let testCaseMarker = problem.find(".testCaseMarker_" + end); if (testCaseMarker.length === 0) { const html = "
"; problem.append($(html)); testCaseMarker = problem.find(".testCaseMarker_" + end); } if (testCaseMarker) { testCaseMarker.show() .offset({top, left: left - 20}) .text(end); } } } }); }, function() { $(this).attr("class").split(" ").forEach((clazz) => { if (clazz.substr(0, "test-example-line-".length) === "test-example-line-") { let end = clazz.substr("test-example-line-".length); if (end !== "even" && end !== "odd" && end !== "0") { $("." + clazz).css("background-color", ""); $(this).closest(".problemindexholder").find(".testCaseMarker_" + end).hide(); } } }); }); });
