视频倍增期 - 题目

题目描述

为了更好地衡量视频质量，快手的产品经理提出了视频的“倍增期”的概念。倍增期是一个以秒为单位的时间量指标，其含义是视频的累计播放量从只有目前的一半到当前总播放量所耗费的时长。低质量的视频往往高开低走，刚发布时人们出于好奇或者是被标题吸引而点击，一段时间之后口碑断崖式滑坡，所以倍增期很长；高质量的视频则往往低开高走，人们看过之后自发传播和推荐，逐渐积攒起口碑和流量，所以倍增期较短。

小张是快手的一位视频后台管理员，有 $n$ 个视频是由小张负责监控的，从 $1$ 到 $n$ 依次编号。小张的一周有 $m$ 秒钟的工作时间，在每秒钟都会有一个需要处理的请求从前台传来，请求分成两种：

更新请求：在这一秒钟内，编号在区间 $[l, r]$ 内的视频均获得了 $x$ 次的播放量，需要更新后台的数据；
查询请求：前台希望知道编号为 $i$ 的视频的倍增期。设该视频本周当前的累计播放量为 $x$，该查询请求是第 $j$ 秒传来的，该视频本周的累计播放量恰好达到 $\lceil x / 2 \rceil$ 时是在第 $j'$ 秒（$j' \ge 0$），则倍增期被定义为 $j - j'$。

面对如此高频度的信息更新和查询需求，小张感到有些棘手，他希望能得到你的帮助。

输入格式

输入的第一行包含两个正整数 $n$ 和 $m$，保证 $1 \le n, m \le 10^5$。

接下来 $m$ 行，第 $j$ 行表示第 $j$ 秒的请求（$1 \le j \le m$），其格式为以下两种之一：

$0 \ l \ r \ x$：表示这是一个更新请求，在第 $j$ 秒，编号在区间 $[l, r] (1 \le l \le r \le n)$ 内的视频获得了 $x$ 次播放量，保证 $1 \le x \le 10^8$；
$1 \ i$：表示这是一个查询请求，查询编号为 $i (1 \le i \le n)$ 的视频在第 $j$ 秒的倍增期。

输出格式

对于每一个查询请求，依次输出一行，表示所查询的倍增期。

样例数据

样例 1 输入

样例 1 输出

2
1
4

样例 1 解释

第 $2$ 秒时，$4$ 号视频的累计播放量为 $0$，在第 $0$ 秒时达到了 $\lceil 0 / 2 \rceil = 0$ 秒的累计播放量，所以此时 $4$ 号视频的倍增期为 $2$ 秒。
第 $4$ 秒时，$4$ 号视频的累计播放量为 $3$，在第 $3$ 秒时达到了 $\lceil 3 / 2 \rceil = 2$ 秒的累计播放量，所以此时 $4$ 号视频的倍增期为 $1$ 秒。
第 $5$ 秒时，$3$ 号视频的累计播放量为 $6$，在第 $1$ 秒时达到了 $\lceil 6 / 2 \rceil = 3$ 秒的累计播放量，所以此时 $3$ 号视频的倍增期为 $4$ 秒。

QOJ.ac

QOJ