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

群论