【树状数组该回炉重造了】Codeforces Round #813 (Div. 2) E2. LCM Sum (hard version)

参考题解

题意：
T T T 组数据，每组数据给定 l l l 和 r r r
求有多少种 l c m ( i , j , k ) ≥ i + j + k lcm(i,j,k)\geq i+j+k lcm(i,j,k)≥i+j+k，其中 l ≤ i < j < k ≤ r l\leq i<j<k\leq r l≤i<j<k≤r

数据范围： 1 ≤ T ≤ 1 0 5 , 1 ≤ l ≤ r ≤ 2 × 1 0 5 , l + 2 ≤ r 1\leq T\leq 10^5, 1\leq l\leq r\leq 2\times 10^5,l+2\leq r 1≤T≤105,1≤l≤r≤2×105,l+2≤r

题解：
仍然是正难则反，考虑 l c m ( i , j , k ) < i + j + k lcm(i,j,k)<i+j+k lcm(i,j,k)<i+j+k 的数量
开一个树状数组 t r tr tr ， t r [ i ] tr[i] tr[i] 用于维护三元组中 i , j , k i,j,k i,j,k的数量
具体是枚举 k k k，

• l c m ( i , j , k ) = k lcm(i,j,k)=k lcm(i,j,k)=k
  枚举 k k k 的因子，第一层枚举 i i i，第二层枚举 j j j。
  经过计算双重枚举在 2 × 1 0 5 2\times10^5 2×105 范围内在 3 e 7 3e7 3e7 左右，时限为 3500 m s 3500ms 3500ms，实测跑 480 m s 480ms 480ms。

• l c m ( i , j , k ) = 2 k lcm(i,j,k)=2k lcm(i,j,k)=2k，以下情况的证明

  第一种情况： i = 2 k 5 , j = 2 k 3 i=\frac{2k}{5},j=\frac{2k}{3} i=52k​,j=32k​
  第二种情况： i = k 2 , j = 2 k 3 i=\frac{k}{2},j=\frac{2k}{3} i=2k​,j=32k​

代码：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 200010;
struct Node {
	int l, id;
};

vector<Node> a[N];
ll ans[N];
ll tr[N]; // 树状数组 tr[i] 表示以 i 开头的 (i,j,k)

const int MAXN = 200000;
const int MAXM = MAXN << 1; 
ll sum(int p) {
	ll res = 0;
	while (p > 0) {
		res += tr[p];
		p -= p & (-p);
	}
	return res;
}

void add(int p, ll x) {
	while (p <= MAXN) {
		tr[p] += x; 
		p += p & (-p);
	}
}

vector<int> fac[N];
int n;

int main()
{
	// 类似埃筛的 O(nlogn) 筛因子法
	for (int i = 1; i <= MAXN; ++i)
		for (int j = i * 2; j <= MAXN; j += i)
			fac[j].push_back(i);
	
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		int l, r;
		scanf("%d%d", &l, &r);
		a[r].push_back({l, i});
		ll x = r - l + 1;
		ans[i] = x * (x - 1) * (x - 2) / 6;
	}
	
	// 枚举 r，同时将这个 r 对应为 k 的所有的 (i, j, k) 累计到树状数组 tr[i] 中
	for (int r = 1; r <= MAXN; ++r) {
		for (int i = 0; i < fac[r].size(); ++i) {
			int x = fac[r][i];
			int cnt = 0;
			for (int j = i + 1; j < fac[r].size(); ++j) {
				int y = fac[r][j];
				if (r % x == 0 && r % y == 0) cnt += 1;
			}
			add(x, cnt);
		}
		
		// lcm(i,j,k)=2k, i=2k/5, j=2k/3
		if (r % 15 == 0) {
			int x = r / 5 * 2;
			int y = r / 3 * 2;
			add(x, 1);
		}
		// lcm(i,j,k)=2k, i=k/2, j=2k/3
		if (r % 6 == 0) {
			int x = r / 2;
			int y = r / 3 * 2;
			add(x, 1);
		}
		// 只统计 从 [l, r - 2] 内的 i 对应的方案数
		for(auto& u: a[r]) {
			ans[u.id] -= sum(r - 2) - sum(u.l - 1);
		}
	}
	
	for (int i = 1; i <= n; ++i) printf("%lld\n", ans[i]);
	
	return 0;
}