P13719 [GCPC 2024] Dark Alley

在一个寒冷而有雾的夜晚，你走在一条阴暗的小巷里。 每隔几米应该有一盏路灯，但似乎没有一盏能亮起，在这个夜晚，连月亮都无法照亮你的路。 孤身一人在黑暗中，你不禁思考： “即使某处有一盏亮着的灯，它能照亮我多少路呢？” 现在，回到家中，你想要计算这个问题。  :::align{center} 雾蒙蒙的小巷。[照片来自 Henryk Niestrój](https://pixabay.com/de/photos/park-in-der-nacht-dunkle-stra%C3%9Fe-4270765/) ::: 这条小巷可以被建模为一条长度为 $n$ 米的直线。 雾的密度是均匀的，每经过 $1$ 米，雾会使灯光衰减 $1-p$ 倍。 某一点的亮度等于所有灯光到达该点的光强之和。 你需要在放置一些灯之后，计算某些点的亮度。

输入包括： - 一行，包含两个整数 $n$ 和 $q$，以及一个实数 $p$（$1\leq n, q\leq 2\cdot10^5, 0 < p < 1$），分别表示小巷的长度、查询次数和雾的密度。雾的密度 $p$ 最多有 $6$ 位小数。 - 接下来 $q$ 行，每行包含以下三种查询之一： 1. “$\texttt{+ b x}$” 给定两个整数 $b$ 和 $x$（$1\leq b \leq 10^9$ 且 $1\leq x \leq n$），表示在位置 $x$ 放置一个亮度为 $b$ 的灯。 2. “$\texttt{- b x}$” 给定两个整数 $b$ 和 $x$（$1\leq b \leq 10^9$ 且 $1\leq x \leq n$），表示移除在位置 $x$ 上亮度为 $b$ 的灯。保证之前在该位置放置过该亮度的灯。 3. “$\texttt{? x}$” 给定一个整数 $x$（$1\leq x \leq n$），询问位置 $x$ 的亮度。

可以证明，亮度可以表示为一个分数 $\frac{P}{Q}$，其中 $Q$ 不会被 $10^9+7$ 整除。对于每个“$\texttt{?}$”类型的查询，输出 $P\cdot Q^{-1} \bmod 10^9+7$，每个答案占一行。

在第一个样例中，放置灯后小巷各点的亮度如下表所示： | $3$ | $4$ | $3$ | $2.25$ | $1.6875$ | |:-:|:-:|:-:|:-:|:-:| 由 ChatGPT 4.1 翻译