相关链接
题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=4630
神犇题解：http://www.cnblogs.com/zhsl/p/3234099.html
吐槽
最开始写了一个复杂度玄学的莫队，然后被卡$T$了
然后又写了一个$O(n \log n \sqrt{n \log n})$的$KD-Tree$，然后又被卡$T$了
然后看了题解就给跪了，这™不是傻逼题吗？
解题报告
我们将询问按照左端点排序，然后降序处理
这样每一次询问就相当于问一个后缀的前缀
然后考虑新加入最左边一个数$a_i$对于答案的影响
显然我们可以枚举因数$v$，然后记$v$上一次出现的位置为$last_v$
那么右端点在$i \sim last_v$之间的询问都会计算到这个$\gcd$
于是我们用$BIT$维护一个前缀最值就可以了
时间复杂度：$O(n \log^2 n)$
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 50009;
int n,m,pos[N],arr[N],last[N],ans[N];
struct Query{
int l,r,id;
inline bool operator < (const Query &Q) const {
return l < Q.l;
}
}q[N];
vector<int> que[N];
inline int read() {
char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}
class Fenwick_Tree{
#define lowbit(x) ((x)&-(x))
int mx[N];
public:
inline void init() {
memset(mx, 0, sizeof(mx));
}
inline void modify(int p, int v) {
for (int i=p;i<=n;i+=lowbit(i)) {
mx[i] = max(mx[i], v);
}
}
inline int query(int p) {
int ret = 1;
for (int i=p;i;i-=lowbit(i)) {
ret = max(ret, mx[i]);
}
return ret;
}
}BIT;
int main() {
for (int T=read();T;T--) {
n = read();
for (int i=1;i<=n;i++) {
que[i].clear();
arr[i] = read();
pos[arr[i]] = i;
}
for (int i=2;i<n;i++) {
for (int j=i;j<=n;j+=i) {
que[pos[j]].push_back(i);
}
}
m = read();
for (int i=1,l,r;i<=m;i++) {
q[i].l = read();
q[i].r = read();
q[i].id = i;
}
sort(q+1, q+1+m);
BIT.init();
memset(last,60,sizeof(last));
for (int i=m,cur=n+1;i;i--) {
while (cur > q[i].l) {
--cur;
for (int j=0;j<que[cur].size();j++) {
int v = que[cur][j];
if (last[v] <= n) {
BIT.modify(last[v], v);
}
last[v] = cur;
}
}
if (q[i].l == q[i].r) ans[q[i].id] = 0;
else ans[q[i].id] = BIT.query(q[i].r);
}
for (int i=1;i<=m;i++) {
printf("%d\n",ans[i]);
}
}
return 0;
}
