A. 跑步

对于每次修改，$O(n^2)$ 的 dp 是显然的。

然后发现每次修改这个 dp 的变化量只有 $+1,-1$ 两种取值。

继续观察性质，可以发现，对于每一行，变化的位置是连续的。

对于不同行，变化的左端点和右端点都是单调的。

所以通过树状数组差分实现区间修改，单调指针确定每一行的修改区间就完事了。

B. 算术

确实想到了搞个 $k$ 次剩余，但是不知道通过这个东西有这么高的正确率。

所以问题就简单了，取几个质数，然后计算 $n$ 在这些质数下是否均有 $k$ 次剩余。

也就是说我们要找是否存在 $x$,满足 $x^k \equiv n \pmod p$。

发现，如果取一个 $p$ ，然后满足 $\gcd(\varphi(p),k) =1$，那么 $k$ 在模 $\varphi(p)$ 意义下是存在逆元的，也就是一定存在 $k$ 次剩余。

所以为了提高正确率，应该尽量选择与 $k$ 的公因数尽量多的 $\varphi(p)$。

考虑使 $p=a*k+1$。

然后发现有 $x^k \equiv n \pmod p , x^{a*k} \equiv 1 \pmod p$

则 $n^a \equiv 1 \pmod p$。

可以发现这两个式子是等价的，所以无需求原根，直接快速幂计算即可。

C. 求和

发现维护全部的答案比较难以实现，问题在于每次修改，要改的地方太多了，然后没有办法一次性统计答案。

所以继续压缩答案可能出现的位置。

发现有这样一种构造，取出所有的位置 $i$。

满足 $a_j \leq a_i (i-k \leq j<i) , a_j < a_i (i<j \leq i+k)$。

可以认为，答案一定选择了这样的位置 $i$ 中的一个。

于是问题变得简单了，对于单次修改，变化量不超过两个。

所以分类讨论这个点在变化之后是否为特殊点即可用线段树维护。