ARC136

C 题降智，终场发现是结论题。

A 比较没意思。

B 是经典结论了，逆序对相关。

C - Circular Addition

积木大赛的环形版本，每次可以选择环上的一段区间 \(+1\)，求加到指定状态的最小次数。

如果考虑模拟最优过程，想再多都是假的（

突发奇想，答案最优是什么，显然不可能 \(<\) 全局最大值 \(M\)。

再观察，考虑差分和 \(S=\sum |a_i-a_{i-1}|\)，注意 \(n,1\) 也是相连的，显然每次至多减少 \(2\)，且时刻是一个偶数。

故 \(Ans\geq \max(S/2,M)\)，需要证明可以达到这个下界，实际上即证明，每次操作可以将 \(\max(S/2,M)\) 减少 \(1\)。

大力讨论：

• 当 \(S/2，显然序列中不存在 \(0\)，否则 \(S/2\geq M\)，故将序列全部 \(-1\) 即可。
• 当 \(S/2=M\)：
  • 若序列中无 \(0\)，随便找到一个极小的包含所有 \(M\) 的某个区间 \(-1\) 即可。
  • 否则，序列中必然不存在多段连续的 \(M\)，否则同样矛盾。那么直接把那一段 \(M\) 变为 \(M-1\) 即可。
• 当 \(S/2>M\)，找到极大的包含 \(M\) 的非 \(0\) 区间 \(-1\) 即可。

证明过程均比较显然，但是结论难想啊（

const int N = 2e5 + 10;
int n, a[N];

int main() {
	int Mx = 0;
	n = read();
	rep(i, 1, n) a[i] = read(), Mx = max(Mx, a[i]);
	LL s = 0;
	rep(i, 1, n) s += abs(a[i] - a[i == 1 ? n : i - 1]);
	printf("%lld\n", max((LL)Mx, s / 2));
	return 0;
}

D - Without Carry

给定长度为 \(n\) 的序列，值域 \([1,10^6]\)，求相加在十进制下不进位的对数。

VP 的时候也有点降智，一直在想咋用 bitset 优化这个 \(6\) 维偏序。

实际每一维值域小的可怜，硬上树状数组即可。

const int N = 1e6 + 10, M = 11;
 
int n, a[N], t[M], tr[M][M][M][M][M][M];
 
void Add(int v) {
	for(int a = v / t[0] % 10 + 1; a <= 10; a += a & - a)
	for(int b = v / t[1] % 10 + 1; b <= 10; b += b & - b)
	for(int c = v / t[2] % 10 + 1; c <= 10; c += c & - c)
	for(int d = v / t[3] % 10 + 1; d <= 10; d += d & - d)
	for(int e = v / t[4] % 10 + 1; e <= 10; e += e & - e)
	for(int f = v / t[5] % 10 + 1; f <= 10; f += f & - f)
		tr[a][b][c][d][e][f] ++;
}
 
int Ask(int v) {
	v = 999999 - v;
	int s = 0;
	for(int a = v / t[0] % 10 + 1; a; a -= a & - a)
	for(int b = v / t[1] % 10 + 1; b; b -= b & - b)
	for(int c = v / t[2] % 10 + 1; c; c -= c & - c)
	for(int d = v / t[3] % 10 + 1; d; d -= d & - d)
	for(int e = v / t[4] % 10 + 1; e; e -= e & - e)
	for(int f = v / t[5] % 10 + 1; f; f -= f & - f)
		s += tr[a][b][c][d][e][f];
	return s;
}
 
int main() {
	n = read();
	rep(i, 1, n) a[i] = read();
	t[0] = 1;
	rep(i, 1, 6) t[i] = t[i - 1] * 10;
	LL ans = 0;
	rep(i, 1, n)
		ans += Ask(a[i]), Add(a[i]);
	printf("%lld\n", ans);
	return 0;
}

E - Non-coprime DAG

给出 \(n\) 个数，针对下标建图，若 \((i,j)\) 满足：

• \(i
• \(\gcd(i,j)>1\)

那么有 \(i\to j\) 的有向边。

要求选出一组两两不可到达的数，使得权值和最大。

一直在往最长反链想，然后有权值有不太可做（

实际上，根据奇偶性讨论，考虑什么样的 \((x,y)\) 不能同时被选：

• 若 \(x\) 为偶，\(y\) 为偶：显然 \(x,y\) 不能同时选。
• 若 \(x\) 为偶，\(y\) 为奇：当且仅当 \(x\leq y-f(y)\)。
• 若 \(x\) 为奇，\(y\) 为偶：当且仅当 \(x+f(x)\leq y\)。
• 若 \(x\) 为奇，\(y\) 为奇：当且仅当 \(x+f(x)\leq y-f(y)\)。

其中 \(f(x)\) 表示 \(x\) 的最小质因子，当 \(x\) 为奇数时，\(x\pm f(x)\) 显然是个偶数，所以前 \(3\) 条不难理解。

最后一条的正确性，充分性也是显然的，必要性也不难。

若 \(x,y\) 不互质，设 \(x=pa,y=pb\)，则 \(x=pa，根据奇偶性。

那么即使 \(p\) 为最小质因子，也还是有 \(x+p=y-p\)。

然后又是比较人类智慧的时刻，考虑将偶数作为单点，奇数变为区间 \([x-f(x)+1,x+f(x)-1]\)。

那么，可以选出的一组数的充要是，它们有交，直接差分维护每个交点的和即可。

const int N = 1e6 + 10;
int n, a[N]; LL c[N];

int t, p[N], f[N];
bool v[N];
 
void Pre() {
	rep(i, 2, n) {
		if(! v[i]) p[++ t] = i, f[i] = i;
		for(int j = 1; j <= t && p[j] * i <= n; j ++) {
			v[p[j] * i] = true;
			f[p[j] * i] = p[j];
			if(i % p[j] == 0) break;
		}
	}
}
 
int main() {
	n = read(), Pre();
	rep(i, 1, n) a[i] = read();
	for(int i = 2; i <= n; i += 2) c[i] += a[i], c[i + 1] -= a[i];
	for(int i = 3; i <= n; i += 2) {
		c[i - f[i] + 1] += a[i];
		if(i + f[i] <= n) c[i + f[i]] -= a[i];
	}
	rep(i, 2, n) c[i] += c[i - 1];
	LL ans = a[1];
	rep(i, 2, n) ans = max(ans, a[1] + c[i]);
	printf("%lld\n", ans);
	return 0;
}

F 是期望 GF 照例是不会的（