E. Concave Hull

算法流程

先算一次凹包，把所有的点分成“在凸包上”和“不在凸包上”的点 SS。

枚举 SS 中的每一个点作为凹点 p0p_0，然后对其他所有点 pip_i 计算出向量 vi=pip0→v_i=\overrightarrow{p_ip_0} 并按极角排序。

极角排序完了之后，向量必定是 on, /, /, /, on, /, /, on, on, /, /, on ...... 这样排列（两个在凸包上的点 c1,c2c_1,c_2 中间夹着一些不在凸包上的点 djd_j，记这些点的集合为 F={F0=c1,F1=d1,d2,…,Fm=dm,Fm+1=c2}F=\{F_0=c_1,F_1=d_1,d_2,\dots,F_m=d_m,F_{m+1}=c_2\}）。我们尝试计算以 p0p_0 作为凹点，Fi,Fi+1F_i,F_{i+1} 作为优角的两边的凹包面积。

这里的话，如果跑暴力算法，时间复杂度会来到 O(n3)O(n^3)。考虑到这个凹包的面积其实是凸包面积去掉一部分面积，我们可以利用这一点加速计算。

两个三角形
两个三角形

我们把凹包凹进去的部分分成左右两半凸壳（图中黄色和绿色部分），做两次 Andrew 凸包扫描算法（从左往右，然后从右往左）。例如 Andrew 算法从左往右扫描，只要扫描算法扫描经过这些点 FF，那么我们就能算出由 c1→Fic_1\to F_i 这些点构成（且包括了 FiF_i 的）的左半凸壳的面积。同理也可以计算出右半凸壳的面积。因此以 p0p_0 为凹点、Fi,Fi+1F_i,F_{i+1} 为优角的凹包面积也就可以算出来了（大凸包面积，减掉这一个凹角对应的凸包上三角形的面积 ΔADG\Delta ADG，再加上左右两个凸壳的面积）

Code

Code
 
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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iostream>
#include <ranges>
#include <utility>
#include <set>
#include <vector>
using i64       = long long;
constexpr i64 M = 1e9 + 7;

struct pvec {
    int x, y;
    friend std::istream &operator>>(std::istream &is, pvec &a) { return is >> a.x >> a.y; }
    friend std::ostream &operator<<(std::ostream &os, const pvec &a) { return os << a.x << ' ' << a.y; }
    bool operator==(const pvec &a) const { return x == a.x && y == a.y; }
    pvec operator-(const pvec &a) const { return {x - a.x, y - a.y}; }
    bool operator<(const pvec &a) const { return x == a.x ? y < a.y : x < a.x; }
};

int sign(i64 val) { return val < 0 ? -1 : (val > 0 ? 1 : 0); }
i64 cross(const pvec &a, const pvec &b) { return 1ll * a.x * b.y - 1ll * a.y * b.x; }
i64 cross(const pvec &a, const pvec &b, const pvec &c) { return cross(b - a, c - a); }
i64 dot(const pvec &a, const pvec &b) { return 1ll * a.x * b.x + 1ll * a.y * b.y; }
int scross(const pvec &a, const pvec &b, const pvec &c) { return sign(cross(a, b, c)); }
i64 sqrlen(const pvec &a) { return dot(a, a); }

