Description

To better measure video quality, Kuaishou’s product manager proposed the concept of a video “doubling period”. The doubling period is a time metric measured in seconds. It means the time it takes for a video’s cumulative views to increase from only half of the current value to the current total views. Low-quality videos often start strong but fade quickly: right after release, people click out of curiosity or because the title is attractive, but after some time the reputation drops sharply, so the doubling period is long. High-quality videos often start slow but grow later: after watching, people share and recommend it on their own, gradually building reputation and traffic, so the doubling period is shorter.

Xiaozhang is a backend administrator at Kuaishou. There are $n$ videos monitored by Xiaozhang, numbered from $1$ to $n$. Xiaozhang has $m$ seconds of work time in a week. Each second, there is one request from the frontend to be processed. Requests are of two types:

• Update request: during this second, all videos with indices in the interval $[l, r]$ gain $x$ views, and the backend data needs to be updated.
• Query request: the frontend wants to know the doubling period of video $i$. Suppose the current cumulative views of this video in this week is $x$, and this query is sent at second $j$. Let $j'$ be the second when the cumulative views of this video in this week first reaches $\lceil x / 2 \rceil$ (with $j' \ge 0$). Then the doubling period is defined as $j - j'$.

Faced with such frequent updates and queries, Xiaozhang finds it difficult and hopes for your help.

Input Format

The first line contains two positive integers $n$ and $m$, with $1 \le n, m \le {10}^5$.

The next $m$ lines describe the requests. Line $j$ represents the request at second $j$ ($1 \le j \le m$), and is in one of the following formats:

• $0 \ l \ r \ x$: this is an update request. At second $j$, videos with indices in $[l, r]$ ($1 \le l \le r \le n$) each gain $x$ views. It is guaranteed that $1 \le x \le {10}^8$.
• $1 \ i$: this is a query request. Query the doubling period of video $i$ ($1 \le i \le n$) at second $j$.

Output Format

For each query request, output one line in order, giving the requested doubling period.

5 5
0 2 3 3
1 4
0 2 4 3
1 4
1 3

2
1
4

Hint

Sample Explanation

• At second $2$, the cumulative views of video $4$ is $0$. It reached the cumulative views $\lceil 0 / 2 \rceil = 0$ at second $0$, so its doubling period at this time is $2$ seconds.
• At second $4$, the cumulative views of video $4$ is $3$. It reached the cumulative views $\lceil 3 / 2 \rceil = 2$ at second $3$, so its doubling period at this time is $1$ second.
• At second $5$, the cumulative views of video $3$ is $6$. It reached the cumulative views $\lceil 6 / 2 \rceil = 3$ at second $1$, so its doubling period at this time is $4$ seconds.

Source

From the 2021 Tsinghua University Programming Contest and Collegiate Invitational (THUPC2021).

Resources such as editorial(s) can be found at https://github.com/yylidiw/thupc_0/tree/master.

Translated by ChatGPT 5