D - Suddenly, A Tempest

给定一个默认矩阵，以左下角和右上角顶点表示，初始设置为(0, 0) 和 (X0, Y0)

其中X0， y0 属于【1， 1e8】
有N次风暴， 每次风暴分X操作和Y操：

  • X操作输入A， B， 把x坐标小于A的所有矩阵全部向下移动B个单位， 把y坐标大于A的所有矩阵全部向上移动B个单位
  • Y操作输入A， B， 把x坐标小于A的所有矩阵全部向左移动B个单位， 把y坐标大于A的所有矩阵全部向右移动B个单位

其中
求所有N此操作后分成的矩阵块和每个矩阵的个数。

解：

考虑到N比较小，定义一个struct模拟风暴中所有的矩阵块，初始值是默认矩阵块，

用一个vector维护当前所有的矩阵块，初始值只有一个默认矩阵

每次风暴来时候如果X或者Y操作会切割矩阵， 将被切割矩阵分成两块，否则保持原来矩阵，同时更新矩阵的位置

所有操作结束后，需要统计矩阵的联通数量，由于N不大，所有操作之后矩阵个数不会超过5e2，考虑使用一个并查集维护所有的连通块，
暴力枚举风暴操作后的vector矩阵数组，把所有联通的合并并计数，排序输出答案

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

struct bk {
    i64 x1, y1, x2, y2;
    i64 siz;

    bk() {}
    bk(i64 x1, i64 y1, i64 x2, i64 y2) : x1(x1), y1(y1), x2(x2), y2(y2) {
        siz = (y2 - y1) * (x2 - x1);
    }
};
bool fp(i64 l1, i64 r1, i64 l2, i64 r2){
    return max(l1, l2) < min(r1, r2);
}
bool connect(const bk &A, const bk &B){
    if (fp(A.x1, A.x2, B.x1, B.x2) && fp(A.y1, A.y2, B.y1, B.y2))
        return true;
    if ((A.x2 == B.x1 || B.x2 == A.x1) && fp(A.y1, A.y2, B.y1, B.y2))
        return true;
    if ((A.y2 == B.y1 || B.y2 == A.y1) && fp(A.x1, A.x2, B.x1, B.x2))
        return true;
    return false;
}
struct DSU {
    vector<int> f, siz;

    DSU() {}
    DSU(int n) {
        init(n);
    }

    void init(int n) {
        f.resize(n);
        iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }

    int find(int x) {
        while (f[x] != x) {
            x = f[x] = f[f[x]];
        }
        return x;
    }

    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }

    int size(int x) {
        return siz[find(x)];
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    i64 n, x, y;
    cin >> n >> x >> y;

    vector<bk> a;
    a.push_back({0, 0, x, y});

    for (int i = 1; i <= n; i++) {
        char c;
        cin >> c;

        vector<bk> nbk;
        if (c == 'X') {
            i64 A, B;
            cin >> A >> B;
            for (auto x : a) {
                auto [x1, y1, x2, y2, _] = x;

                if (x1 < A && A < x2) {
                    nbk.push_back({x1, y1 - B, A, y2 - B});
                    nbk.push_back({A, y1 + B, x2, y2 + B});
                } else if (A <= x1) {
                    nbk.push_back({x1, y1 + B, x2, y2 + B});
                } else {
                    nbk.push_back({x1, y1 - B, x2, y2 - B});
                }
            }
        } else {
            i64 A, B;
            cin >> A >> B;
            for (auto x : a) {
                auto [x1, y1, x2, y2, _] = x;

                if (y1 < A && A < y2) {
                    nbk.push_back({x1 - B, y1, x2 - B, A});
                    nbk.push_back({x1 + B, A, x2 + B, y2});
                } else if (A <= y1) {
                    nbk.push_back({x1 + B, y1, x2 + B, y2});
                } else {
                    nbk.push_back({x1 - B, y1, x2 - B, y2});
                }
            }
        }

        a = nbk;
    }

    vector<i64> ans;
    i64 cur = 0;
    vector<i64> S(a.size() + 1);
    DSU d(a.size() + 1);

    for (int i = 0; i < a.size(); i++) {
        for (int j = i + 1; j < a.size(); j++) {
            if (connect(a[i], a[j])) {
                d.merge(i + 1, j + 1);
            }
        }
    }

    for (int i = 1; i <= a.size(); i++) {
        S[d.find(i)] += a[i - 1].siz;
    }

    for (int i = 1; i <= a.size(); i++) {
        if (S[i]) {
            ans.push_back(S[i]);
        }
    }

    ranges::sort(ans);

    cout << ans.size() << '\n';
    for (auto x : ans) {
        cout << x << ' ';
    }
    return 0;
}

