提出 4b60ebf9-39c8-4aeb-bd13-ef20653a95d4

コード

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

struct BIT
{
	int n;
	vector<ll> bit;
	BIT(int n) : n(n), bit(n + 1, 0) {}
	void add(int i, ll v)
	{
		for (; i <= n; i += i & -i)
			bit[i] += v;
	}
	ll sum(int i)
	{
		ll s = 0;
		for (; i > 0; i -= i & -i)
			s += bit[i];
		return s;
	}
	ll range(int l, int r)
	{
		return sum(r) - sum(l - 1);
	}
};

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int N;
	cin >> N;

	vector<ll> A(N + 1);
	for (int i = 1; i <= N; i++)
		cin >> A[i];

	vector<int> mu(N + 1, 1), prime;
	vector<bool> is_prime(N + 1, true);
	mu[0] = 0;
	mu[1] = 1;

	for (int i = 2; i <= N; i++)
	{
		if (is_prime[i])
		{
			prime.push_back(i);
			mu[i] = -1;
		}
		for (int p : prime)
		{
			if (i * p > N)
				break;
			is_prime[i * p] = false;
			if (i % p == 0)
			{
				mu[i * p] = 0;
				break;
			}
			else
			{
				mu[i * p] = -mu[i];
			}
		}
	}

	vector<ll> B(N + 1, 0);
	for (int d = 1; d <= N; d++)
	{
		for (int i = d; i <= N; i += d)
		{
			B[i] += (ll)mu[d] * A[i / d];
		}
	}

	BIT bit(N);
	for (int i = 1; i <= N; i++)
		bit.add(i, B[i]);

	int Q;
	cin >> Q;

	ll Z = 0;

	while (Q--)
	{
		int T;
		ll Hx, Hy;
		cin >> T >> Hx >> Hy;

		ll x = Hx ^ Z;
		ll y = Hy ^ Z;

		if (T == 1)
		{
			if (x > y)
				swap(x, y);
			ll ans = bit.range(x, y);
			cout << ans << "\n";
			Z ^= ans;
		}
		else
		{
			ll delta = y - A[x];
			A[x] = y;

			for (int k = 1; k * x <= N; k++)
			{
				int i = x * k;
				ll add = (ll)mu[k] * delta;
				bit.add(i, add);
			}
		}
	}
}

結果

問題	点数	言語	結果	実行時間	メモリ
G. Decomposite or Die	650	C++ (gcc)	AC	273 ms	17280 KiB

テストセット

テストセット	結果	得点	実行時間	メモリ
Subtask1	AC × 5	160	15 ms	8320 KiB
Subtask2	AC × 10	190	164 ms	8320 KiB
Subtask3	AC × 23	300	273 ms	17280 KiB

詳細結果

テストケース	結果	実行時間	メモリ
1_1	AC	15 ms	8192 KiB
1_2	AC	13 ms	8192 KiB
1_3	AC	14 ms	8064 KiB
1_4	AC	14 ms	8320 KiB
1_5	AC	15 ms	8320 KiB
2_1	AC	149 ms	8064 KiB
2_2	AC	99 ms	7936 KiB
2_3	AC	110 ms	8192 KiB
2_4	AC	105 ms	8320 KiB
2_5	AC	164 ms	8320 KiB
3_1	AC	266 ms	17280 KiB
3_10	AC	213 ms	17280 KiB
3_2	AC	226 ms	17280 KiB
3_3	AC	228 ms	17280 KiB
3_4	AC	245 ms	17152 KiB
3_5	AC	263 ms	17280 KiB
3_6	AC	207 ms	17280 KiB
3_7	AC	259 ms	17152 KiB
3_8	AC	273 ms	17152 KiB
3_9	AC	251 ms	17152 KiB
sample_1	AC	16 ms	8064 KiB
sample_2	AC	13 ms	8064 KiB
sample_3	AC	13 ms	8192 KiB