竞赛讨论区 > 牛客练习赛135
头像
道柒
发布于 03-14 21:37 江苏
+ 关注

牛客练习赛135

因为我想出一些教育场，给大家来一些不是很偏，比较典，而且考的比较少的知识点或trick学习。所以希望大家可以在这一场有所收获，对于E和F其实如果掌握了这个知识点并不算太难，所以大家可以去学习一下对应的知识点再回来补题。

A 小柒的数字

关键观察点在于当 时，满足条件的 必须满足 。此时， 和 都等于 0。对于 ，由于 至少是 的两倍， 会小于 ，因此不满足条件。

因此，满足条件的 的范围是 。我们需要计算这个区间在 内的有效部分：

  • 当 时，有效数量为 。
  • 当 时，有效数量为 。

如果你不想思考，当然也可以打个表很容易便可观察到。

#include<bits/stdc++.h>

using i64 = long long;

void DAOQI() {
    int x, y, n;
    std::cin >> x >> y >> n;
    if (n >= x) {
        std::cout << x - 1 << "\n";
    } else {
        std::cout << n << "\n";
    }
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T = 1;
    std::cin >> T;
    while (T--) DAOQI();
    return 0;
}

B 小柒的逆序对(一)

对于一个排列来说，交换两个不下标的元素，逆序对数量的奇偶性必改变，具体的证明可以搜一下《线性代数》教学视频 2.0版宋浩老师

那么这个题就很简单，而不知道这个性质的同学也可以打个表很容易就可以发现。

#include<bits/stdc++.h>

using i64 = long long;

void DAOQI() {
    i64 n, m, q;
    std::cin >> n >> m >> q;
    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }
    bool ok = (m & 1);
    while (q--) {
        int i, j;
        std::cin >> i >> j;
        if (i != j) ok ^= 1;
        std::cout << (ok ? "odd" : "even") << "\n";
    }
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T = 1;
    //std::cin >> T;
    while (T--) DAOQI();
    return 0;
}

C 小柒的逆序对(2)

因为我们只是改变字母表的顺序，而并未改变字符串,因此我们可使用一个的二维数组g来记录在本宇宙字母表顺序中两种字母产生了多少逆序对。

那么在其他的平行宇宙中，如果这两个字母的出现顺序交换了，那么只要把它们产生的逆序对交换一下即可。例如在一开始一共有个序列，个序列。那么若字母在之后出现则会对逆序对产生的贡献，否则产生的贡献。所以如果字母表两个字母的出现顺序与本宇宙不符，只要把减去加上即可，其他两两字母组合同理。

#include<bits/stdc++.h>

using i64 = long long;

void DAOQI() {
    int n, q;
    std::cin >> n >> q;
    std::string s;
    std::cin >> s;
    std::vector<int> cnt(26), pos(26);
    std::vector g(26, std::vector(26, 0ll));
    i64 ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 26; j++) {
            if (j > s[i] - 'a') {
                ans += cnt[j];
            }
            g[j][s[i] - 'a'] += cnt[j];
        }
        cnt[s[i] - 'a']++;
    }
    for (int i = 1; i <= q; i++) {
        std::string t;
        std::cin >> t;
        for (int j = 0; j < 26; j++) {
            pos[t[j] - 'a'] = j;
        }
        i64 res = ans;
        for (int j = 0; j < 26; j++) {
            for (int k = 0; k < j; k++) {
                if (pos[k] > pos[j]) {
                    res = res - g[j][k] + g[k][j];
                }
            }
        }
        std::cout << res << std::endl;
    }
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T = 1;
    //std::cin >> T;
    while (T--) DAOQI();
    return 0;
}

D小柒分糖果

对于某一种糖果发放的方法而言，假设是第 个孩子获的的糖果数量，则的解的数量即是答案。

然而这个怎么求呢，我们可以加一个数即 解的合法数量跟上面一样的，因为我们可以把没有分给前m的人的给虚拟的第m+1个人，而这个式子的解的数量就是 n个相同的小球，放到m+1个不同的盒子的方案数

