Supercomputer - MarisaOJ: Marisa Online Judge

Given an empty sequence

$S$ , perform a series of

$t$ operations, each belonging to one of the following types: - Add an element

$x$ to the end of sequence

$S$ . - Calculate the sum of elements having values within the range

$[a,b]$ . - Rearrange sequence

$S$ in non-decreasing order, then calculate the sum of elements with indices from

$p$ to

$q$ (where

$1 \le p \le q \le |S|$ , and

$|S|$ is the number of elements in sequence

$S$ ). After that, append two elements to the end of sequence

$S$ : one with the value of the element at index

$p$ plus

$1$ , and the other with the value of the element at index

$q$ minus

$1$ . ### Input - The first line consists of a positive integer

$t$ . - The

$i$ -th line among the

$t$ following lines describes the

$i$ -th operation, which is one of three types in the format: Start type

$k$ (

$k$ is either

$1$ or

$2$ or

$3$ ). If it's operation type

$1$ , then it is followed by an integer

$x$ (

$−10^9 ≤ x ≤ 10^9$ ). If it's operation type

$2$ , then it is followed by two integers

$a, b$ (

$−10^9 ≤ a \le b ≤ 10^9$ ). If it's operation type

$3$ , then it is followed by two positive integers

$p, q$ . ### Output - Print the answers for each operation of types

$2$ and

$3$ . ### Constraints - 40% of the tests have

$t \le 1000$ . - 40% of the tests have

$t \le 10^5$ , with no operation of type

$3$ . - 20% of the tests have

$t \le 10^5$ . ### Example Input:

$7 1 5 1 3 1 1 2 2 4 1 2 3 2 3 2 2 4$

Output:

$3 5 10$

Duyên Hải Bắc Bộ 2019 - Khối 11
	Beautiful sequence
	Group
	Supercomputer

Topic

Data structure

Rating

2000

Solution (0)

Solution