AtCoder Beginner Contest 253

A, B 比较简单就不写了。

我的代码 : All Submissions - SGColin

C. Max - Min Query

维护一个 multiset ，支持插入一个 \(x\) ，删除 \(\min(c_i,s.count(x))\) 个 \(x\) ，查询最大值-最小值。

开始想想直接模拟复杂度是对的就写了 multiset，没想到 multiset 的 lower_bound 太慢了 T 了几个点。

Upd : 经提醒应该是 count 函数太慢了，官网描述是 "Logarithmic in size and linear in the number of matches" ，也就是说复杂度是 \(\mathcal{O}(k+\log n)\) ，其中 \(k\) 是查询数字的出现次数，所以加入 \(10^5\) 个点之后，多查几次就超时了。

所以改为用 map 维护一个计数器，每次某个数字新出现/消失的时候再对 set 操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

map<int, int> cnt;

set<int> s;

int main() {
    int n = rd();
    for (int i = 1; i <= n; ++i) {
        int op = rd();
        if (op == 1) {
            int x = rd();
            ++cnt[x];
            if (cnt[x] == 1) s.insert(x);
        }
        else if (op == 2) {
            int x = rd();
            int t = min(rd(), cnt[x]);
            cnt[x] -= t;
            if (cnt[x] == 0) s.erase(x);
        } else printf("%d\n", (*--s.end()) - (*s.begin()));
    }
    return 0;
}

D. FizzBuzz Sum Hard

给定 \(n,a,b\) 找出 \([1,n]\) 内不是 \(a\) 或 \(b\) 倍数的数字的和。

简单的容斥原理，扣掉 \(a,b\) 的倍数，加上 \(\text{lcm}(a,b)\) 的倍数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

int main() {
    int n = rd(), a = rd(), b = rd();
    ll sum = 1ll * n * (n + 1) / 2;
    int ka = n / a;
    int kb = n / b;
    sum -= 1ll * a * ka * (ka + 1) / 2;
    sum -= 1ll * b * kb * (kb + 1) / 2;
    ll lcm = 1ll * a * b / gcd(a, b);
    ll kl = n / lcm;
    sum += 1ll * lcm * kl * (kl + 1) / 2;
    printf("%lld\n", sum);
    return 0;
}

E. Distance Sequence

计数长度为 \(n\) 的序列 \(\{a_i\}\) ：(1) \(a_i\in[1,m]\) ; (2) \(\forall i\in[2,n], |a_i-a_{i-1}|\ge k\) .

直接 DP ，设 \(f_{i,j}\) 表示长度为 \(i\) 的序列，结尾是 \(j\) 的方案数，有： \[ f_{i,j}=\sum_{w\in[1,j-k]\cup[j+k,m]} f_{i-1,w} \] 用一个前缀和优化即可，注意下 \(k=0\) 时不要算重，复杂度 \(O(nm)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 1007
#define M 5007
#define mod 998244353

int f[N][M], sum[N][M];

inline int fpow(int x, int t) {
    int res = 1;
    for (; t; t >>= 1, x = 1ll * x * x % mod)
        if (t & 1) res = 1ll * res * x % mod;
    return res;
}

int main() {
    int n = rd(), m = rd(), k = rd();
    if (k == 0) {printf("%d\n", fpow(m, n)); return 0;}
    for (int i = 1; i <= m; ++i) {
        f[1][i] = 1; sum[1][i] = i;
    }
    for (int i = 2; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            int l = max(0, j - k);
            int r = min(m, j + k - 1);
            f[i][j] = (sum[i - 1][m] - sum[i - 1][r] + mod) % mod;
            f[i][j] = (f[i][j] + sum[i - 1][l]) % mod;
        }
        for (int j = 1; j <= m; ++j) 
            sum[i][j] = (sum[i][j - 1] + f[i][j]) % mod;
    }
    printf("%d\n", sum[n][m]);
    return 0;
}

F. Operations on a Matrix

维护一个初始是全 \(0\) 的 \(n\times m\ (n,m\le 2\ast 10^5)\) 的矩阵，支持：

  • 对 \([l_i,r_i]\) 这些列的每一个元素加 \(x\)
  • 将第 \(i\) 行全部赋值为 \(x\)
  • 查询矩阵中 \((x_i,y_i)\) 的值

