Tag: 调和级数

相关链接

题目传送门：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;
}