#include<bits/stdc++.h>

using i64 = long long;
using i64 = long long;

template<class T>
constexpr T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}

constexpr i64 mul(i64 a, i64 b, i64 p) {
    i64 res = a * b - i64(1.L * a * b / p) * p;
    res %= p;
    if (res < 0) {
        res += p;
    }
    return res;
}

template<i64 P>
struct MLong {
    i64 x;

    constexpr MLong() : x{} {}

    constexpr MLong(i64 x) : x{norm(x % getMod())} {}

    static i64 Mod;

    constexpr static i64 getMod() {
        if (P > 0) {
            return P;
        } else {
            return Mod;
        }
    }

    constexpr static void setMod(i64 Mod_) {
        Mod = Mod_;
    }

    constexpr i64 norm(i64 x) const {
        if (x < 0) {
            x += getMod();
        }
        if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }

    constexpr i64 val() const {
        return x;
    }

    explicit constexpr operator i64() const {
        return x;
    }

    constexpr MLong operator-() const {
        MLong res;
        res.x = norm(getMod() - x);
        return res;
    }

    constexpr MLong inv() const {
        assert(x != 0);
        return power(*this, getMod() - 2);
    }

    constexpr MLong &operator*=(MLong rhs) &{
        x = mul(x, rhs.x, getMod());
        return *this;
    }

    constexpr MLong &operator+=(MLong rhs) &{
        x = norm(x + rhs.x);
        return *this;
    }

    constexpr MLong &operator-=(MLong rhs) &{
        x = norm(x - rhs.x);
        return *this;
    }

    constexpr MLong &operator/=(MLong rhs) &{
        return *this *= rhs.inv();
    }

    friend constexpr MLong operator*(MLong lhs, MLong rhs) {
        MLong res = lhs;
        res *= rhs;
        return res;
    }

    friend constexpr MLong operator+(MLong lhs, MLong rhs) {
        MLong res = lhs;
        res += rhs;
        return res;
    }

    friend constexpr MLong operator-(MLong lhs, MLong rhs) {
        MLong res = lhs;
        res -= rhs;
        return res;
    }

    friend constexpr MLong operator/(MLong lhs, MLong rhs) {
        MLong res = lhs;
        res /= rhs;
        return res;
    }

    friend constexpr std::istream &operator>>(std::istream &is, MLong &a) {
        i64 v;
        is >> v;
        a = MLong(v);
        return is;
    }

    friend constexpr std::ostream &operator<<(std::ostream &os, const MLong &a) {
        return os << a.val();
    }

    friend constexpr bool operator==(MLong lhs, MLong rhs) {
        return lhs.val() == rhs.val();
    }

    friend constexpr bool operator!=(MLong lhs, MLong rhs) {
        return lhs.val() != rhs.val();
    }
};

template<>
i64 MLong<0LL>::Mod = i64(1E18) + 9;

template<int P>
struct MInt {
    int x;

    constexpr MInt() : x{} {}

    constexpr MInt(i64 x) : x{norm(x % getMod())} {}

    static int Mod;

    constexpr static int getMod() {
        if (P > 0) {
            return P;
        } else {
            return Mod;
        }
    }

    constexpr static void setMod(int Mod_) {
        Mod = Mod_;
    }

    constexpr int norm(int x) const {
        if (x < 0) {
            x += getMod();
        }
        if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }

    constexpr int val() const {
        return x;
    }

    explicit constexpr operator int() const {
        return x;
    }

    constexpr MInt operator-() const {
        MInt res;
        res.x = norm(getMod() - x);
        return res;
    }

    constexpr MInt inv() const {
        assert(x != 0);
        return power(*this, getMod() - 2);
    }

    constexpr MInt &operator*=(MInt rhs) &{
        x = 1LL * x * rhs.x % getMod();
        return *this;
    }

    constexpr MInt &operator+=(MInt rhs) &{
        x = norm(x + rhs.x);
        return *this;
    }

