牛客练习赛126

A 雾粉与签到题

void solve() {
    int n;cin >> n;
    vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    cout << *min_element(a.begin() + 2, a.begin() + n) << '\n';
}

B 雾粉与数论

give you a positive integer n,calculate \sum_{i = 2}^{n} gcd (\frac{i (i - 1)}{2}, \frac{i (i + 1)}{2})

打表找规律/分别对于奇数和偶数化简

void solve() {
    int n;cin >> n;
    cout << (n * (n + 1) / 2 - 1 - (n / 2)*(n / 2 + 1) / 2)%mod << '\n';
}

C/D 雾粉与最小值

给一个长度为 $n$ 的正整数数组 $a$ ，一个长度为 $m$ 的查询数组 $q$ ， $q [i] = (v a l, m i n l e n, m a x l e n)$ 。

请你按输入顺序处理这 $m$ 次查询，对于第 $i$ 次查询 $q [i] = (v a l, m i n l e n, m a x l e n) :$

easy：请你判断是否存在一个 $a$ 的子数组 $s$ 满足 $m i n (s) \geq v a l$ 且 $s$ 的长度在 minlen 和 maxlen 之间。

hard : 请你输出有多少个 $a$ 的子数组 $s$ 满足 $m i n (s) \geq v a l$ 且 $s$ 的长度在 minlen 和 maxlen 之间。

easy :

单调栈

H 佬用的方式感觉很有启发意义。

巧妙的找到了区间最小值，map[i] 代表 $\geq i$ 的区间长度，若长度是 $\geq m i n l e n$ ，则满足条件。

(也可以用单调栈来计算对于每一种值的区间长度)

void solve() {
    int n;cin >> n;
    vector<pair<int, int>> p(n);
    set<int> occ = {-1, n};
    for (int i = 0; i < n; i ++) {
        cin >> p[i].first;
        p[i].second = i;
        occ.insert(i);
    }
    sort(p.rbegin(), p.rend());
    map<int, int> ans;
    int cur = 0;
    for (auto [a, i] : p) {
        auto it = occ.find(i);
        cur = max(cur, *next(it) - *prev(it) - 1);
        occ.erase(it);
        ans[a] = cur;
    }
    int m;cin >> m;
    for (int i = 0; i < m; i ++) {
        int val, mn, mx;cin >> val >> mn >> mx;
        auto it = ans.lower_bound(val);
        if (it != ans.end() and it->second >= mn) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }
}

hard ：

(挖坑...)看不懂

线段树

void solve() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cout << fixed << setprecision(20);
    int n;cin >> n;

    vector<pair<int, int>> p(n);
    set<int> occ = {-1, n};
    for (int i = 0; i < n; i += 1) {
        cin >> p[i].first;
        p[i].second = i;
        occ.insert(i);
    }
    sort(p.rbegin(), p.rend());
    vector<tuple<int, int, int, int>> t;
    for (auto [a, i] : p) {
        auto it = occ.find(i);
        t.emplace_back(a, numeric_limits<int>::max(), *next(it) - i, i - *prev(it));
        occ.erase(it);
    }

    int m;cin >> m;
    for (int i = 0, val, mn, mx; i < m; i += 1) {
        cin >> val >> mn >> mx;
        t.emplace_back(val, i, mn, mx);
    }
    sort(t.rbegin(), t.rend());

    vector<ll> tk(n << 2), tb(n << 2), sum(n << 2);
    auto apply = [&](int v, int tl, int tr, ll k, ll b) {
        tk[v] += k;
        tb[v] += b;
        sum[v] += (tl + tr) * (tr - tl + 1) / 2 * k + (tr - tl + 1) * b;
        };
    auto push = [&](int v, int tl, int tr) {
        int tm = (tl + tr) / 2;
        apply(v * 2, tl, tm, tk[v], tb[v]);
        apply(v * 2 + 1, tm + 1, tr, tk[v], tb[v]);
        tk[v] = tb[v] = 0;
        };
    auto query = [&](int l, int r) {
        auto get = [&](auto& get, int v, int tl, int tr) -> ll {
            if (tl >= l and tr <= r) return sum[v];
            int tm = (tl + tr) / 2;
            push(v, tl, tr);
            ll res = 0;
            if (l <= tm) res += get(get, v * 2, tl, tm);
            if (r > tm) res += get(get, v * 2 + 1, tm + 1, tr);
            return res;
            };
        return get(get, 1, 1, n);
        };
    auto add = [&](int l, int r, int k, int b) {
        auto get = [&](auto& get, int v, int tl, int tr) {
            if (tl >= l and tr <= r) return apply(v, tl, tr, k, b);
            int tm = (tl + tr) / 2;
            push(v, tl, tr);
            if (l <= tm) get(get, v * 2, tl, tm);
            if (r > tm) get(get, v * 2 + 1, tm + 1, tr);
            sum[v] = sum[v * 2] + sum[v * 2 + 1];
            };
        get(get, 1, 1, n);
        };
    vector<ll> ans(m);
    for (auto [_, id, x, y] : t) {
        if (id < m) {
            ans[id] = query(x, y);
        } else {
            if (x > y) swap(x, y);
            add(1, x, 1, 0);
            if (x == y) {
                add(y + 1, x + y - 1, -1, x + y);
            } else {
                if (x + 1 < y) add(x + 1, y - 1, 0, x);
                add(y, x + y - 1, -1, x + y);
            }
        }
    }
    for (ll x : ans) {
        cout << x << "\n";
    }
}

补题补到 E ，然后补 ARC 的 B，(C)，然后就是补昆明，西安的题，补完之后就是板刷 ABC/CF，(外加补充自己不熟悉的知识点：特别是搜索和 DP) ABC 357