基础与搜索

基础模板

// #pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define all(x) (x).begin(), (x).end()
 
constexpr int MOD = 1e9 + 7;
// -9.2e18 ~ 9.2e18
 
void solve()
{
 
}
 
signed main()
{
    cin.tie(0)->ios::sync_with_stdio(0);
    cout << setiosflags(ios::fixed) << setprecision(2);
    int TT = 1;
    // cin >> TT;
    while (TT--)
    {
        solve();
        // cout << endl;
    }
}

离散化

vector<int> vals = a;
sort(all(vals));
vals.erase(unique(all(vals)), vals.end());
int C = vals.size();
vector<int> b(n);
for (int i = 0; i < n; i++)
{
    b[i] = lower_bound(all(vals), a[i]) - vals.begin();
}

二分答案

// 二分答案：找最小的可行值（单调性 false ... false, true ... true）
long long first_true(long long lo, long long hi, auto check) {
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (check(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}
 
// 找最大的可行值（单调性 true ... true, false ... false）
long long last_true(long long lo, long long hi, auto check) {
    while (lo < hi) {
        long long mid = lo + (hi - lo + 1) / 2;
        if (check(mid)) lo = mid;
        else hi = mid - 1;
    }
    return lo;
}

ST 表

// ============================================================
// ST 表 / Sparse Table（静态区间查询，数组使用 1 下标）
// ============================================================
// 支持：min、max、gcd、按位与、按位或、区间和、区间异或。
// 数组建立后不能修改；有修改操作时应使用线段树或树状数组。
//
// 用法：
//   vector<int> v(n + 1); // v[1..n]
//   STTable st(v, ST_MAX);
//   cout << st.query(l, r);
//
// min/max/gcd/and/or 查询是 O(1)：
//   它们允许用两个可能重叠的区间覆盖 [l,r]，重复计算不影响答案。
//
// sum/xor 查询是 O(log n)：
//   它们不能重复计算，所以要把 [l,r] 拆成互不重叠的 2 的幂区间。
//   实际做题时，静态 sum 推荐前缀和，静态 xor 推荐前缀异或，会比 ST 表更简单。
//
// 建表 O(n log n)，空间 O(n log n)。
// ============================================================
 
enum STMode
{
    ST_MIN,
    ST_MAX,
    ST_GCD,
    ST_AND,
    ST_OR,
    ST_SUM,
    ST_XOR
};
 
class STTable
{
private:
    int n, LOG;
    STMode mode;
 
    // st[j][i] 表示区间 [i, i + 2^j - 1] 的答案。
    vector<vector<int>> st;
 
    // 合并左右两个区间的答案。
    int merge(int left, int right) const
    {
        if (mode == ST_MIN)
        {
            return min(left, right);
        }
        if (mode == ST_MAX)
        {
            return max(left, right);
        }
        if (mode == ST_GCD)
        {
            return gcd(left, right);
        }
        if (mode == ST_AND)
        {
            return left & right;
        }
        if (mode == ST_OR)
        {
            return left | right;
        }
        if (mode == ST_SUM)
        {
            return left + right;
        }
        return left ^ right;
    }
 
    // 这些运算重复计算同一个元素不会改变答案，可以使用 O(1) 重叠查询。
    bool can_overlap() const
    {
        return mode == ST_MIN or mode == ST_MAX or mode == ST_GCD or
               mode == ST_AND or mode == ST_OR;
    }
 
public:
    // v 使用 1 下标，v[0] 空置。
    STTable(const vector<int> &v, STMode mode)
        : n(v.size() - 1), LOG(__lg(max(1ll, n)) + 1), mode(mode),
          st(LOG, vector<int>(n + 1))
    {
        for (int i = 1; i <= n; i++)
        {
            st[0][i] = v[i];
        }
 
        // 两个长度为 2^(j-1) 的相邻区间，合并成长度为 2^j 的区间。
        for (int j = 1; j < LOG; j++)
        {
            int half = 1ll << (j - 1);
            int len = 1ll << j;
            for (int i = 1; i + len - 1 <= n; i++)
            {
                st[j][i] = merge(st[j - 1][i], st[j - 1][i + half]);
            }
        }
    }
 
    // 查询闭区间 [l,r]，要求 1 <= l <= r <= n。
    int query(int l, int r) const
    {
        if (can_overlap())
        {
            int k = __lg(r - l + 1);
            return merge(st[k][l], st[k][r - (1ll << k) + 1]);
        }
 
        // sum/xor：从左到右取互不重叠的区间。
        int ans = 0;
        int pos = l;
        for (int j = LOG - 1; j >= 0; j--)
        {
            int len = 1ll << j;
            if (pos + len - 1 <= r)
            {
                ans = merge(ans, st[j][pos]);
                pos += len;
            }
        }
        return ans;
    }
};