    constexpr MInt &operator-=(MInt rhs) &{
        x = norm(x - rhs.x);
        return *this;
    }

    constexpr MInt &operator/=(MInt rhs) &{
        return *this *= rhs.inv();
    }

    friend constexpr MInt operator*(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res *= rhs;
        return res;
    }

    friend constexpr MInt operator+(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res += rhs;
        return res;
    }

    friend constexpr MInt operator-(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res -= rhs;
        return res;
    }

    friend constexpr MInt operator/(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res /= rhs;
        return res;
    }

    friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
        i64 v;
        is >> v;
        a = MInt(v);
        return is;
    }

    friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
        return os << a.val();
    }

    friend constexpr bool operator==(MInt lhs, MInt rhs) {
        return lhs.val() == rhs.val();
    }

    friend constexpr bool operator!=(MInt lhs, MInt rhs) {
        return lhs.val() != rhs.val();
    }
};

template<>
int MInt<0>::Mod = 998244353;

template<int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();

constexpr int P = 1000000007;
using Z = MInt<P>;

/*
 * 组合数(Comb)
 * */
template<typename T>
struct Comb {
    //大质数-->1999999999999999909
    T mod = 1e9 + 7;
    int n = 0;
    std::vector<T> _fac, _inv, _invfac;

    Comb() : n{0}, _fac{1}, _invfac{1}, _inv{0} {}

    explicit Comb(int n) : Comb() {
        init(n);
    }

    T power(T a, i64 b) {
        T ans = 1;
        for (; b; b >>= 1, a = a * a % mod) {
            if (b & 1) ans = ans * a % mod;
        }
        return ans;
    }

    void init(int m) {
        if (m <= n) return;
        _fac.resize(m + 1);
        _inv.resize(m + 1);
        _invfac.resize(m + 1);
        _fac[0] = _inv[0] = _invfac[0] = 1;
        for (int i = n + 1; i <= m; i++) {
            _fac[i] = _fac[i - 1] * i % mod;
        }
        _invfac[m] = power(_fac[m], mod - 2);
        for (int i = m; i > n; i--) {
            _invfac[i - 1] = _invfac[i] * i % mod;
            _inv[i] = _invfac[i] * _fac[i - 1] % mod;
        }
        n = m;
    }

    T sub(T a, T b) {
        return ((a - b) % mod + mod) % mod;
    }

    T fac(int m) {
        if (m > n) init(m);
        return _fac[m];
    }

    T invfac(int m) {
        if (m > n) init(m);
        return _invfac[m];
    }

    T inv(int m) {
        if (m > n) init(m);
        return _inv[m];
    }

    T binom(int _n, int m) {
        if (_n < 0 || m < 0 || _n < m) return 0;
        return fac(_n) * invfac(m) % mod * invfac(_n - m) % mod;
    }

    T perm(int _n, int m) {
        if (_n < 0 || m < 0 || _n < m) return 0;
        return fac(_n) * invfac(_n - m) % mod;
    }

    T lucas(i64 _n, i64 m) {
        if (m == 0) return 1;
        return lucas(_n / mod, m / mod) * binom(_n % mod, m % mod) % mod;
    }

    T catalan(int _n) {
        return sub(binom(_n * 2, _n), binom(_n * 2, _n - 1));
    }

    T catalan(int _n, int m, int k) { //对于任意的i属于(_n+m)时，_n<=m+k,即n最多比m多k个的方案数
        if (_n > m + k) return 0;
        return sub(binom(_n + m, m), binom(_n + m, m + k + 1));
    }
};

void DAOQI() {
    int n, m;
    std::cin >> n >> m;
    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }
    Z ans = 1;
    Comb<i64> comb;
    for (int i = 1; i <= n; i++) {
        ans *= comb.binom(a[i] + m + 1 - 1, m);
    }
    std::cout << ans << "\n";
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T = 1;
    //std::cin >> T;
    while (T--) DAOQI();
    return 0;
}