auto convex_hull(const std::vector<pvec> &x) {
    std::vector<pvec> v(x);
    std::vector<pvec> used, unused;
    std::sort(v.begin(), v.end());
    int m = v.size(), tp = -1;
    
    for (int i = 0; i < m; i++) {
        while (tp > 0 && cross(used[tp-1], used[tp], v[i]) <= 0) 
            tp--, used.pop_back();
        used.push_back(v[i]), tp++;
    }
    int t = tp;
    for (int i = m - 1; i >= 0; i--) {
        while (tp > t && cross(used[tp-1], used[tp], v[i]) <= 0) {
            tp--;
            used.pop_back();
        }
        used.push_back(v[i]), tp++;
    }
    used.pop_back();
    std::set<pvec> s;
    for(auto d: used) s.insert(d);
    for(auto d: v) if (!s.contains(d)) unused.push_back(d);
    return std::pair{used, unused};
}
bool comp(const pvec &a, const pvec &b) {
    bool upA = a.y > 0 || (a.y == 0 && a.x >= 0);
    bool upB = b.y > 0 || (b.y == 0 && b.x >= 0);
    if (upA != upB) return upA;
    auto val = cross(a, b);
    return val > 0;
}
i64 area(const std::vector<pvec> &p) {
    i64 res = 0;
    for (int i = 0, m = p.size(); i < m; i++) res += cross(p[i], p[(i + 1) % m]);
    return res;
}

void run() {
    int n;
    std::cin >> n;

    std::vector<pvec> p(n);
    for (auto &x : p) std::cin >> x;

    auto [used, un] = convex_hull(p);
    int sz          = used.size();
    i64 ans         = 0;

    for (const auto &x : un) { // enum concave point.
        std::vector<std::pair<pvec, int>> al;
        std::vector<pvec> cur(sz);
        std::vector<i64> val(sz, 0); // area of triangle formed by on-convex points
        i64 sum = 0;

        for (const auto &y : un) { // compute vectors
            if (y == x) continue;
            al.push_back({y - x, -1});
        }
        for (int i = 0; i < sz; i++) {
            cur[i] = used[i] - x;
            al.push_back({cur[i], i});
        }
        // sort by angle
        std::sort(al.begin(), al.end(), [&](const auto &a, const auto &b) { return comp(a.first, b.first); });

        // rotate to satisfy pattern:
        // [on-convex, not, not, ..., not, on-convex, not, not .... , not, on-convex]
        for (int i = 0; i < al.size(); i++) {
            if (al[i].second == -1) continue;
            std::rotate(al.begin(), al.begin() + i, al.end());
            break;
        }

        // compute convex area
        for (int i = 0; i < sz; i++) {
            val[i] = cross(cur[i], cur[(i + 1) % sz]);
            sum += val[i];
        }

        // enum all points between 2 on-convex points
        for (int l = 0, r = 0, al_size = al.size(); l < al_size; l = r) {
            r = l + 1;
            while (r < al_size && al[r].second == -1) r++;
            // (l, r) is the range of not-on-convex points
            // l, r are on-convex points

            int pos = al[l].second;
            std::vector<i64> T(r - l, 0);
            assert((pos + 1) % sz == al[r % al_size].second);

            // left convex
            [&al, &T, &l, &r] {
                std::vector<pvec> pts;
                int top  = -1;
                i64 ssum = 0;

                for (int fix = l; fix < r; fix++) {
                    const auto &q = al[fix].first;
                    while (top >= 1 && cross(q - pts[top - 1], pts[top] - pts[top - 1]) >= 0) {
                        ssum -= cross(pts[top - 1], pts[top]);
                        top--, pts.pop_back();
                    }
                    pts.push_back(q), top++;
                    if (top >= 1) ssum += cross(pts[top - 1], pts[top]);

                    T[fix - l] += ssum;
                }
            }();
            // right convex
            [&al, &T, &l, &r, &al_size] {
                std::vector<pvec> pts;
                int top  = -1;
                i64 ssum = 0;

                for (int fix = r; fix > l; fix--) {
                    const auto &q = al[fix % al_size].first;
                    while (top >= 1 && cross(pts[top - 1], pts[top], q) >= 0) {
                        ssum -= cross(pts[top], pts[top - 1]);
                        top--, pts.pop_back();
                    }
                    pts.push_back(q);
                    top++;
                    if (top >= 1) ssum += cross(pts[top], pts[top - 1]);

                    T[fix - l - 1] += ssum;
                }
            }();

            for (int i = 0; i < r - l; i++) {
                i64 st = sum - val[pos] + T[i];
                (ans += std::abs(st)) %= M;
            }
        }
    }

    std::cout << ans << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int T = 1;
    // std::cin >> T;
    while (T--) run();

    return 0;
}

