回复 @Rapiz :
贪心水过的蒟蒻飘过

把最长上升子序列复制粘贴了两遍，改了下符号，就过了。。。。。。

回复 @Hzoi_AntiLeaf :
ysf大神完全可以写树套树主席树吗~~

回复 @紅蓮之心熾熱��_血瞳洞穿無盡陰暗 :
能用zkw过也是种技术
要不然我的zkw早过了......

真是醉了。。
这个题明明是考查我们各种数论的。。前6个点应该线段树维护区间乘积。
后4个点应该处理逆元（前6个点不行，因为p1和p2不一定与我们维护的数互质）
而且最后3个点由于p1与p2不是质数，所以必须用中国单身狗定理来处理逆元。。
然而，我最后一个点996242 个询问只有一个不对，一个啊！！！
当我打表过了以后，我点开另一个过了的大神的代码一看：天哪！
没有两个程序，没有逆元，没有中国单身狗定理，有的只是前6个点的做法：线段树维护区间乘积，但是，
但是这位大神居然用了ztw线段树然后+快读+快写+卡常卡过了！！！
真是跪了。。好好地一道数论题输给了常数，还不知道有一个询问是怎么错的。。
最后，希望大神帮我看看我那个询问为什么不对。。
好吧，我知道了，我开了三个数组存逆元（p2的三个因数），但我只把一个的下标为0的初始化为了1，又智障了。。

回复 @紅蓮之心熾熱��_血瞳洞穿無盡陰暗 :
那啥 我代码里不是zkw线段树
不是所有非递归的线段树处理的东西都是zkw线段树
虽然是卡常，这个做法还是讲道理的，我看来不比中国剩余定理做差
算法是这样的，首先对于线段树每个节点(flo,l,r)是第flo层的表示[l,r]区间的节点
设mid=(l+r)/2，a[]为输入的数组，记录下a[mid]一直往左边乘到a[l]的值，和a[mid+1]一直往右边乘到a[r]的值
这样对于一个询问的区间[gl,gr]只要找到一个区间[l,r]满足l<=gl<=mid<gr<=r就可以只做一次乘法就算出答案
整个算法乘法和取模的次数是严格(nlogn+m) 一共是2100万次
你可以数数你的扩展欧几里得和后面中国剩余定理的乘法和取模次数一共有多少次 这个常数完全赶得上一个log
(最后我有点好奇后面两位的代码和跑出来的时间是怎么过的

回复 @scpointer :
当然，无论什么做法，能过就是好算法，而且你的做法确实很有道理，这点我服，而且考试时当然是做法越简单越易实现越好，从这点看你的代码好得多。
我发评论只是为了宣泄下自己的痛苦，毕竟我太辣鸡了。。

说实话，不知道怎么过的。。。。。。

回复 @Mike is Fool :
表示严重怀疑十多秒的是偷偷把时限放大过了再把时限改回去的。。

回复 @Mike is Fool :
你以为非递归线段树就能不T吗......

说好的常数级修改，结果改的连数据范围都不能信了

25行，懒到不优化。。。。。。

回复 @Mike is Fool :
最后四个点不是你卡常能过的，7要求逆元，8、9、10要用中国单身狗定理。。
别问我为什么，我都改了一下午了。。

这题非要我们把线段树写成非递归吗？卡常真严重。

回复 @Rapiz :
这个可以保证。相当于是对于以每个点为起点进行最短路，在过程中中途终止，记录下答案，然后继续进行。
如果说你能卡掉的话，给我一组数据。

数据有误，数据中询问有最大路径 d等于1e9+1
如果把没有的边权值设为1e9+1就能A
设成更大的就过不去了
8,9,10组应该都有问题，第8组 921161个询问对应最大值就是1e9+1，答案输出了96（所有的点），正确应该是88

最大值请赋1e9+1……
0x3f调了一天

小于！小于！小于！