E 小柒的神器

第一步,我们怎么判断一个区间的神器是否可以成功融合在一起呢，那么我们可以转化一下思路。若区间中的所有神奇都可以融合在一起，那么对于所有的来说，和也必然可以融合，所以我们可以判断这个区间的所有的和是否可以通过融合关系融合。

假设你要判断两个神器与神器能否通过一系列关系进入同一个集合，那么这个操作是很经典的并查集的操作。我们可以用一个数组来记录和是否能够连接，若能则记为0,不能则记为inf(一个极大值),那么我们跑一边st表之后，若query(l,r-1)的值为inf,则说明这个区间有两个相邻的神器不能融合，则这个区间内的神器不能全部融合。否则可以。

那么接下来想一下融合的最大代价是多少，同样这个区间的神器融合的最大代价也可以通过两个相邻的神器融合的代价取最大值得出，即若和可以融合的最小代价为v，则让.

两个神器融合的最小代价怎么求呢，可以理解为神器可以通过一系列关系到达 ，这些关系形成一条路径，那么最小代价就是这条路径上的最大值。那么我们肯定要让这个最大值尽可能小，那么这个就是最小瓶颈路了。那么如何快速求出这个值呢。这其实就是kruskal重构树的板子题了。

#include<bits/stdc++.h>

using i64 = long long;

template<typename T, typename Compare=std::less<>>
struct MST {
    int n;
    std::vector<std::vector<int>> adj;
    std::vector<T> val;
    std::vector<std::tuple<T, int, int>> E;
    std::vector<int> fa, doc, dep;
    std::vector<std::array<int, 25>> f;

    MST(int n_) : n(n_) {};

    void addEdge(int u, int v, T w) {
        E.emplace_back(w, u, v);
    }

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

    T Kruskal(Compare comp = Compare()) {
        if (fa.empty())fa.assign(n, 0);
        iota(fa.begin(), fa.end(), 0);
        doc.clear();
        sort(E.begin(), E.end(), comp);
        T ans = 0;
        int cnt = 0;

        for (int i = 0; i < E.size(); i++) {
            auto [w, u, v] = E[i];
            int fu = find(u), fv = find(v);

            if (fu != fv) {
                fa[fu] = fv;
                doc.push_back(i);
                ans += w;
                cnt++;
            }
            if (cnt == n - 2) return ans;
        }
        return -1;
    }

    int KruskalRsTree() {
        fa.assign(2 * n - 2, 0);
        std::iota(fa.begin(), fa.end(), 0);
        adj.resize(2 * n - 2);
        val.resize(2 * n - 2);

        for (int i = 0; i < doc.size(); i++) {
            auto [w, u, v] = E[doc[i]];
            adj[n + i].emplace_back(find(u));
            adj[n + i].emplace_back(find(v));
            val[n + i] = w;
            fa[find(u)] = fa[find(v)] = n + i;
        }

        return n + doc.size() - 1;
    }

    void dfs(int u) {
        if (f.empty()) {
            f.assign(adj.size(), {});
            dep.assign(adj.size(), 1);
        }
        for (int i = 1; dep[u] && i <= std::__lg(dep[u]); i++) {
            f[u][i] = f[f[u][i - 1]][i - 1];
        }
        for (int v: adj[u]) {
            if (v == fa[u]) continue;
            dep[v] = dep[u] + 1;
            f[v][0] = u;
            dfs(v);
        }
    }

    void work() {
        for (int i = 1; i < fa.size(); i++) {
            if (fa[i] == i) {
                dfs(i);
            }
        }
    }

    int lca(int u, int v) {
        if (dep[u] < dep[v]) std::swap(u, v);
        for (int i = 24; i >= 0; i--) {
            if (dep[f[u][i]] >= dep[v]) {
                u = f[u][i];
            }
        }
        if (u == v) return v;

        for (int i = 24; i >= 0; i--) {
            if (f[u][i] != f[v][i]) {
                u = f[u][i], v = f[v][i];
            }
        }
        return f[u][0];
    }