记录每行最后一次被赋值的时间戳 \(lst_i\) 和赋值 \(x_i\) ，则答案为 \(x_i\) + \([lst,now]\) 这段操作里对 \(y_i\) 加的值。

  • 在线的做法就是写一个主席树 + 标记持久化；

  • 离线的做法就是把后面的贡献写做前缀和差分，然后两个时刻维护一下。

学到了简老师的主席树写法 OwO

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define mid ((l + r) >> 1)
#define N 200007

int tot, rttot;

struct node {
    int ls, rs;
    ll sum;
} c[N << 6];

int rot[N], lst[N];

ll x[N];

int copy(int rt) {
    c[++tot] = c[rt];
    return tot;
}

void upd(int &rt, int l, int r, int L, int R, int x) {
    rt = copy(rt);
    if (L <= l && r <= R) {
        c[rt].sum += x; return;
    }
    if (L <= mid) upd(c[rt].ls, l, mid, L, R, x);
    if (R > mid) upd(c[rt].rs, mid + 1, r, L, R, x);
}

ll query(int rtl, int rtr, int l, int r, int p) {
    ll res = c[rtr].sum - c[rtl].sum;
    if (l == r) return res;
    if (p <= mid) res += query(c[rtl].ls, c[rtr].ls, l, mid, p);
    else res += query(c[rtl].rs, c[rtr].rs, mid + 1, r, p);
    return res;
}

int main() {
    int n = rd(), m = rd(), q = rd();
    for (int i = 1; i <= q; ++i) {
        int op = rd();
        if (op == 1) {
            ++rttot;
            rot[rttot] = rot[rttot - 1];
            int l = rd(), r = rd(), v = rd();
            upd(rot[rttot], 1, m, l, r, v);
        } else if (op == 2) {
            int p = rd(); 
            x[p] = rd(); 
            lst[p] = rttot;
        } else {
            int row = rd(), col = rd();
            printf("%lld\n", x[row] + query(rot[lst[row]], rot[rttot], 1, m, col));
        }
    }
    return 0;
}

G. Swap Many Times

对于 \(n\) ，初始化一个序列 \(a_1,\cdots,a_n\) ，满足 \(a_i=i\) 。

对于 \(n\) ，有 \(\frac{n(n+1)}{2}\) 个形如 \((x,y)\) 的满足 \(1\le x<y\le n\) 的数对，按照 pair 的规则排序。

给定 \(L,R\) ，对于这个 pair 序列的第 \(L\) 个到第 \(R\) 个，依次操作：交换 \(a_x\) 和 \(a_y\)

求最终的序列。

观察这个序列， \(x\) 相同的 pair 是连续出现的，考虑对于同一个 \(x\) 把所有操作都做掉。

假设以 \(x\) 为 first 的在 \([L,R]\) 内的操作为 \((x,y_a),(x,y_a+1),\cdots,(x,y_b)\)

那么实际操作的结果就是把序列中 \(x,y_a,y_a+1,\cdots,y_b\) 这些位置整体向右 shift 一个位置。

枚举 \(x\) ，然后只需要一个支持某个位置插入删除的数据结构就可以了。

然后昨天趁机学了一下 rope ，内核是块状链表，理论复杂度 \(\mathcal{O}(n\sqrt{n})\) ，实际表现速度很快。

只能说非常好用，可惜 Clang 编译不了，是在 Custom Test 手动调试的。

p.s. 题解的做法貌似不需要数据结构，好像很精妙

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
#include <ext/rope>
using namespace std;
using namespace __gnu_cxx;

typedef long long ll;

inline ll rd() {
    ll x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

rope<int> s;

int main() {
    int n = rd();
    ll L = rd(), R = rd();
    ll l = 0, r = 0;
    for (int i = 0; i <= n; ++i) s.push_back(i);
    for (int i = 1; i <= n; ++i) {
        l = r + 1; r = l + n - i - 1;
        if (L <= r && R >= l) {
            int ll = max(l, L), rr = min(r, R);
            int pl = i + 1 + ll - l;
            int pr = i + 1 + rr - l;
            int x = s[pr];
            s.erase(pr, 1);
            s.insert(pl, s[i]);
            s.erase(i, 1);
            s.insert(i, x);
        }
    }
    for (int i = 1; i <= n; ++i)
        printf("%d ", s[i]);
    return 0;
}