11 杂项

11.1 快读

char buf[1 << 20], *p1, *p2;
char gc() {
    return p1 == p2 ? p2 = buf + fread(p1 = buf, 1, 1 << 20, stdin), (p1 == p2) ? EOF : *p1++ : *p1++;
}
inline int read(int f = 1, char c = gc(), int x = 0) {
    while (c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = gc();
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc();
    return f * x;
}

11.2 调试

void pv(const T& v) {
    if constexpr (is_same_v<T, vector<int>>) {
        for (auto i : v) cout << i << " ";
    } else {
        cerr << v;
    }
}
#define debug(v) cerr << #v << " = ", pv(v), cerr << endl

11.3 __int128

#include <bits/stdc++.h>
using namespace std;

using i128 = __int128;

ostream& operator<<(ostream& os, i128 x) {
    if (x < 0) {
        os << "-";
        x = -x;
    }
    if (x == 0) return os << 0;
    string s;
    while (x) {
        s += char('0' + x % 10);
        x /= 10;
    }
    reverse(s.begin(), s.end());
    return os << s;
}

istream& operator>>(istream& is, i128& x) {
    string s; is >> s;
    x = 0;
    for (auto c : s) {
        x = x * 10 + c - '0';
    }
    return is;
}

i128 sqrti128(i128 x) {
    i128 lo = 0, hi = 1e18;
    while (lo < hi) {
        i128 mid = (lo + hi + 1) / 2;
        if (mid * mid <= x) {
            lo = mid;
        } else {
            hi = mid - 1;
        }
    }
    return lo;
}

11.4 实数域二分

for (int t = 1; t <= 100; t++) {
    ld mid = (l + r) / 2;
    if (judge(mid)) r = mid;
    else l = mid;
}
cout << l << endl;

11.5 整数域三分

这段代码求的是极小值，极大值需要改变不等号方向。

while (l < r) {
    int mid = (l + r) / 2;
    if (check(mid) <= check(mid + 1)) r = mid; // <========= 注意不等号方向
    else l = mid + 1;
}
cout << check(l) << endl;

11.6 实数域三分

ld l = -1E9, r = 1E9;
for (int t = 1; t <= 100; t++) {
    ld mid1 = (l * 2 + r) / 3;
    ld mid2 = (l + r * 2) / 3;
    if (judge(mid1) < judge(mid2)) {
        r = mid2;
    } else {
        l = mid1;
    }
}
cout << l << endl;

11.7 pb_ds

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

// ordered_set: 支持 order_of_key / find_by_order
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int main() {
    // 普通有序集合
    ordered_set<int> os;
    os.insert(5);
    os.insert(1);
    os.insert(7);
    os.insert(3);
    // find_by_order(k): 返回第 k (0-based) 小元素的迭代器
    cout << "2nd: " << *os.find_by_order(2) << "\n"; // 5

    // order_of_key(x): 返回集合中严格小于 x 的元素个数
    cout << "count < 5: " << os.order_of_key(5) << "\n"; // 2 (1,3)

    // 删除
    os.erase(3);
    cout << "after erase 3, count < 5: " << os.order_of_key(5) << "\n"; // 1
}

11.8 日期换算（基姆拉尔森公式）

已知年月日，求星期数。

int week(int y,int m,int d){
    if(m<=2)m+=12,y--;
    return (d+2*m+3*(m+1)/5+y+y/4-y/100+y/400)%7+1;
}

11.9 自适应辛普森法（Simpson）

二维平面上的曲线长度 $$ L = ∫_a^b \sqrt{1 + (f'(x))^2} dx $$

\[ L = ∫_{t1}^{t2} \sqrt{(dx/dt)^2 + (dy/dt)^2} dt \]

const int MAX_DEPTH = 60;

double simpson(double l, double r) {
    return (f(l) + 4.0 * f((l + r) / 2.0) + f(r)) * (r - l) / 6.0;
}

double integral_rec(double l, double r, double eps, double st, int depth) {
    double mid = (l + r) / 2.0;
    double sl = simpson(l, mid), sr = simpson(mid, r);
    double I = sl + sr;
    double err = fabs(I - st) / 15.0; // 估计的误差

    // 复合绝对/相对容差
    double tol = max(eps, eps * fabs(I)); // 或：max(abs_tol, rel_tol * fabs(I))

    if (err <= tol || depth >= MAX_DEPTH) {
        return I + (I - st) / 15.0; // Richardson 修正
    }
    return integral_rec(l, mid, eps / 2.0, sl, depth + 1)
         + integral_rec(mid, r, eps / 2.0, sr, depth + 1);
}

double integral(double l, double r, double EPS) {
    double s = simpson(l, r);
    return integral_rec(l, r, EPS, s, 0);
}

11.10 整数除法

int floordiv(int x, int y) {
    int q = x / y;
    if (x % y and (x > 0) != (y > 0)) q--;
    return q;
}
int ceildiv(int x, int y) {
    int q = x / y;
    if (x % y and (x > 0) == (y > 0)) q++;
    return q;
}