#arc159e. [arc159_e]Difference Sum Query

[arc159_e]Difference Sum Query

给定 N,MN,M 以及 MM 个二元组 (a0,b0),...,(aM1,bM1)(a_0,b_0),...,(a_{M-1},b_{M-1})

对于任意的 i[1,n]i\in[1,n],有 max(aibi,biai)2\max(\dfrac{a_i}{b_i},\dfrac{b_i}{a_i})\leqslant 2

生成序列 {XN}\{X_{N}\},生成方式如下:

  • 首先有 l=1,r=N,t=0l=1,r=N,t=0

  • m=atmodM×l+btmodM×ratmodM+btmodMm=\lfloor\dfrac{a_{t\bmod M}\times l+b_{t\bmod M}\times r}{a_{t\bmod M}+b_{t\bmod M}}\rfloor,若 m=im=i 则令 Xi=tX_i=t 并结束;

  • li<ml\leqslant i<m,则令 r=m1r=m-1,柔则令 l=m+1l=m+1,令 tt+1t\leftarrow t+1 并返回第二步。

QQ 个询问,每次给定区间 (ci,di)(c_i,d_i),询问 j=cidi1XjXj+1\sum\limits_{j=c_i}^{d_i-1}|X_j-X_{j+1}|

translated by cszyf