seuOJ524 - 山

题目描述

我曾踏足山巅，也曾进入低谷，二者都让我受益良多。

nn 座山从高到低排成了一条直线，这就是进入低谷的路；不过，现在并不是进入低谷的时候，你可以改变山的高度！！！

在每次操作中：

在任何时间，任何地点都有可能陷入低谷。所以请问，在给定 kk 的情况下，对于山的某个区间 ll 到 rr 来说，使得这个区间内的所有山的高度单调不减的操作次数最少是多少。

形式化地来说，给你一个长度为 nn 的单调不增序列 aa，在每次操作中，你可以选择一个位置 i(1≤i≤n)i(1\le i\le n)，使得 ai=ai×ka_i=a_i\times k。那么在给定 kk 的情况下，使得序列 aa 的某个子段 [al,…,ar][a_l,\dots,a_r] 单调不减的操作次数最小值是多少。

输入格式

第一行，一个整数 t(1≤t≤104)t(1\le t\le 10^4)，代表数据组数。

对于每组数据：

第一行，三个整数 n,q,b(2≤n≤5⋅105;1≤q≤5⋅105;1≤b≤106)n,q,b(2\le n\le 5\cdot 10^5;1\le q\le 5\cdot10^5;1\le b\le 10^6)，代表直线上山的数量，询问次数和表示山的高度时的基数。

接下来一行有 nn 个整数 x1,…,xn(0≤xi≤n)x_1,\dots,x_n(0\le x_i\le n)，代表初始时第 ii 座山的高度 ai=bxia_i=b^{x_i}，保证所有山的高度数组 aa 是单调不增的。

接下来连续的 qq 行，每行三个整数 l,r,k(1≤l<r≤n;2≤k≤109)l,r,k(1\le l<r\le n;2\le k\le 10^9)，代表每次询问的区间范围和询问时的 kk。

保证同一测试点内 nn 的总和和 qq 的总和均不超过 5⋅1055\cdot10^5。

输出格式

对于每次询问，输出一行整数代表使得当前区间内山的高度数组变得单调不减的最少操作次数。

因为本题可能存在一定的精度问题，所以允许选手的答案和标准答案之间有 10−510^{-5} 的相对误差，即假如标准答案为 ansans，选手输出为 outout，那么选手的输出会被认为是正确的当且仅当 ∣ans−out∣ans≤10−5\frac{|ans-out|}{ans}\le 10^{-5}。

样例

输入样例

4
4 2 1
1 3 0 4
1 4 2
2 3 71
2 1 2
1 1
1 2 273
10 6 2
10 10 8 6 2 1 1 1 0 0
1 10 2
1 2 998244353
3 7 4
2 5 31
2 10 33
2 3 12
7 4 99787
6 5 4 3 2 1 0
1 7 2
1 7 99788
1 7 99787
2 6 99786

输出样例

0
0
0
61
0
12
6
28
1
357
21
21
20