20220816 - 模拟赛 | Final Fantasy = xixike = 人间忽晚，山河已秋

贪心，分块 + 暴力，莫比乌斯反演，二分（单调栈）

# A. [USACO14OPEN]Fair Photography S

贪心就行了。

首先令 W 等于 1， S 等于 -1，观察到白牛可以染成黑牛（黑就黑吧）。

不难推出，如果前缀和 $s_i$ 大于等于 0，那么从第一头牛到当前牛都可以选，当然还要判一下奇偶：

$i$ 是偶数，那么可以选 $pos_i - pos_1$ .
$i$ 是奇数，那么可以选 $pos_i - pos_2$ .

如果 $s_i$ 小于 0 怎么办呢？

也很简单，直接开个 $\text{map}$ 存一下 $s_i$ 第一次出现位置，遇到 $s_i < 0$ 的情况，直接跟 $\text{map}$ 里的值计算答案即可。

	#include <bits/stdc++.h>
	#define pc putchar
	#define pb push_back
	#define fi first
	#define se second
	#define int long long

	using namespace std;

	namespace IO{
	inline int read(){
	int x = 0, f = 1;
	char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
	while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
	return x * f;
	}

	template <typename T> inline void write(T x){
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
	}
	}
	using namespace IO;

	const int N = 1e5 + 10;
	int n;
	struct node{
	int pos, col;
	inline bool operator < (const node &b) const{
	return pos < b.pos;
	}
	}a[N];
	int s[N], sum, ans;
	map <int, int> vis;

	signed main(){
	#ifndef ONLINE_JUDGE
	freopen("test.in", "r", stdin);
	freopen("test.out", "w", stdout);
	#endif
	n = read();
	for(int i = 1; i <= n; ++i){
	int x = read(); char c; scanf("%c", &c);
	a[i] = (node){x, c == 'W' ? 1 : -1};
	}
	sort(a + 1, a + 1 + n);
	a[n + 1].pos = 1e9;
	vis[0] = 1;
	for(int i = 1; i <= n; ++i){
	sum = sum + a[i].col;
	if(sum < 0 && !vis[sum]) vis[sum] = i + 1;
	if(sum >= 0){
	if(sum & 1) ans = max(ans, a[i].pos - a[2].pos);
	else ans = max(ans, a[i].pos - a[1].pos);
	}else ans = max(ans, a[i].pos - a[vis[sum]].pos);
	}
	write(ans), puts("");
	return 0;
	}

# B. DZY Loves Colors

分块水题。

维护一个 $cov$ 标记，标记整块是否被某一种颜色覆盖。

注意到一次修改最多会使两个块不再被同一种颜色覆盖，是 $O(n)$ 级别的，所以直接暴力枚举整块修改即可。

写的时候注意 $cov$ 标记的下放，不要忘了放，也不要放多了（

	#include <bits/stdc++.h>
	#define pc putchar
	#define pb push_back
	#define fi first
	#define se second
	#define int long long

	using namespace std;

	namespace IO{
	inline int read(){
	int x = 0, f = 1;
	char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
	while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
	return x * f;
	}

	template <typename T> inline void write(T x){
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
	}
	}
	using namespace IO;

	const int N = 1e5 + 10;
	int n, m, B, tot;
	int be[N], L[N], R[N];
	int c[N], w[N], sum[N], tag[N], tagc[N];

	inline void build(){
	tot = n / B;
	if(n % B) tot++;
	for(int i = 1; i <= n; ++i) be[i] = (i - 1) / B + 1;
	for(int i = 1; i <= tot; ++i) L[i] = R[i - 1] + 1, R[i] = i * B;
	R[tot] = n;
	for(int i = 1; i <= n; ++i) c[i] = i;
	}

	inline void upd(int l, int r, int k){
	for(int i = l; i <= r; ++i){
	if(!tagc[be[l]]) w[i] += abs(c[i] - k), sum[be[l]] += abs(c[i] - k), c[i] = k;
	else w[i] += abs(tagc[be[l]] - k), sum[be[l]] += abs(tagc[be[l]] - k), c[i] = k;
	}
	if(tagc[be[l]]){
	for(int i = L[be[l]]; i < l; ++i) c[i] = tagc[be[l]];
	for(int i = r + 1; i <= R[be[r]]; ++i) c[i] = tagc[be[r]];
	}
	tagc[be[l]] = 0;
	}

	inline void update(int l, int r, int k){
	if(be[l] == be[r]) return upd(l, r, k);
	for(int i = be[l] + 1; i <= be[r] - 1; ++i){
	if(tagc[i]) sum[i] += B * abs(k - tagc[i]), tag[i] += abs(k - tagc[i]);
	else for(int j = L[i]; j <= R[i]; ++j) w[j] += abs(c[j] - k), sum[i] += abs(c[j] - k), c[j] = k;
	tagc[i] = k;
	}
	upd(l, R[be[l]], k), upd(L[be[r]], r, k);
	}

	inline int query(int l, int r){
	int res = 0;
	if(be[l] == be[r]){
	for(int i = l; i <= r; ++i) res += w[i] + tag[be[l]];
	return res;
	}
	for(int i = be[l] + 1; i <= be[r] - 1; ++i) res += sum[i];
	for(int i = l; i <= R[be[l]]; ++i) res += w[i] + tag[be[l]];
	for(int i = L[be[r]]; i <= r; ++i) res += w[i] + tag[be[r]];
	return res;
	}

	signed main(){
	#ifndef ONLINE_JUDGE
	freopen("test.in", "r", stdin);
	freopen("B.out", "w", stdout);
	#endif
	double st = clock();
	n = read(), m = read(), B = sqrt(n);
	build();
	while(m--){
	int op = read(), l = read(), r = read();
	if(op == 1) update(l, r, read());
	else write(query(l, r)), puts("");
	}
	double ed = clock();
	cerr << ed - st << endl;
	return 0;
	}

