#H1067. 战骸处理

战骸处理

题目描述

hsez 爆发了魔怔病毒,前线的 Rikka__ 和 ISYRHH 发来捷报,成功摧毁了魔怔始祖 YLCH,不过他们发现 YLCH 遗留了剧毒的魔怔病毒,于是他们向总部的死亡先知 brAKzero 和大魔法师 logfk 发出求助。

brAKzero 通过先知之眼窥探到了魔怔病毒的本质,病毒是一个长为 n n 的整数序列,且存在一个魔怔程度 dd,brAKzero 需要借助大魔法师 logfk 的法力,对病毒进行 mm 次操作,病毒才能得到妥善处理。

操作只有一种,形如:type l r,表示判断病毒序列的下标 llrr 之间的子区间是否可以重新排序成为公比为 dd 的等比数列。

若是,则输出 true,且对这段区间按照大小顺序进行重新排序(type=1type=1 从小到大,type=2type=2 从大到小),否则输出 false​。

输入格式

由于病毒过于复杂,你需要用特殊的方式得到整个序列。

第一行包含三个整数 n,m,dn,m,d

第二行到第 n+1n+1​ 行,每行一个整数 typetype​,若 type=1type=1​​,则直接读入,否则再读入两个整数 x,yx,y​ 表示第 ii​ 个数是第 xx​ 个数乘上 dyd^y​ 的结果。

保证 x<ix<i​,且 type=1type=1 时,输入数据的值小于 10510^5

n+2n+2 行到第 n+m+1n+m+1 行,每行三个整数 type x y,意义见上文。

输出格式

mm 行,每行输出 truefalse 表示每一组操作的答案。

5 5 2 
1 1
1 2
1 4
0 2 2
1 3
1 1 4
2 1 4
1 1 5
1 2 3
1 1 2
true
true
false
true
false

数据规模与约定

对于 10%10\% 的数据,m=0m=0

对于 50%50\% 的数据,1n,m1031\le n,m\le 10^3​;

对于另外 20%20\%​ 的数据,保证数据纯随机;

对于 100%100\% 的数据,1n105,1m1061\le n\le 10^5,1\le m\le 10^6​ 。

保证序列中的所有数字不重复,保证查询中的 xyx\le y

为了卡掉错误的算法,本题需要保证正解的耗时极小,建议写文件快读或者使用 O2/Ofast 优化。