算法

(莫队) $O(n\sqrt{q})$

本题依旧是普通莫队板题
可以先离散化一下，虽然用 std::map 也可以过

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

// Coodinate Compression
template<typename T=int>
struct CC {
  bool initialized;
  vector<T> xs;
  CC(): initialized(false) {}
  void add(T x) { xs.push_back(x);}
  void init() {
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(),xs.end()),xs.end());
    initialized = true;
  }
  int operator()(T x) {
    if (!initialized) init();
    return upper_bound(xs.begin(), xs.end(), x) - xs.begin() - 1;
  }
  T operator[](int i) {
    if (!initialized) init();
    return xs[i];
  }
  int size() {
    if (!initialized) init();
    return xs.size();
  }
};

int main() {
    cin.tie(nullptr) -> sync_with_stdio(false);

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

    CC cc;
    vector<int> a(n);
    rep(i, n) {
        cin >> a[i];
        cc.add(a[i]);
    }
    rep(i, n) a[i] = cc(a[i]);

    vector<int> l(q), r(q);
    rep(i, q) cin >> l[i] >> r[i];
    rep(i, q) l[i]--, r[i]--;

    vector<int> qs(q);
    iota(qs.begin(), qs.end(), 0);
    const int D = n/sqrt(q)+1;
    sort(qs.begin(), qs.end(), [&](int i, int j) {
        if (r[i]/D == r[j]/D) return l[i] < l[j];
        return r[i] < r[j];
    });

    vector<int> ans(q);
    int nl = 0, nr = -1;
    int now = 0;
    vector<int> cnt(n);
    auto add = [&](int i) {
        now += cnt[a[i]] == 1;
        now -= cnt[a[i]] == 2;
        cnt[a[i]]++;
    };
    auto del = [&](int i) {
        now += cnt[a[i]] == 3;
        now -= cnt[a[i]] == 2;
        cnt[a[i]]--;
    };
    for (int qi : qs) {
        while (nl < l[qi]) del(nl), nl++;
        while (nl > l[qi]) nl--, add(nl);
        while (nr < r[qi]) nr++, add(nr);
        while (nr > r[qi]) del(nr), nr--;
        ans[qi] = now;
    }

    rep(i, q) cout << ans[i] << '\n';

    return 0;
}

算法

(st表)

本题只需静态查询区间最小值即可！st表板题

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

template<class D, class OP>
struct SparseTable {
    D e;
    OP op;
    vector<vector<D>> data;
    SparseTable(vector<D> v = vector<D>(), D _e = D(), OP _op = OP()): e(_e), op(_op) {
        int n = v.size();
        if (n == 0) return;
        int lg = 31 - __builtin_clz(unsigned(n)) + 1;
        data = vector<vector<D>>(lg);
        data[0] = v;
        int l = 1;
        for (int s = 1; s < lg; ++s) {
            data[s] = vector<D>(n);
            rep(i, n-l) {
                data[s][i] = op(data[s-1][i], data[s-1][i+l]);
            }
            l <<= 1;
        }
    }
    D query(int l, int r) const {
        assert(l <= r);
        if (l == r) return e;
        int u = 31 - __builtin_clz(unsigned(r-l));
        return op(data[u][l], data[u][r-(1<<u)]);
    }
};

template<class D, class OP>
SparseTable<D, OP> get_sparse_table(vector<D> v, D e, OP op) {
    return SparseTable<D, OP>(v, e, op);
}

inline int read() {
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}

int main() {
    int n = read(), q = read();

    vector<int> a(n);
    rep(i, n) a[i] = read();

    const int INF = 1001001001;
    auto st = get_sparse_table(a, INF, [&](int x, int y) { return min(x, y); });
    rep(qi, q) {
        int l = read()-1, r = read();
        cout << st.query(l, r) << '\n';
    }

    return 0;
}

using ll = long long;
class Solution {
public:
    long long repairCars(vector<int>& ranks, int cars) {
        ll wa = 0, ac = 1e15;
        while (ac-wa > 1) {
            ll wj = (ac+wa)/2;
            auto ok = [&]{
                ll cnt = 0;
                for (int r : ranks) {
                    cnt += sqrt(wj/r);
                }
                return cnt >= cars;
            }();
            if (ok) ac = wj; else wa = wj;
        }
        return ac;
    }
};

