CF438D The Child and Sequence

很显然地线段树题目,考虑区间取模和单点修改如何同时做. 懒标记 t a g 懒标记tag 懒标记tag维护这个区间还有什么东西没有取模到. 考虑下不同标记的影响,显然一个比较小的模数 p p p会覆盖掉模数大的情况,取min,那么 t a g tag tag初始值取 I N F INF INF即可. 很快我发现一个很大的问题,我去,区间和不能取模,它只是叶子取模,所以每次取模都要遍历一边这些勾八叶子. 然而,这和那个花神周游那个题很类似的,一个叶子不能被取模太多次的,如果区间最大值已经小于取模数p了,返回即可. 为什么这样区间修改不会超时,其实和这个 花神 差不多 如果有一个数字 x x x,随便取一个模 p p p y = x % p , y=x\%p, y=x%p,思考下如果让 y y y尽量大,那么 p p p最好取 x / 2 x/2 x/2. p p p取小了值域也就小了,取大了剩余的就小了,一半正好合适. 也就是有 x % p < x / 2 x\%pl>>r; coutr>>x; seg.update1(1,1,n,l,r,x); } if(op==3){ int pos,x;cin>>pos>>x; seg.update2(1,1,n,pos,x); } } }