题目链接：bzoj1998 题目大意： 有n个位置，从0到n-1依次编号，一开始0号位置空，其它的位置i上有编号为i的盒子。Lostmonkey要按照以下规则重新排列这些盒子。 规则由5个数描述，q，p，m，d，s，s表示空位的最终位置。首先生成一个序列c，c0=0，ci+1=(ci*q+p) mod m。接下来从第一个盒子开始依次生成每个盒子的最终位置posi，posi=(ci+d*xi+y

Description 某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣

Description 某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有

题目链接 点击打开链接 题目解法 动态 m s t mst mst 板板题~ 考虑类似于线段树分治的做法 我们需要把边划分成静态边和动态边 动态边是当前分治区间 [ l , r ] [l,r] [l,r] 中修改的边，其他边是静态边 我们考虑到静态边的边集太大，考虑缩小范围，不难想到 答案加上必选边 和 删去无用边 令动态边的边权为 − ∞ -\infty −∞，这样仍在 m s