#define rep(i, n) for (int i = 0; i < (n); ++i)
class Solution {
public:
    vector<int> evenOddBit(int n) {
        int even = 0, odd = 0;
        rep(i, 10) if (n>>i&1) {
            if (i&1) odd++; else even++;
        }
        return {even, odd};
    }
};

class Solution {
public:
    int A(int x, int y) {
        int res = 1;
        for (int i = 0; i < x; ++i) {
            res *= y--;
        }
        return res;
    }
    int f(int mask, const string& s, int i, bool same) {
        if (i == s.size()) return 1;
        int t = same ? s[i]-'0' : 9, res = 0, c = __builtin_popcount(mask)+1;
        for (int k = 0; k <= t; ++k) {
            if (mask>>k&1) continue;
            if (same and k == t) res += f(mask|(1<<t), s, i+1, true);
            else if (mask == 0 and k == 0) res += f(0, s, i+1, false);
            else res += A(s.size()-1-i, 10-c);
        }
        return res;
    }
    int numDupDigitsAtMostN(int n) {
        string s = to_string(n);
        return n + 1 - f(0, s, 0, true);
    }
};

#define rep(i, n) for (int i = 0; i < (n); ++i)
using P = pair<int, int>;
class Solution {
public:
    bool checkValidGrid(vector<vector<int>>& grid) {
        if (grid[0][0]) return false;
        int n = grid.size();
        vector<P> idx(n*n);
        rep(i, n)rep(j, n) idx[grid[i][j]] = P(i, j);
        for (int i = 1; i < n*n; ++i) {
            int dx = idx[i].first - idx[i-1].first;
            int dy = idx[i].second - idx[i-1].second;
            if ((abs(dx) == 1 and abs(dy) == 2) or (abs(dx) == 2 and abs(dy) == 1)) continue;
            return false;
        }
        return true;
    }
};

#define rep(i, n) for (int i = 0; i < (n); ++i)
class Solution {
public:
    int beautifulSubsets(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> invalid(n);
        rep(i, n)rep(j, n) {
            if (abs(nums[i]-nums[j]) == k) invalid[i] |= 1<<j;
        }
        int res = 0;
        for (int s = 1; s < (1<<n); ++s) {
            bool ok = true;
            rep(i, n) if (s>>i&1) {
                if (s&invalid[i]) ok = false;
            }
            if (ok) res++;
        }
        return res;
    }
};

class Solution {
public:
    int findSmallestInteger(vector<int>& nums, int value) {
        vector<int> v(value);
        for (const int num : nums) {
          ++v[(num % value + value) % value];
        }
        int mex = 0;
        while (v[mex % value] > 0) --v[mex++ % value];
        return mex;
    }
};

算法分析

暴力 $\operatorname{bfs}$ 的复杂度为 $O(H^2W^2)$

考虑优化：

注意到，使用同一个字母的传送器两次显然是没用的，所以如果你使用了一次传送器，接下来你就不能再使用那个字母了！
时间复杂度可以降为 $O(HW)$

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using P = pair<int, int>;

const int INF = 1001001001;
const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, 1, 0, -1};

int main() {
    int h, w;
    cin >> h >> w;

    vector<string> s(h);
    rep(i, h) cin >> s[i];

    vector dist(h, vector(w, INF));
    queue<P> q;
    rep(i, h)rep(j, w) {
        if (s[i][j] == 'S') {
            q.emplace(i, j);
            dist[i][j] = 0;
        }
    }
    vector<vector<P>> warps(256);
    rep(i, h)rep(j, w) warps[s[i][j]].emplace_back(i, j);

    while (q.size()) {
        auto [i, j] = q.front(); q.pop();
        if (s[i][j] == 'G') {
            cout << dist[i][j] << '\n';
            return 0;
        }
        rep(v, 4) {
            int ni = i+di[v], nj = j+dj[v];
            if (ni < 0 or ni >= h or nj < 0 or nj >= w) continue;
            if (s[ni][nj] == '#') continue;
            if (dist[ni][nj] != INF) continue;
            dist[ni][nj] = dist[i][j]+1;
            q.emplace(ni, nj);
        }

        if (islower(s[i][j])) {
            for (auto [ni, nj] : warps[s[i][j]]) {
                if (dist[ni][nj] != INF) continue;
                dist[ni][nj] = dist[i][j]+1;
                q.emplace(ni, nj);
            }
            warps[s[i][j]].clear();
        }
    }

    puts("-1");

    return 0;
}