E - Clamp

给定一个长度为 NN 的整数序列 A=(A1,A2,…,AN)A=(A1​,A2​,…,AN​) 。

您收到了 QQ 查询，您应该按顺序处理这些查询。每个查询均采用以下格式之一：

  • 1 x y : 将 AxAx​ 的值更改为 yy 。
  • 2 l r ：查找 ∑1≤i≤Nmax⁡(l,min⁡(r,Ai))1≤i≤N∑​max(l,min(r,Ai​)) 的值。

解：

纸上画下所求的条件，发现所求的区间和分为三块： 【0, L】【L + 1, R - 1】【R, +∞】

其中小于L的都会变成L， 即L （小于L的数字个数）
大于R的都会变成R， 即R (大于R的个数)
在L + 1, R - 1范围内的正常计数操作，由于a【i】 属于【1， 5e5】，考虑使用一个线段树， 维护每个数字的出现次数, 每次询问计算即可

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

template<typename T>
struct Segment {
    vector<T> f, sum;
    int n;

    Segment() {}
    Segment(int n) : n(n) {
        f.assign((n << 2) + 1, 0);
        sum.assign((n << 2) + 1, 0);
    }

    void pushup(int s, int t, int p) {
        f[p] = f[p * 2] + f[p * 2 + 1];
        sum[p] = sum[p * 2] + sum[p * 2 + 1];
    }

    void update(int l, int r, T c, int s, int t, int p, T v) {
        if (s == t && l == s) {
            f[p] += c;
            sum[p] += c * v; 
            return;
        }

        int m = s + ((t - s) >> 1);

        if (l <= m) {
            update(l, r, c, s, m, p * 2, v);
        }
        if (r > m) {
            update(l, r, c, m + 1, t, p * 2 + 1, v);
        }
        pushup(s, t, p);
    }

    T q1(int l, int r, int s, int t, int p) {
        if (l <= s && t <= r) {
            return f[p];
        }
        int m = s + ((t - s) >> 1);
        T res = 0;
        if (l <= m) res += q1(l, r, s, m, p * 2);
        if (r > m) res += q1(l, r, m + 1, t, p * 2 + 1);
        return res;
    }

    T query(int l, int r, int s, int t, int p) {
        if (l <= s && t <= r) {
            return sum[p];
        }
        int m = s + ((t - s) >> 1);
        T res = 0;
        if (l <= m) res += query(l, r, s, m, p * 2);
        if (r > m) res += query(l, r, m + 1, t, p * 2 + 1);
        return res;
    }

    void update(int s, int t, T c, T v) {
        update(s, t, c, 1, n, 1, v);
    }

    T query(int s, int t) {
        if (s > t) return 0;
        return q1(s, t, 1, n, 1);
    }

    T q2(int s, int t) {
        if (s > t) return 0;
        return query(s, t, 1, n, 1);
    }
};
const int N = 5e5 + 1;
Segment<i64> sg(N + 2); 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    vector<i64> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for (int i = 1; i <= n; i++) {
        a[i]++; 
        sg.update(a[i], a[i], 1, a[i] - 1);
    }

    while (q--) {
        int op;
        cin >> op;

        if (op == 1) {
            int x; i64 y;
            cin >> x >> y;
            y++;

            sg.update(a[x], a[x], -1, a[x] - 1);
            a[x] = y;
            sg.update(a[x], a[x], 1, a[x] - 1);
        }
        else {
            i64 l, r;
            cin >> l >> r;
            l++; r++; 

            if (l >= r) {
                cout << 1LL * (l - 1) * n << '\n';
                continue;
            }

            i64 S = sg.query(1, l);       
            i64 D = sg.query(r, sg.n);    

            i64 mid = sg.q2(l + 1, r - 1); 
            i64 ans = S * (l - 1) + D * (r - 1) + mid;
            cout << ans << '\n';
        }
    }
    return 0;
}