基本情況

A秒了，B错一次之后也过了，C没思路。

B. Beautiful Array

Problem - B - Codeforces

void solve()
{
	long long n, k, b, s;
	memset(ans, 0, sizeof(ans));
	std::cin >> n >> k >> b >> s;
	if (s < b * k) {std::cout << "-1\n"; return ;}
	s -= b * k;
	ans[1] = b * k;
	for (int i = 2; i <= n; i++)
	{
		if (s - k > 0)
		{
			s -= k; ans[i] = k;
		}
		else
		{
			ans[i] = s; s = 0; break;
		}
	}
	if (s != 0) {std::cout << "-1\n"; return ;}
	for (int i = 1; i <= n; i++) std::cout << ans[i] << " ";
	std::cout << std::endl;
}

这个贪心大体上好像很对，但是又是细节问题。

我把剩下的 $ans_i$ 都赋成 $k$ ，然而 $\left \lfloor \frac{k}{k} \right \rfloor$ 是 $1$ 啊，我要搞的是等于零的最大可能的数，自然是 $k - 1$。
$ans_1 = b * k $ 还不够贪，可以往上找到最大的符合 $\left \lfloor \frac{temp}{k} \right \rfloor = b$ 的数，一开始样例跑了很久，突然发现可能会T，然后改用二分就OK。（然而这个改进并不影响正确性，似乎数据不大行）

这两个改完就AC了。

void getTemp(long long& x)
{
	long long l = b * k, r = s, mid;
	while(l <= r)
	{
		mid = l + (r - l >> 1); 
		if (mid / k == b) x = mid, l = mid + 1;
		else r = mid - 1;
	}
	return ;
}

void solve()
{
	memset(ans, 0, sizeof(ans));
	std::cin >> n >> k >> b >> s;
	if (s < b * k) {std::cout << "-1\n"; return ;}
	long long temp;
	getTemp(temp);
	s -= temp; ans[n] = temp; 
	k--;
	for (int i = n - 1; i >= 1; i--)
	{
		if (s - k > 0)
		{
			s -= k; ans[i] = k;
		}
		else
		{
			ans[i] = s; s = 0; break;
		}
	}
	if (s != 0) {std::cout << "-1\n"; return ;}
	for (int i = 1; i <= n; i++) std::cout << ans[i] << " ";
	std::cout << std::endl;
}

C. Monoblock

Problem - C - Codeforces

想了一个递推，还是错的，时间复杂度也不行。

思路

每次只变一个数，因此考虑在短时间内计算：每个位置的数产生的贡献。

容易发现以下的条件：

不管 $a_i$ 是什么，当它作为一个子串的首项时，块数一定会加一。共有 $(n - i + 1)$ 个串的首项是 $a_i$。
如果 $a_i \ne a_{i-1}$，所有包含 $a_i$ 与 $a_{i+1}$ 的子串，块数都加一。乘法原理，头有 $(i - 1)$ 个位置可以选（$0$ 到 $i - 1$），尾有 $(n - i + 1)$ 个位置可以选（$i$ 到 $n$），共 $(i - 1) \times (n - i + 1)$。

那么，我们就可以知道 $a_{i - 1}$ 与 $a_i$ 间产生的贡献是多少。

LL calc(int i) //统计 a[i-1]与a[i]间产生的贡献
{
	LL k = n - i + 1; //以 a[i] 为头的所有子串，不管a[i-1]与a[i]相不相同，都要计算贡献。 
	if (a[i-1] == a[i]) return k;
	return 1ll * (i - 1) * (n - i + 1) + k; //不同才会产生贡献
}

然后，我们可以计算：原本的 $a$ 数组有多少贡献。这非常简单。

LL sum = 0;
for (int i = 1; i <= n; i++) sum += calc(i);

那么，怎样在短时间内计算 $a_i$ 改变后的值呢？只需要：

减去 $a_{i-1}$ 与 $a_i$ 产生的贡献，减去 $a_i$ 与 $a_{i + 1}$ 产生的贡献。因为它们过一会会变。
更改 $a_i$。
重新加上 $a_{i-1}$ 与 $a_i$ 产生的贡献，以及加上 $a_i$ 与 $a_{i + 1}$ 产生的贡献。

然后再输出结果即可。

代码

LL calc(int ind) //统计 a[i-1]与a[i]间产生的贡献
{
	LL k = n - ind + 1;//以 a[i] 为头的所有子串，不管a[i-1]与a[i]相不相同，都要计算贡献。
	if (a[ind - 1] == a[ind]) return k;
	return 1ll * (ind - 1) * (n - ind + 1) + k;//不同才会产生贡献
}
int main()
{
 	LL sum = 0;
 	std::cin >> n >> m;
 	for (int i = 1; i <= n; i++) std::cin >> a[i];
 	for (int i = 1; i <= n; i++) sum += calc(i);//先算一遍总值
 	while(m--)
 	{
 		std::cin >> ind >> x;
 		sum -= calc(ind); sum -= calc(ind + 1);//把修改前i上的数的贡献减掉
 		a[ind] = x;
 		sum += calc(ind); sum += calc(ind + 1);//把修改后i上的数的贡献加上
 		std::cout << sum << std::endl;
	}
	return 0;
}