    T dist(int u, int v) {
        return val[lca(u, v)];
    }
};

template<class T>
struct RMQ {
    int n;
    std::vector<T> a;
    std::vector<std::array<T, 30>> f;
    std::function<T(T, T)> func;

    RMQ() {};

    RMQ(std::vector<T> init_, std::function<T(T, T)> func_) {
        work(init_, func_);
    }

    void work(std::vector<T> &init_) {
        work(init_, [&](T x, T y) { return std::max(x, y); });
    }

    void work(std::vector<T> &init_, std::function<T(T, T)> func_) {
        this->a = init_;
        this->func = func_;
        this->n = a.size();
        this->f.assign(n, {});
        for (int i = 0; i < n; i++) f[i][0] = a[i];
        for (int j = 1; j <= std::__lg(n) + 1; j++) {
            for (int i = 0; i + (1 << j) - 1 < n; i++) {
                f[i][j] = func(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
            }
        }
    }

    T query(int l, int r) {
        int k = std::__lg(r - l + 1);
        return func(f[l][k], f[r - (1 << k) + 1][k]);
    }
};

/**
 * 并查集
 */
struct DSU {
    std::vector<int> fa, siz;

    DSU() {}

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

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

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

    bool same(int x, int y) {
        return find(x) == find(y);
    }

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

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

void DAOQI() {
    int n, m, q;
    std::cin >> n >> m >> q;
    MST<i64> mst(n + 1);
    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }
    DSU dsu(n + 1);
    for (int i = 1; i <= m; i++) {
        int u, v;
        std::cin >> u >> v;
        dsu.merge(u, v);
        mst.addEdge(u, v, a[u] + a[v]);
    }
    mst.Kruskal();
    mst.KruskalRsTree();
    mst.work();
    std::vector<i64> ans(n + 1);
    for (int i = 1; i < n; i++) {
        if (dsu.same(i, i + 1)) {
            ans[i] = mst.dist(i, i + 1);
        } else {
            ans[i] = 1e18;
        }
    }
    RMQ<i64> rmq;
    rmq.work(ans);
    while (q--) {
        int l, r;
        std::cin >> l >> r;
        if (l == r) {
            std::cout << 0 << "\n";
            continue;
        }
        i64 res = rmq.query(l, r - 1);
        if (res >= 1e18) {
            std::cout << -1 << "\n";
        } else {
            std::cout << res << "\n";
        }
    }
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T = 1;
    //std::cin >> T;
    while (T--) DAOQI();
    return 0;
}

思路二

本题如果时间加上秒则可使用这个方法通过，即分块思想加可撤销并查集，看代码。

#include<bits/stdc++.h>

using i64 = long long;

/**   可撤销并查集（DSU With Rollback）
**/
struct DSU {
    int n;
    std::vector<int> siz, f;
    std::vector<std::array<int, 2>> his;

    DSU(int _n = 1) {
        init(_n);
    }

    void init(int _n) {
        this->n = _n;
        siz.assign(n, 1);
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
    }

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

    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        if (siz[x] < siz[y]) {
            std::swap(x, y);
        }
        his.push_back({x, y});
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }

    int time() {
        return his.size();
    }

    void revert(int tm) {
        while (his.size() > tm) {
            auto [x, y] = his.back();
            his.pop_back();
            f[y] = y;
            siz[x] -= siz[y];
        }
    }

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

    bool same(int u, int v) {
        return find(u) == find(v);
    }
};

template<class T>
struct SparseTable {
    int n;
    std::vector<T> a;
    std::vector<std::array<T, 30>> f;
    std::function<T(T, T)> func;

    SparseTable() {};

    SparseTable(std::vector<T> init_, std::function<T(T, T)> func_) {
        work(init_, func_);
    }

    void work(std::vector<T> &init_) {
        work(init_, [&](T x, T y) { return std::max(x, y); });
    }

