给定 N,M 以及 M 个二元组 (a0,b0),...,(aM−1,bM−1)。
对于任意的 i∈[1,n],有 max(biai,aibi)⩽2。
生成序列 {XN},生成方式如下:
-
首先有 l=1,r=N,t=0;
-
令 m=⌊atmodM+btmodMatmodM×l+btmodM×r⌋,若 m=i 则令 Xi=t 并结束;
-
若 l⩽i<m,则令 r=m−1,柔则令 l=m+1,令 t←t+1 并返回第二步。
有 Q 个询问,每次给定区间 (ci,di),询问 j=ci∑di−1∣Xj−Xj+1∣。
translated by cszyf