Chillee

static char buf[450 << 20];
void *operator new(size_t s) {
    static size_t i = sizeof buf;
    assert(s < i);
    return (void *)&buf[i -= s];
}
void operator delete(void *) {}

Chillee

int sz[MAXN];
int cpar[MAXN];
bool dead[MAXN];
int sizedfs(int cur, int p) {
    sz[cur] = 1;
    for (auto i : adj[cur]) {
        if (i != p && !dead[i])
            sz[cur] += sizedfs(i, cur);
    }
    return sz[cur];

Chillee

template <int MAXN> struct LCA { // O(log N) queries
    const static int MAXB = 33 - __builtin_clz(MAXN);
    int tin[MAXN], tout[MAXN], depth[MAXN], timer = 0;
    int pars[MAXN][MAXB];
    void calc(vector<int> adj[], int cur = 0, int p = 0, int d = 0) {
        depth[cur] = d;
        tin[cur] = ++timer;
        pars[cur][0] = p;
        for (int d = 1; d < MAXB; d++)
            pars[cur][d] = pars[pars[cur][d - 1]][d - 1];

Chillee

double simpson(function<double(double)> f, double a, double b) {
    double c = (a + b) / 2;
    return (b - a) / 6 * (f(a) + 4 * f(c) + f(b));
}
double rec(function<double(double)> f, double a, double b, double eps, double S, bool rel = true) {
    double c = (a + b) / 2;
    double S1 = simpson(f, a, c), S2 = simpson(f, c, b), T = S1 + S2;
    if (abs(T - S) <= 15 * eps || b - a < 1e-10 || (rel && abs((T - S) / S) <= 15 * eps))
        return T + (T - S) / 15;
    return rec(f, a, c, eps / 2, S1, rel) + rec(f, c, b, eps / 2, S2, rel);

Chillee

array<vector<int>, 2> manacher(string &s) { // (even, odd)
    int n = s.size();
    array<vector<int>, 2> p = {vector<int>(n), vector<int>(n)};
    for (int z = 0, l = 0, r = 0; z < 2; z++, l = 0, r = 0)
        for (int i = 0; i < n; i++) {
            if (i < r)
                p[z][i] = min(r - i + !z, p[z][l + r - i + !z]);
            int L = i - p[z][i], R = i + p[z][i] - !z;
            while (L - 1 >= 0 && R + 1 < n && s[L - 1] == s[R + 1])
                p[z][i]++, L--, R++;

Chillee

int gauss(vector<vector<double>> a, vector<double> &ans) {
    const double EPS = 1e-6;
    int n = (int)a.size();
    int m = (int)a[0].size() - 1;

    vector<int> where(m, -1);
    for (int col = 0, row = 0; col < m && row < n; ++col) {
        int sel = row;
        for (int i = row; i < n; ++i)
            if (abs(a[i][col]) > abs(a[sel][col]))

Chillee

int mobius[MAXPR];
bool sieve[MAXPR];
vector<int> primes;
void calcMobius() {
    mobius[1] = 1;
    for (int i = 2; i < MAXPR; i++) {
        if (!sieve[i]) {
            primes.push_back(i);
            mobius[i] = -1;
        }

Chillee

struct SuffixArray { // sa[0] = n, sa[i] = i-th in sorted suffix array. O(n log n)
#define rep(i, a, b) for (int i = a; i < (b); i++)
    vector<int> sa, lcp;
    SuffixArray(string &s, int lim = 256) { // no null characters, use basic_string<int> to extend
        int n = s.size() + 1, k = 0, a, b;
        vector<int> x(all(s) + 1), y(n), ws(max(n, lim)), rank(n);
        sa = lcp = y, iota(all(sa), 0);
        for (int j = 0, p = 0; p < n; j = max(1, j * 2), lim = p) {
            p = j, iota(all(y), n - j);
            rep(i, 0, n) if (sa[i] >= j) y[p++] = sa[i] - j;

Chillee

struct Line {
    mutable ll m, b, p;
    bool operator<(const Line &o) const { return m < o.m; }
    bool operator<(const ll &x) const { return p < x; }
};

struct LineContainer : multiset<Line, less<>> { // upper convex hull.
    // (for doubles, use inf = 1/.0, div(a,b) = a/b)
    const ll inf = LLONG_MAX;
    ll div(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); }

Chillee

vector<int> ans;
for (auto x : A) {
    auto it = lower_bound(ans.begin(), ans.end(), x);
    if (it == ans.end())
        ans.push_back(x);
    else
        *it = x;
}