一开始没什么思路，后来发现一条线段是可以平移旋转的，所以只统计从 $(0, 0)$ 开始的线段就行了。

枚举从 $(0, 0)$ 开始的线段终点是 $(i, j)$ 。

众所周知，中间不经过其他整点的条件相当于是 $\gcd(i, j) = 1$ 。

再来看能平移到那些位置，不难发现有 $(n - i + 1) \times (m - j + 1)$ 个位置，平且可以旋转，所以再乘个 2。

对于横平竖直的边单独处理一下就行。

暴力的话 $O(nm\log n)$ 可以拿到 $\text{65pts}$ 。

下面来优化，目前答案就是：

$\begin{aligned} Ans =& \sum_{i = 1}^n\sum_{j = 1}^m2(n - i + 1)(m - j + 1)[\gcd(i, j) == 1] \\ =& \sum_{i = 1}^n\sum_{j = 1}^m\sum_{d | (i, j)}\mu(d)2(n - i + 1)(m - j + 1) \\ =& \sum_{d = 1}^n\mu(d)\sum_{i = 1}^{\lfloor\frac nd\rfloor}2(n - i + 1)\sum_{j = \lceil\frac{\sqrt{l^2 - (id)^2}}{k}\rceil}^{\lfloor\frac{\sqrt{h^2 - (id)^2}}{k}\rfloor}(m - j + 1) \\ \end{aligned}$

令 $L = \lceil\frac{\sqrt{l^2 - (id)^2}}{k}\rceil, R = \lfloor\frac{\sqrt{h^2 - (id)^2}}{k}\rfloor$ ，得：

$\begin{aligned} Ans =& \sum_{d = 1}^n\mu(d)\sum_{i = 1}^{\lfloor\frac nd\rfloor}2(n - i + 1)\sum_{j = L}^{R}(m - j + 1) \\ =& \sum_{d = 1}^n\mu(d)\sum_{i = 1}^{\lfloor\frac nd\rfloor}2(n - i + 1)\frac{[(m - L + 1) + (m - R + 1)](R - L + 1)}{2} \\ =& \sum_{d = 1}^n\mu(d)\sum_{i = 1}^{\lfloor\frac nd\rfloor}(n - i + 1)[(m - L + 1) + (m - R + 1)](R - L + 1) \end{aligned}$

复杂度 $O(n \ln n)$ 。

	#include <bits/stdc++.h>
	#define pb push_back
	#define int long long

	using namespace std;

	namespace IO{
	inline int read(){
	int x = 0, f = 1;
	char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
	while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
	return x * f;
	}

	template <typename T> inline void write(T x){
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
	}
	}
	using namespace IO;

	const int N = 1e5 + 10;
	int n, m, l, h, mod, ans;
	int mu[N], p[N], vis[N], tot;

	inline void euler(int n){
	mu[1] = 1;
	for(int i = 2; i <= n; ++i){
	if(!vis[i]) p[++tot] = i, mu[i] = -1;
	for(int j = 1; j <= tot && i * p[j] <= n; ++j){
	vis[i * p[j]] = 1;
	if(i % p[j]) mu[i * p[j]] = -mu[i];
	else break;
	}
	}
	}

	inline int add(int x) {return x >= mod ? x - mod : x;}
	inline int sub(int x) {return x < 0 ? x + mod : x;}
	inline int mul(int x, int y) {return 1ll * x * y % mod;}
	inline int cal(int x) {return (x % mod + mod) % mod;}
	inline int sqr(int x) {return x * x;}

	signed main(){
	#ifndef ONLINE_JUDGE
	freopen("test.in", "r", stdin);
	freopen("test.out", "w", stdout);
	#endif
	n = read(), m = read(), l = read(), h = read(), mod = read();
	if(n > m) swap(n, m);
	euler(n);
	if(l <= 1) ans = add(mul(n, m + 1) + mul(m, n + 1));
	for(int d = 1; d <= n; ++d){
	int res = 0;
	for(int i = 1; i <= n / d; ++i){
	if(sqr(h) <= sqr(i * d)) continue;
	int L = ceil(1.0 * sqrt(sqr(l) - sqr(i * d)) / d), R = min(m, (int)floor(sqrt(sqr(h) - sqr(i * d)))) / d;
	if(sqr(l) <= sqr(i * d)) L = 1;
	if(L > R \|\| L > m) continue;
	res = add(res + mul(n - i * d + 1, mul(add(m - L * d + 1 + m - R * d + 1), R - L + 1)));
	}
	ans = add(ans + cal(mu[d] * res));
	}
	write(ans), puts("");
	return 0;
	}

# D. 牛宫

考场上写个 $O(n^4)$ 发现暴力跑的飞快，结果 $\text{Luogu}$ 不给开 $\text{O2}$ /fn/fn/fn

大概是套路的枚举行的上下边界，再枚举计算一下行的前缀和，然后二分列的长度 $len$ ， $\text{check}$ 一下就行。

我没写正解，只有暴力代码，就不放了吧（

# A. [USACO14OPEN]Fair Photography S

# B. DZY Loves Colors

# C. [USACO12MAR]Large Banner G

# D. 牛宫

20220729

群论