Seaside Streaming
本题没有可用的提交语言。
Description
On a serene seaside, jellyfish communicate with the shore using unique pulsating signals. These signals are of two types:
- A Type 0 signal represents a jellyfish sending a pulsation intensity of value $v (0\leq v\leq 10^9)$ from a specific location $x (1\leq x\leq 10^9)$ in the sea. Note that a pulsation with intensity $0$ still counts as a pulsation.
- A Type 1 signal is a call from the marine researchers on the shore. They want to detect sequences of jellyfish pulsations within a specific section of the sea, defined by the interval $[l, r] (1 \leq l \leq r \leq 10^9)$. Formally, a luminous dance is a sequence of pulsations that is continuous and has an intensity of $$\sum_{x \in [i, j]} v_x$$ if Type 0 signals have been sent from all points in $[i, j]$ and no pulsations were detected at point $i-1$ and point $j+1$. Researchers want to know how many luminous dances are completely contained in the given range, and what the total intensity of all these dances is. If no such luminous dance can be found in the specified section, the researchers note a value of $-1$ for both values.
The first line contains $N (1\leq N\leq 2\cdot 10^5)$, the number of jellyfish signals received by the shore.
The next $N$ lines describe each of these signals:
- 0 x v - This represents a Type 0 signal, where a jellyfish at location $x$ in the sea sends a pulsation with intensity $v$.
- 1 l r - This represents a Type 1 signal, where the marine researchers wish to decode the sum of all continuous sequence of jellyfish pulsations between the sea locations $l$ and $r$, and the number of those sequences.
It's also guaranteed that all $x$ are distinct.
For each type 1 query, print the answer on a new line. Print the number of continuous luminous dances, followed by a space, and then the intensity (sum) of all the luminuous dance intensities that are continuous for the interval $[l, r]$.
Input
The first line contains $N (1\leq N\leq 2\cdot 10^5)$, the number of jellyfish signals received by the shore.
The next $N$ lines describe each of these signals:
- 0 x v - This represents a Type 0 signal, where a jellyfish at location $x$ in the sea sends a pulsation with intensity $v$.
- 1 l r - This represents a Type 1 signal, where the marine researchers wish to decode the sum of all continuous sequence of jellyfish pulsations between the sea locations $l$ and $r$, and the number of those sequences.
It's also guaranteed that all $x$ are distinct.
Output
For each type 1 query, print the answer on a new line. Print the number of continuous luminous dances, followed by a space, and then the intensity (sum) of all the luminuous dance intensities that are continuous for the interval $[l, r]$.
6
0 1 2
1 1 4
0 3 4
1 1 4
0 2 3
1 1 4
3
0 1 1
0 2 1
1 1 1
10
0 10 68
1 3 9
1 3 4
0 3 9
1 1 8
0 4 70
0 9 35
1 1 8
0 2 55
0 1 1
1 2
2 6
1 9
-1 -1
-1 -1
-1 -1
1 9
1 79
Note
For the first sample, let's denote the first 5 elements by index [1, 2, 3, 4, 5]. Then, the state after each 0 query will be:
- [2, 0, 0, 0, 0]
- [2, 0, 4, 0, 0]
- [2, 3, 4, 0, 0]
For the first query, we can see that there is one dance with intensity 2, so we print out 1 2
For the second query, we can see that there are two dances with total intensity 6, so we print out 2 6
For the third query, since dance $[2, 3, 4]$ is fully contained, but now there is one continuous dance, so we print 1 9