    void work(std::vector<T> &init_, std::function<T(T, T)> func_) {
        this->a = init_;
        this->func = func_;
        this->n = a.size();
        this->f.assign(n, {});
        for (int i = 0; i < n; i++) f[i][0] = a[i];
        for (int j = 1; j <= std::__lg(n) + 1; j++) {
            for (int i = 0; i + (1 << j) - 1 < n; i++) {
                f[i][j] = func(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
            }
        }
    }

    T query(int l, int r) {
        int k = std::__lg(r - l + 1);
        return func(f[l][k], f[r - (1 << k) + 1][k]);
    }
};

constexpr i64 inf = 1e17;

void DAOQI() {
    int n, m, q;
    std::cin >> n >> m >> q;
    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }
    std::vector<std::array<int, 3>> e(m + 1);
    for (int i = 1; i <= m; i++) {
        int u, v;
        std::cin >> u >> v;
        e[i] = {u, v, a[u] + a[v]};
    }
    std::sort(e.begin() + 1, e.end(), [&](auto &x, auto &y) {
        return x[2] < y[2];
    });

    int siz = static_cast<int>(std::sqrt(m));
    DSU dsu(n + 1);
    std::vector<DSU> dsus;
    dsus.push_back(dsu);
    for (int i = 1; i <= m; i += siz) {
        int k = (i - 1) / siz + 1;
        for (int j = i; j <= std::min(m, k * siz); j++) {
            auto &[u, v, w] = e[j];
            dsu.merge(u, v);
        }
        dsus.push_back(dsu);
    }
    int M = dsus.size() - 1;
    std::vector<i64> tmp(n + 1);
    for (int i = 1; i < n; i++) {
        if (!dsus.back().same(i, i + 1)) {
            tmp[i] = inf;
            continue;
        }
        for (int j = M; j >= 0; j--) {
            if (dsus[j].same(i, i + 1)) continue;
            int tim = dsus[j].time();
            for (int k = j * siz + 1; k <= m; k++) {
                auto &[u, v, w] = e[k];
                dsus[j].merge(u, v);
                if (dsus[j].same(i, i + 1)) {
                    tmp[i] = w;
                    break;
                }
            }
            dsus[j].revert(tim);
            break;
        }
    }
    SparseTable<i64> st;
    st.work(tmp);
    for (int i = 1; i <= q; i++) {
        int l, r;
        std::cin >> l >> r;
        if (l == r) {
            std::cout << 0 << "\n";
            continue;
        }
        i64 res = st.query(l, r - 1);
        std::cout << (res == inf ? -1 : res) << "\n";
    }
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T = 1;
    //std::cin >> T;
    while (T--) DAOQI();
    return 0;
}

F 小柒的颜色

本题是一道比较典的回滚莫队题目

那么莫队首先便是分块，对原序列进行分块，以左端点所属的块的id为关键字排序且以右端点从小到大排序。

如果询问左端点所属块和上一个询问左端点所属块的id不同，那么将设为这个询问左端点的所在块的右边界加1，同时设为这个块的右边界

int r = std::min(i * siz, n), ql = r + 1, qr = r;

那么每次块相同的几个询问，我们的qr指针必定是一直向右移动，因为排序的时候按照右端点从小到大排序。那么只有左端点的大小关系不一定。但是这些左端点一定在同一个块中，所以即使我们每次都移动一个整块的长度复杂度也就,所以对于每次在相同块的左端点我们可以让它暴力从开始减。

同时因为qr一定是一直向右移动的，所以我们可以记录当ql=r+1时,qr移动到这个询问的右边界时的答案，这样当下一次qr移动时，就不必重新记录[r+1,qr]的内容了。

那么其余的操作就是普通莫队的操作了，即加这个点该干什么。

#include<bits/stdc++.h>

using i64 = long long;
using l64 = long double;