H. Mah-Jong

算法流程

我们先预处理出所有可能的顺子的情况 SS，每个顺子最多出现 22 次（否则可以视为 33 个碰），最少出现 00 次，因此最多 729729 种情况。

于是每一个合法的区间都可以视为，SS 中的某一个顺子搭配 ss 加上 若干个碰，因此对于区间 [l,r][l, r] 而言，令这个区间有 did_i 个数字为 ii 的麻将牌，而顺子组合 ss 要求 bib_i 个数字为 ii 的牌，那么区间合法这个条件等同于

di≡bi(mod3)di≥bi \begin{aligned} d_i&\equiv b_i \pmod 3\\ d_i&\ge b_i \end{aligned}
  • 考虑如何维护 di≥bid_i\ge b_i 这个条件：
    • 如果我们固定右端点 rr，那么我们只需要让 l:r→1l:r\to 1 扫描，直到 [l,r][l,r] 的 did_i 开始满足 di≥bid_i\ge b_i，那么对于所有 p<lp\lt l，都一定会有 [p,r]:di≥bi[p,r]:d_i\ge b_i（因为 p<lp\lt l，因此只会往这个区间里添加新的数，因此 did_i 不可能变小）
  • 考虑如何维护同余 di≡bi(mod3)d_i\equiv b_i\pmod {3}
    • 用桶维护即可。可以开 88 维数组或者用三进制表示

时间复杂度 O(36n)O(3^6n)

Code
 
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
#include <iostream>
#include <ranges>
#include <vector>
using i64 = long long;

void run() {
    int n;
    std::cin >> n;

    std::vector cnt(n + 1, std::vector<int>(8, 0));
    std::vector<int> mask(n + 1, 0);
    std::vector<int> a(n + 1, 0);
    auto encode = [&](int d) {
        int s = 0;
        for (auto i : std::views::iota(0, 8)) s = s * 3 + cnt.at(d).at(i) % 3;
        return s;
    };
    auto decode_chow = [&](int pat) {
        std::vector<int> p(8, 0);
        for (int i : std::views::iota(0, 6)) {
            int u = pat % 3;
            pat /= 3;
            p.at(i) += u, p.at(i + 1) += u, p.at(i + 2) += u;
        }
        return p;
    };
    for (int i = 1; i <= n; i++) {
        std::cin >> a.at(i);
        a.at(i)--;

        cnt.at(i) = cnt.at(i - 1);
        cnt.at(i).at(a.at(i))++;

        mask.at(i) = encode(i);
    }

    i64 ans = 0;
    std::vector<int> bucket(8000, 0);
    for (auto pattern : std::views::iota(0, 729)) {
        auto pat = decode_chow(pattern);

        for (int i = 0; i <= n; i++) bucket.at(mask.at(i))++;

        int r = 0;
        for (int l = 1; l <= n; l++) {
            for (; r <= l; r++) bucket.at(mask.at(r))--; // 先去除不合法的区间（即 右端点小于左端点的区间）
            int target = 0;

            for (int t : std::views::iota(0, 8)) {
                // 用双指针去除不满足偏序关系的
                while (r <= n && cnt.at(r).at(t) < cnt.at(l - 1).at(t) + pat.at(t)) {
                    bucket.at(mask.at(r))--;
                    r++;
                }
                target = target * 3 + (cnt.at(l - 1).at(t) + pat.at(t)) % 3;
            }
            if (r > n) break;
            ans += bucket[target]; // 加上满足同余的区间的贡献
        }
    }

    std::cout << ans << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int T = 1;
    std::cin >> T;
    while (T--) run();

    return 0;
}