还能蒸？

https://codeforces.com/contest/475/submission/360336341

怎么跑这么慢，难道说我写法某一块复杂度假了？

---

众所周知，ST 表解法很简单，但是 $O(n\log^2 V)$ 的复杂度还是太超模了，所以考虑换种解法。

考虑分治。

首先依旧势能分析，发现任意一个区间 $[l,r]$ 的前缀和后缀 $\gcd$ 一定能分成 $\min\{r-l+1,\lfloor\log_2 V\rfloor\}$ 段，每段相同。

所以合并两个区间时，我们可以枚举这两个区间的每一段计算。每左右两段会对它们区间的 $\gcd$ 贡献两段长度之积。

先说结论，如果能 $O(1)$ 求出 $\gcd$，则这个解法是 $O(n\log V)$ 的。

证明：我们把这个递归树分一下层，会发现最下面 $\log_2\log_2 V$ 层合并都是 $O((r-l+1)^2)$ 的，所以下面那 $\log_2 \log_2 V$ 层总的时间复杂度都是 $O(n\log V)$。再看上面的，上面的每个节点大小都在 $\log_2 V$ 以上，所以所有节点数不超过 $\frac{2n}{\log_2 V}$，每次合并是 $O(\log^2 V)$，所以时间复杂度也是 $O(n\log V)$。

现在的问题就是如何设计一个可以看做 $O(1)$ 的求 $\gcd$ 的方法了。

注意到前面那篇题解提到：

有人可能会说：诶你这计算 $\gcd$ 不算时间复杂度吗？其实势能分析一下，对于一个数 $V$ 进行 $n$ 次 $\gcd$ 运算，最多只会算 $n+\log_2 V$ 次。所以次数可以忽略不计。

考虑充分运用这个性质。

• 对于上层节点，因为后面的前缀 $\gcd$ 一定是前面的因数，所以我们记录上一次合并的区间 $\gcd$ 直接用上，即可均摊 $O(1)$。
• 对于下层节点，由于节点数不超过 $\log_2 V$，所以我们直接 $O(n\log V)$ 预处理出每个点后 $\log_2 V$ 个数的 $\gcd$，合并时直接 $O(1)$ 使用。

这样就能做到 $O(n\log V)$ 了吧，但为什么跑这么慢？

namespace cjdst{
    void solve2(std::vector <int> &a, std::vector <std::vector <int>> &sufgcd, int l, int r, std::vector <pii> &pre, std::vector <pii> &suf, std::unordered_map <int, ll> &mp){
		if(l == r){
			pre.push_back({l, a[l]});
			suf.push_back({l, a[l]});
			mp[a[l]]++;
			return;
		}
		int mid = (l + r) >> 1;
		std::vector <pii> pl, sl, pr, sr;
		solve2(a, sufgcd, l, mid, pl, sl, mp);
		solve2(a, sufgcd, mid + 1, r, pr, sr, mp);
		for(int i = 0; i < int(sl.size()); i++){
			int curgcd = sl[i].second;
			ll len1 = mid - sl[i].first + 1;
			if(i) len1 -= mid - sl[i - 1].first + 1;
			for(int j = 0; j < int(pr.size()); j++){
				ll len2 = pr[j].first - mid;
				if(j) len2 -= pr[j - 1].first - mid;
				if(r - l + 1 <= 32) curgcd = sufgcd[sl[i].first][pr[j].first - sl[i].first];
				else curgcd = std::__gcd(curgcd, pr[j].second);
				mp[curgcd] += len1 * len2;
			}
		}
		for(int i = l; i <= r; i++){
			int len = pre.size() - 1;
			if(pre.empty()) pre.push_back({i, a[i]});
			else if(a[i] % pre[len].second == 0) pre[len].first = i;
			else pre.push_back({i, std::__gcd(a[i], pre[len].second)});
		}
		for(int i = r; i >= l; i--){
			int len = suf.size() - 1;
			if(suf.empty()) suf.push_back({i, a[i]});
			else if(a[i] % suf[len].second == 0) suf[len].first = i;
			else suf.push_back({i, std::__gcd(a[i], suf[len].second)});
		}
	}

	void solve(){
		int n, m;
		std::cin >> n;
		std::vector <int> a(n + 5);
		std::vector <std::vector <int>> sufgcd(n + 5, std::vector <int>(33));
		for(int i = 1; i <= n; i++) std::cin >> a[i];
		for(int i = 1; i <= n; i++){
			sufgcd[i][0] = a[i];
			for(int j = 1; j <= 32; j++){
				if(i + j > n) break;
				sufgcd[i][j] = std::__gcd(sufgcd[i][j - 1], a[i + j]);
			}
		}
		std::vector <pii> pre, suf;
		std::unordered_map <int, ll> mp;
		solve2(a, sufgcd, 1, n, pre, suf, mp);
		std::cin >> m;
		while(m--){
			int val;
			std::cin >> val;
			std::cout << mp[val] << '\n';
		}
	}
}