题目概述
$n$个数的数列 $a_n$ ,$q$次询问。
每次询问给出数$v$，区间端点$[l，r]$,问用$v$按顺序依次对数列$[l,r]$中的数取模，得到的最终答案。
数据范围
分析与解
这道题在考场上试图通过主席树+二分来解，可惜复杂度为$O(qlog^21e18log^2n)$常数大得离谱。故失败。
首先我们注意到一点，就是每一次取模，这个$v$都会减小一半，因此直接取模最多$log1e18$求解是可行的。关键在于每次精确的找到对哪个数取模？实际上，就是求对于当前这个数，在它右边最近的小于等于它的数的位置。
这里之前用主席树做麻烦了，其实把上面这句话翻译下，不就是该数$x$向右延伸最多能延伸多少遇到的都是$>x$的数？这件事就转化为一个区间最小值的问题了。而且为了更好的解决延伸，其实用ST表和倍增思路就一步到位了。
实现见代码。
复杂度为$O(qlogn \cdot log10^{18})$
代码
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL mread() {
LL ret=0,f=1;
char c=getchar();
while(c<'0' || c>'9') {
if(c=='-')f=-1;
c=getchar();
}
do {
ret=ret*10+c-'0';
c=getchar();
} while('0'<=c && c<='9');
return ret*f;
}
#define MAXN 200100
LL mmin[MAXN][25];
LL a[MAXN];
int n,q;
int main() {
LL v;
int l,r,now;
n=mread(),q=mread();
for(int i=1; i<=n; i++) {
a[i]=mread();
mmin[i][0]=a[i];
}
for(int i=1; i<=25; i++) {
for(int j=1; j+(1<<i)-1<=n; j++)
mmin[j][i]=min(mmin[j][i-1],mmin[j+(1<<(i-1))][i-1]);
}
while(q--) {
v=mread(),l=mread(),r=mread();
now=l;
while(now<=r) {
v=v%a[now];
for(int i=25; i>=0; i--)
if(now+(1<<i)-1<=r && mmin[now][i]>v)
now+=((1<<i)-1);
now++;
}
printf("%lld\n",v);
}
return 0;
}
|