CWOI S C0232 A 前k大

题意使用 openssl enc -aes256 -pbkdf2 加密。

U2FsdGVkX1985UZqJJvxcjgJvf2O6Nc4nb/QV3wLd6yI3cwIqFgZyWVwXWAmlbqW
jWmt9QN56u47OFNXj4QPkhI20YGBRBPLJr2Wyjh+HUxwGXWi+ovOvGQ384AUIO0C
PzA224pzOLCPOqtCKHDwMOItfhntl4AveEhJ+K4wG4CuzmkUsThZmwrKih4wb+Le
yBYVfzyK6N/q6XG0ZIawu5bsujfb29wi1T/HEPBLmBmkuYowxOAgNFCkTbzMU2MG
/rjA0W0FkgE78hWUO0tyokicKJaXLwB5OI8qPenOg4FKYt1elZ4qUd6Cl7WEnpjs
rz6e4AyDB7nTAsBalNhhzt4WUfsw5QymK9YC1r7jFzk=

解析

由于 $f(x)$ 不会很大，我们可以根据 $f(x)$ 的值对所有的 $x$ 分类：

f(x) = 0: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, ...
f(x) = 1: 2, 6, 10, 14, 18, ...
f(x) = 2: 4, 12, 20, ...
f(x) = 3: 8, ...
f(x) = 4: 16, ...

容易注意到所有相同 $f(x)$ 值的 $x$ 组成了一个等差数列，如果用 $h_i(x)$ 表示 $f(x)$ 为 $i$ 的数列的话，可以得到 $h_i(x) = 2^{i + 1} \times x + 2^i$。而 $g(h_i(x)) = h_i(x) + c \times i$，同样是个等差数列。我们可以二分出第 $k$ 大的值，然后再求出所有大于 $k$ 的 $g$ 值之和。

时间复杂度 $O(\log^2(r))$。

void solve()
{
	long long L, R, k, c;
	scanf("%lld%lld%lld%lld", &L, &R, &k, &c);
	R++;

	std::array<std::pair<long long, long long>, 31> ranges;
	for (int i = 0; i < 31; i++) {
		auto begin = 1ll << i;
		auto step = 1ll << (i + 1);
		ranges[i] = {
			(L - begin + step - 1) / step,
			(R - begin + step - 1) / step
		};
		// printf("%d: [%lld %lld)\n", i, ranges[i].first, ranges[i].second);
	}

	long long l = 0, r = 1e12;
	long long cnt = 0;
	while (l < r) {
		long long mid = l + (r - l) / 2;
		long long mid_cnt = 0;
		for (int i = 0; i < 31; i++) {
			if (ranges[i].second - ranges[i].first <= 0) continue;
			auto begin = (1ll << i) + c * i;
			auto step = 1ll << (i + 1);
			auto x = (mid - begin + step - 1) / step;
			mid_cnt += std::max(0ll, ranges[i].second -
					    std::max(ranges[i].first,
						     x));
		}
		if (mid_cnt <= k) {
			r = mid;
			cnt = mid_cnt;
		} else {
			l = mid + 1;
		}

		// printf("%lld: %lld\n", mid, mid_cnt);
	}

	long long sum = 0;
	for (int i = 0; i < 31; i++) {
		auto begin = (1ll << i) + c * i;
		auto step = 1ll << (i + 1);
		auto x = std::max(ranges[i].first, (r - begin + step - 1) / step);
		if (x >= ranges[i].second) continue;
		auto fx = begin + step * x;
		auto end = ranges[i].second - 1;
		auto fend = begin + step * end;
		auto cnt = ranges[i].second - x;
		sum += (fx + fend) * cnt / 2;
		// printf("%d: %lld(%lld) + ... + %lld(%lld)\n", i, x, fx, end, fend);
	}
	sum += (k - cnt) * (r - 1);

	printf("%lld\n", sum);
}