Function

引理:
我们称 $X\ge M$ 时 $X\ mod\ M$ 为一次有效的取模,则 $X$ 在 $\lceil log_{2}X\rceil$ 次有效的取模后一定变为 0 。
简要说明:
考虑最坏情况,取 $M=\lfloor\frac{X}{2}\rfloor+1$ ,$X->\lfloor\frac{X-1}{2}\rfloor$
(当 $M’>M$ 或 $M’<M$ 时,$X$ 都会变得更小)

题解:
考虑到 $a[l]$ 有效取模次数是 $log$ 级别的,所以只需要快速找出下一次有效的取模
即,每次寻找不大于当前数的最靠左的数
可以二分右端点,并询问区间内最小的数
使用ST维护,预处理 $O(NlogN)$ ,询问 $O(1)$
取模 $O(logX)$ 次,二分 $O(logN)$ 次,rmq $O(1)$ ,每个case复杂度为 $O(M*logX*logN)$
ST好久没写。。。可能失败的二分也好久没写。。。T了好多好多次。。。代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=100010;
int st[N][25];

void st_init(int n)
{
for (int i=1;(1<<i)<=n;i++)
for (int j=1;j+(1<<i)-1<=n;j++)
st[j][i]=min(st[j][i-1],st[j+(1<<(i-1))][i-1]);
}

int st_query(int l,int r)
{
int k=0;
while ((1<<(k+1))<=r-l+1) k++;
return min(st[l][k],st[r-(1<<k)+1][k]);
}

int bsearch(int l,int r,int lim)
{
int res=r+1;
while (l<=r) {
int m=(l+r)>>1;
if (st_query(l,m)>lim) l=m+1;
//区间最小值大于当前值,即区间所有数大于当前值
else r=m-1,res=m;
}
return res;
}

int main()
{
int T,n,m;
scanf("%d",&T);
while (T--) {
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&st[i][0]);
st_init(n);
scanf("%d",&m);
while (m--) {
int l,r;
scanf("%d%d",&l,&r);
int res=st[l++][0];
while (l<=r&&res) {
l=bsearch(l,r,res);
if (l<=r) {
res%=st[l++][0];
}
}
printf("%d\n",res);
}
}
return 0;
}