void DAOQI() {
    int n, m;
    std::cin >> n >> m;
    std::vector<int> a(n + 1), bl(n + 1);
    int siz = std::sqrt(n);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
        bl[i] = (i - 1) / siz + 1;
    }
    std::vector<std::array<int, 3>> q(m + 1);
    for (int i = 1; i <= m; i++) {
        std::cin >> q[i][0] >> q[i][1];
        q[i][2] = i;
    }
    std::sort(q.begin() + 1, q.end(), [&](auto x, auto y) {
        return bl[x[0]] ^ bl[y[0]] ? bl[x[0]] < bl[y[0]] : x[1] < y[1];
    });

    std::vector<std::pair<i64, int>> ans(m + 1);
    std::vector<i64> cnt(n + 1), s(n + 1);
    auto calc = [&](int l, int r) -> std::pair<i64, int> {
        i64 id = 1e9, mx = 0, sum = 0;
        for (int i = l; i <= r; i++) cnt[a[i]] = s[a[i]] = 0;
        for (int i = l; i <= r; i++) {
            s[a[i]] += cnt[a[i]] * a[i];
            sum += cnt[a[i]] * a[i];
            cnt[a[i]]++;
            if (s[a[i]] > mx || (s[a[i]] == mx && a[i] < id)) {
                mx = s[a[i]], id = a[i];
            }
        }
        for (int i = l; i <= r; i++) cnt[a[i]] = s[a[i]] = 0;
        return {sum, id};
    };

    for (int i = 1, x = 1; i <= bl[n]; i++) {
        int r = std::min(i * siz, n), tl = r + 1, tr = r;
        i64 lstsum = 0, lstid = 1e9, tmx = 0;
        for (int j = 1; j <= n; j++) {
            cnt[j] = s[j] = 0;
        }
        for (; x < q.size() && bl[q[x][0]] == i; x++) {
            if (bl[q[x][0]] == bl[q[x][1]]) {
                ans[q[x][2]] = calc(q[x][0], q[x][1]);
                continue;
            }
            while (tr < q[x][1]) {
                tr++;
                s[a[tr]] += cnt[a[tr]] * a[tr];
                lstsum += cnt[a[tr]] * a[tr];
                cnt[a[tr]]++;
                if (s[a[tr]] > tmx || (s[a[tr]] == tmx && a[tr] < lstid)) {
                    tmx = s[a[tr]], lstid = a[tr];
                }
            }
            i64 sum = lstsum, id = lstid, mx = tmx;
            while (tl > q[x][0]) {
                tl--;
                s[a[tl]] += cnt[a[tl]] * a[tl];
                sum += cnt[a[tl]] * a[tl];
                cnt[a[tl]]++;
                if (s[a[tl]] > mx || (s[a[tl]] == mx && a[tl] < id)) {
                    mx = s[a[tl]], id = a[tl];
                }
            }
            ans[q[x][2]] = {sum, id};
            while (tl <= r) {
                cnt[a[tl]]--;
                s[a[tl]] -= cnt[a[tl]] * a[tl];
                tl++;
            }
        }
    }

    for (int i = 1; i <= m; i++) {
        std::cout << ans[i].first << " " << ans[i].second << "\n";
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T = 1;
    //std::cin >> T;
    while (T--) DAOQI();
    return 0;
}
2025最新求职资料大礼包领取
真题
历年笔试真题附答案
2019 PayPal实习生招聘数据科学卷
趋势科技2019秋招技术岗客观题汇总
【2024】贝壳找房秋招产品经理笔试卷2
全部 >
面经
面试常考问题整理
管理类双非硕的23秋招记录＆反思
23届联想面经分享： 秋招上岸
0928携程笔试题解
全部 >
内推
员工内推码获取
拼多多内推 拼多多内推码（可转正）
全部 >
大家都在关注
校招日程表 笔试日历 ai模拟面试 面试宝典 剑指offer 知识点专项练习

全部评论

(5) 回帖
加载中...
话题 回帖
返回全部帖子

本文相关内容

等你来战

查看全部

热门推荐

牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”