相关链接
题目传送门: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; }