转载请注明出处

杂项

卡时

有一个 clock() 函数，返回程序运行时间。

while ((double)clock()/CLOCKS_PER_SEC < MAX_TIME) action();

这样子就会一直跑action，直到用时即将超过时间限制

MAX_TIME 是一个自定义的略小于时限的数（秒）

O1快速乘

inline LL qmul(LL x, LL y, LL p) {
    LL z = (LD) x / p * y;
    LL res = (ULL) x * y - (ull) z * p;
    return (res + p) % p;
}

随机数生成器

static mt19937 gen(time(nullptr));
//static mt19937 gen(chrono::steady_clock::now().time_since_epoch().count()); //更高精度的时间戳增加随机性
inline int randInt(int l, int r) {                  // 支持负数, 范围[l, r]
    uniform_int_distribution<int> d(l, r);          // 确保分布均匀
    return d(gen);
}

inline double randDouble(double l, double r) {     // 支持负数, 范围[l, r)
    uniform_real_distribution<double> d(l, r);     // 确保分布均匀
    return d(gen);
}

any_hash (用于 unordered_map, unordered_set等防止哈希冲突，以及使其支持PII)

struct any_hash {
    static size_t get_seed() {
        static const size_t sd = []() {
            mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
            return static_cast<size_t>(rng());
        }();
        return sd;
    }

    template<typename T>
    size_t operator()(const T &x) const {
        return hash<T>{}(x) ^ (get_seed() + 0x9e3779b9 + (x << 6) + (x >> 2));
    }

    template<typename T1, typename T2>
    size_t operator()(const pair<T1, T2> &p) const {
        size_t hash1 = (*this)(p.first);
        size_t hash2 = (*this)(p.second);
        return hash1 ^ (hash2 + get_seed() + 0x9e3779b9 + (hash1 << 6) + (hash1 >> 2));
    }
};

离散化

insert 之后请务必先 build 再 get

struct Discretizer {
    vector<int> a;

    inline void insert(int x) { a.push_back(x); }

    void build() {
        sort(a.begin(), a.end());
        a.resize(unique(a.begin(), a.end()) - a.begin());
    }

    inline int get(int x) { return lower_bound(a.begin(), a.end(), x) - a.begin() + 1; }
};

数据结构

莫队

基础莫队(极限数据量 $5 \times 10^5$/s)

vector<int> pos(50005), ans(50005), cnt(50005), a(50005);

struct XX {
    int L, R, p;
} q[200005];

bool cmp(XX A, XX B) {
    if (pos[A.L] != pos[B.L])return pos[A.L] < pos[B.L];
    if (pos[A.L] & 1) return A.R > B.R;
    else return A.R < B.R;
}
int A = 0;
inline void add(int x) {
    A -= cnt[a[x]] * cnt[a[x]];
    ++cnt[a[x]];
    A += cnt[a[x]] * cnt[a[x]];
}

inline void del(int x) {
    A -= cnt[a[x]] * cnt[a[x]];
    --cnt[a[x]];
    A += cnt[a[x]] * cnt[a[x]];
}

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    int block = sqrt(n);  //块长
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        pos[i] = i / (block + 1);    //索引所属块
    }
    for (int i = 0; i < m; ++i) {
        cin >> q[i].L >> q[i].R;
        q[i].p = i;
        --q[i].L, --q[i].R;
    }
    sort(q, q + m, cmp);
    int zl = 0, zr = -1;
    for (int i = 0; i < m; ++i) {    //该处放"暴力求解"代码
        while (zl < q[i].L) del(zl++);
        while (zr > q[i].R) del(zr--);
        while (zl > q[i].L) add(--zl);
        while (zr < q[i].R) add(++zr);
        ans[q[i].p] = A;
    }
    for (int i = 0; i < m; ++i) {
        cout << ans[i] << endl;
    }
}

莫队+分块求区间MEX(离线)

const int N = 2e5 + 10, NN = 500;

vector<int> cnt(200005), a(200005), pos(200005), ans(200005), b(502);
struct XX {
    int L, R, id;
} q[200005];

bool cmp(XX A, XX B) {
    if (pos[A.L] != pos[B.L]) return A.L < B.L;
    else {
        if (pos[A.L] & 1) return A.R > B.R;
        else return A.R < B.R;
    }
}

inline void add(int p) {
    if (++cnt[a[p]] == 1) ++b[a[p] / NN];
}

inline void del(int p) {
    if (--cnt[a[p]] == 0) --b[a[p] / NN];
}

inline int check() {
    for (int i = 0; i < 501; ++i) {
        if (b[i] != NN) {
            for (int j = NN * i; j < 200005; ++j) {
                if (!cnt[j]) return j;
            }
        }
    }
}

void solve() {
    int n, m;
    cin >> n >> m;
    int block = static_cast<int>(sqrt(n));
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        pos[i + 1] = i / (block + 1);
    }

    for (int i = 0; i < m; ++i) {
        cin >> q[i].L >> q[i].R;
        q[i].id = i;
    }
    sort(q, q + m, cmp);
    int L = 1, R = 0;
    for (int i = 0; i < n; ++i) {
        while(L < q[i].L) del(L++);
        while(L > q[i].L) add(--L);
        while(R < q[i].R) add(++R);
        while(R > q[i].R) del(R--);
        ans[q[i].id] = check();
    }
    for (int i = 0; i < m; ++i) {
        cout << ans[i] << endl;
    }
}

带修莫队

vector<int> pos(150000), a(150000), ans;

struct XX {
    int L, R, T, p;
} q[150000];

struct FIX {
    int x, v;  //位置，值
};

bool cmp(XX A, XX B) {
    if (pos[A.L] != pos[B.L])return pos[A.L] < pos[B.L];
    else if (pos[A.R] != pos[B.R]) {
        if (pos[A.L] & 1) return A.R > B.R;
        else return A.R < B.R;
    }
    else return A.T < B.T;
}

int A = 0;
vector<int> cnt(1000001);

inline void add(int x) {
    if (++cnt[x] == 1) ++A;
}

inline void del(int x) {
    if (--cnt[x] == 0) --A;
}

vector<FIX> r(133335); //下标为时间戳，什么时候修改了什么值

void solve() {
    //ans.reserve(150000); 预分配空间，防止push_back() 产生内存移动
    int n, m, T = 0;
    cin >> n >> m;
    int block = pow(n,  2.0 / 3.0);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        pos[i] = i / block;
    }

    for (int i = 0; i < m; ++i) {
        char op;
        cin >> op;
        if (op == 'Q') {
            cin >> q[i].L >> q[i].R;
            q[i].T = T;
            q[i].p = static_cast<int>(ans.size());
            ans.push_back(0);
        } else {
            ++T;
            cin >> r[T].x >> r[T].v;
        }
    }
    sort(q, q + m, cmp);
    int zl = 1, zr = 0;
    T = 0;
    for (int i = 0; i < m; ++i) {
        while (zl < q[i].L) del(a[zl++]);
        while (zr > q[i].R) del(a[zr--]);
        while (zl > q[i].L) add(a[--zl]);
        while (zr < q[i].R) add(a[++zr]);
        while (T < q[i].T) {
            ++T;
            if (zl <= r[T].x && r[T].x <= zr) {
                add(r[T].v);
                del(a[r[T].x]);
            }
            swap(a[r[T].x], r[T].v);
        }
        while (T > q[i].T) {
            if (zl <= r[T].x && r[T].x <= zr) {
                add(r[T].v);
                del(a[r[T].x]);
            }
            swap(a[r[T].x], r[T].v);
            --T;
        }
        ans[q[i].p] = A;
    }
    for (long long i: ans) cout << i << endl;
}

Trie

普通Trie

template <int MAXN, int ALPHA_SIZE, char BASE_CHAR>
struct Trie {
    int tr[MAXN][ALPHA_SIZE];
    int cnt[MAXN];
    int pass_cnt[MAXN]; //如不需要删除或者start_with可以不开该数组节省空间
    int node_cnt;

    void init() {
        memset(tr[0], 0, ALPHA_SIZE * sizeof(int));
        memset(cnt, 0, sizeof(cnt));
        memset(pass_cnt, 0, sizeof(pass_cnt));
        node_cnt = 1;
    }

    void insert(const string &s) {
        int p = 0;
        for (int i = 0; s[i]; ++i) {
            int c = s[i] - BASE_CHAR;
            if (!tr[p][c]) {
                memset(tr[node_cnt], 0, ALPHA_SIZE * sizeof(int));
                tr[p][c] = node_cnt++;
            }
            p = tr[p][c];
            pass_cnt[p]++;
        }
        cnt[p]++;
    }

    void erase(const string &s) {
        int p = 0;
        for (int i = 0; s[i]; ++i) {
            p = tr[p][s[i] - BASE_CHAR];
            if (!p) return;
            pass_cnt[p]--;
        }
        if (cnt[p] > 0) cnt[p]--;
    }

    int search(const string &s) {
        int p = 0;
        for (int i = 0; s[i]; ++i) {
            p = tr[p][s[i] - BASE_CHAR];
            if (!p) break;
        }
        return p ? cnt[p] : 0;
    }

    bool starts_with(const string &s) {
        int p = 0;
        for (int i = 0; s[i]; ++i) {
            p = tr[p][s[i] - BASE_CHAR];
            if (!p || pass_cnt[p] == 0) return false;
        }
        return true;
    }

};

/* 注意:内开需要把静态改为vector

初始化<节点容量, 字符数, 起始字符>

使用示例：

// 小写字母 trie（1e5 节点容量）
Trie<100000, 26, 'a'> lower_trie;

// 数字 trie（1e4 节点容量）
Trie<10000, 10, 0> num_trie;

// 01 trie （1e4节点容量）
Trie<10000, 2, 0> num_trie;

// 大写字母 trie（带自定义容量）
Trie<50000, 26, 'A'> upper_trie;

// 初始化
lower_trie.init(); //一定要记得
lower_trie.insert("algorithm");
lower_trie.search("algo");  // 返回 0
lower_trie.search("algorithm");  // 返回 1
lower_trie.starts_with("algo"); // 返回 true
*/

01 Trie 求最大异或值

template <int MAX_BIT = 31, typename T = int>  // 默认处理 31位int整数（符号位除外）

struct BTrie {
    static const int SIZE = MAX_BIT * 5e5 + 10;  // 根据问题规模调整
    int tr[SIZE][2];
    int cnt[SIZE];  // 经过该节点的数字数量
    int node_cnt;

    inline void init() {
        node_cnt = cnt[0] = tr[0][0] = tr[0][1] = 0;
    }

    // 插入数字（二进制从高位到低位存储）
    void insert(T num) {
        int p = 0;
        for (int i = MAX_BIT-1; i >= 0; --i) {
            int b = (num >> i) & 1;
            if (!tr[p][b]) {
                tr[p][b] = ++node_cnt;
                cnt[node_cnt] = tr[node_cnt][0] = tr[node_cnt][1] = 0;
            }
            p = tr[p][b];
            cnt[p]++;
        }
    }

    // 删除数字（需保证数字存在）
    void erase(T num) {
        int p = 0;
        for (int i = MAX_BIT-1; i >= 0; --i) {
            int b = (num >> i) & 1;
            p = tr[p][b];
            cnt[p]--;
        }
    }
    // 查询与 num 异或后的最大值
    T max_xor(T num) {
        if (!node_cnt) return 0;  // 空 Trie
        T res = 0;
        int p = 0;
        for (int i = MAX_BIT-1; i >= 0; --i) {
            int best = ((num >> i) & 1) ^ 1;  // 优先选相反的位

            if (tr[p][best] && cnt[tr[p][best]] > 0) {
                res |= ((T)1 << i);
                p = tr[p][best];
            } else {
                p = tr[p][best ^ 1];
            }
        }
        return res;
    }
};


/* 使用示例：
BTrie<31> trie;  // 处理 31 位非负整数
BTrie <32, unsigned int> trie;  // 处理 32位
*/

//可用于处理 (最大/最小 AND/OR/XOR) 区间最大XOR和(配合前缀XOR数组)

可持久化Trie

template <int MAX_BIT = 31, typename T = int>
struct PersistentBTrie {
    struct Node {
        int ch[2] = {0, 0};
        int cnt = 0;
    };
    std::vector<Node> nodes;
    std::vector<int> roots;  // 各版本根节点索引

    PersistentBTrie() {
        nodes.emplace_back();  // 初始化空节点（版本0）
        roots.push_back(0);    // 初始版本0
    }

    // 插入新数字并生成新版本，prev_version为基准版本号
    int insert(T num, int prev_version) {
        int new_root = nodes.size();
        nodes.push_back(nodes[roots[prev_version]]); // 克隆旧根节点
        nodes[new_root].cnt++; // 当前路径计数+1
        roots.push_back(new_root); // 记录新版本根节点

        int curr = new_root;
        for (int i = MAX_BIT-1; i >= 0; --i) {
            int b = (num >> i) & 1;
            int next = nodes[curr].ch[b];
            int new_node = nodes.size();
            nodes.push_back(nodes[next]); // 克隆子节点
            nodes[new_node].cnt++;        // 更新当前路径计数
            nodes[curr].ch[b] = new_node; // 链接新节点
            curr = new_node;
        }
        return roots.size() - 1; // 返回新版本号
    }

    // 查询区间 [l_ver, r_ver] 内与num异或的最大值
    T max_xor(int l_ver, int r_ver, T num) {
        int l_root = roots[l_ver], r_root = roots[r_ver];
        T res = 0;
        for (int i = MAX_BIT-1; i >= 0; --i) {
            int b = (num >> i) & 1;
            int target = b ^ 1; // 期望的bit

            int r_ch = nodes[r_root].ch[target];
            int l_ch = nodes[l_root].ch[target];
            int diff = nodes[r_ch].cnt - nodes[l_ch].cnt;

            if (diff > 0) { // 存在该路径
                res |= T(1) << i;
                r_root = r_ch;
                l_root = l_ch;
            } else { // 路径不存在，选择另一边
                r_root = nodes[r_root].ch[target ^ 1];
                l_root = nodes[l_root].ch[target ^ 1];
            }
        }
        return res;
    }
};

树状数组

普通树状数组(单点修改, 区间查询)

template<typename T>
struct Fenwick {
    vector<T> tree;
    int n;

    static inline int lowbit(int x) { return x & (-x); }

    explicit Fenwick(int size) : n(size), tree(size + 1, 0) {}

    void add(int x, T v) {
        while (x <= n) {
            tree[x] += v;
            x += lowbit(x);
        }
    }

    T query(int x) const {
        T res = 0;
        while (x) {
            res += tree[x];
            x -= lowbit(x);
        }
        return res;
    }

    // 查询区间和 [l, r]
    T query(int l, int r) { return query(r) - query(l - 1); }
    T operator[](int x) const { return query(x) - query(x - 1); }
};

普通树状数组区间修改

template<typename T>
struct FenwickRange {
    vector<T> tree1, tree2;  // 两个差分树
    int n;

    static inline int lowbit(int x) { return x & (-x); }

    explicit FenwickRange(int size) : n(size), tree1(size + 2, 0), tree2(size + 2, 0) {}

    void _add(vector<T>& tree, int x, T v) {    // 同时更新两个树
        while (x <= n) {
            tree[x] += v;
            x += lowbit(x);
        }
    }

    void add(int l, int r, T v) {   // 区间 [l, r] 增加 v
        _add(tree1, l, v);
        _add(tree1, r + 1, -v);
        _add(tree2, l, v * l);
        _add(tree2, r + 1, -v * (r + 1));
    }

    T query(int x) {    // 查询前缀和 [1, x]
        T res1 = 0, res2 = 0;
        int t = x;
        while (x > 0) {
            res1 += tree1[x];
            res2 += tree2[x];
            x -= lowbit(x);
        }
        return (t + 1) * res1 - res2;
    }

    // 查询区间和 [l, r]
    T query(int l, int r) { return query(r) - query(l - 1); }

    T operator[](int x) const { return query(x, x); }
};

二维树状数组

template<typename T>
struct Fenwick2D {
    vector<vector<T>> tree;
    int rows, cols;

    static int lowbit(int x) { return x & (-x); }

    explicit Fenwick2D(int r, int c) : rows(r), cols(c), tree(r + 1, vector<T>(c + 1, 0)) {}

    void add(int x, int y, T v) {  // 在位置 (x,y) 处增加值 v（1-based）
        for (int i = x; i <= rows; i += lowbit(i)) {
            for (int j = y; j <= cols; j += lowbit(j)) {
                tree[i][j] += v;
            }
        }
    }

    T query(int x, int y) const {   // 查询(1,1) 到 (x,y) 的矩形和
        T res = 0;
        for (int i = x; i > 0; i -= lowbit(i)) {
            for (int j = y; j > 0; j -= lowbit(j)) {
                res += tree[i][j];
            }
        }
        return res;
    }

    T query(int x1, int y1, int x2, int y2) const {    // 矩形区域 [x1,y1] 到 [x2,y2] 的和（闭区间）
        return query(x2, y2) - query(x1 - 1, y2) - query(x2, y1 - 1) + query(x1 - 1, y1 - 1);
    }
};

二维树状数组区间修改

template<typename T>
struct Fenwick2DRange {
    struct {
        vector<vector<T>> tree;
        int rows{}, cols{};

        void init(int r, int c) {
            rows = r;
            cols = c;
            tree.assign(r + 2, vector<T>(c + 2, 0));
        }

        void add(int x, int y, T v) {
            for (int i = x; i <= rows; i += lowbit(i))
                for (int j = y; j <= cols; j += lowbit(j))
                    tree[i][j] += v;
        }

        T query(int x, int y) {
            T res = 0;
            for (int i = x; i > 0; i -= lowbit(i))
                for (int j = y; j > 0; j -= lowbit(j))
                    res += tree[i][j];
            return res;
        }
    } D, Dx, Dy, Dxy;

    int rows, cols;

    static int lowbit(int x) { return x & (-x); }

    explicit Fenwick2DRange(int r, int c) : rows(r), cols(c) {
        D.init(r, c);
        Dx.init(r, c);
        Dy.init(r, c);
        Dxy.init(r, c);
    }

    void range_add(int x1, int y1, int x2, int y2, T v) {
        D.add(x1, y1, v);
        D.add(x1, y2+1, -v);
        D.add(x2+1, y1, -v);
        D.add(x2+1, y2+1, v);

        Dx.add(x1, y1, v * (x1-1));
        Dx.add(x1, y2+1, -v * (x1-1));
        Dx.add(x2+1, y1, -v * x2);
        Dx.add(x2+1, y2+1, v * x2);

        Dy.add(x1, y1, v * (y1-1));
        Dy.add(x1, y2+1, -v * y2);
        Dy.add(x2+1, y1, -v * (y1-1));
        Dy.add(x2+1, y2+1, v * y2);

        Dxy.add(x1, y1, v * (x1-1) * (y1-1));
        Dxy.add(x1, y2+1, -v * (x1-1) * y2);
        Dxy.add(x2+1, y1, -v * x2 * (y1-1));
        Dxy.add(x2+1, y2+1, v * x2 * y2);
    }

    T query(int x, int y) {
        return x * y * D.query(x, y)
            - y * Dx.query(x, y)
            - x * Dy.query(x, y)
            + Dxy.query(x, y);
    }

    T query(int x1, int y1, int x2, int y2) {
        return query(x2, y2)
            - query(x1-1, y2)
            - query(x2, y1-1)
            + query(x1-1, y1-1);
    }

    T get(int x, int y) { return query(x, y, x, y); }

    /*
    Fenwick2DRange<int> fr(100, 100);  // 创建 100x100 的二维区间树 (行, 列)

    // 在 [3,5] 到 [10,20] 的矩形区域加 5
    fr.range_add(3, 5, 10, 20, 5);

    // 查询 [1,1] 到 [50,50] 的和
    fr.query(1, 1, 50, 50);

    // 单点查询 (7,8)
    fr.get(7, 8);

    */
};

线段树

线段树区间加减乘

template<int MAX_N>
struct LazySegmentTree {
private:
    static constexpr int MAX_TREE_SIZE = 4 * MAX_N;
    ll tree[MAX_TREE_SIZE];
    struct LazyTag { ll mul, add; } lazy[MAX_TREE_SIZE];
    ll mod;
    int n;
    vector<ll> a;

    // 辅助函数：处理负数的取模
    inline ll mod_val(ll x) const {
        if (mod == 0) return x;
        return (x % mod + mod) % mod;
    }

    void push_down(int L, int M, int R, int p) {
        if ((lazy[p].mul != 1 || lazy[p].add != 0) && L != R) {
            int lc = p<<1, rc = p<<1|1;

            // 更新左子树
            tree[lc] = mod_val(tree[lc] * lazy[p].mul + lazy[p].add * (M-L+1));
            // 更新右子树
            tree[rc] = mod_val(tree[rc] * lazy[p].mul + lazy[p].add * (R-M));

            // 合并标记到左子树
            lazy[lc].add = mod_val(lazy[lc].add * lazy[p].mul + lazy[p].add);
            lazy[lc].mul = mod_val(lazy[lc].mul * lazy[p].mul);

            // 合并标记到右子树
            lazy[rc].add = mod_val(lazy[rc].add * lazy[p].mul + lazy[p].add);
            lazy[rc].mul = mod_val(lazy[rc].mul * lazy[p].mul);

            // 重置当前标记
            lazy[p].mul = 1;
            lazy[p].add = 0;
        }
    }

    void push_up(int p) {
        tree[p] = mod_val(tree[p<<1] + tree[p<<1|1]);
    }

    void build(int L, int R, int p) {
        lazy[p] = {1, 0};
        if (L == R) {
            tree[p] = mod_val(a[L]);
            return;
        }
        int M = (L+R) >> 1;
        build(L, M, p<<1);
        build(M+1, R, p<<1|1);
        push_up(p);
    }

    void _update_add(int L, int R, int p, int l, int r, ll v) {
        if (l <= L && R <= r) {
            tree[p] = mod_val(tree[p] + v * (R-L+1));
            lazy[p].add = mod_val(lazy[p].add + v);
            return;
        }
        int M = (L+R) >> 1;
        push_down(L, M, R, p);
        if (l <= M) _update_add(L, M, p<<1, l, r, v);
        if (r > M) _update_add(M+1, R, p<<1|1, l, r, v);
        push_up(p);
    }

    void _update_mul(int L, int R, int p, int l, int r, ll v) {
        if (l <= L && R <= r) {
            tree[p] = mod_val(tree[p] * v);
            lazy[p].add = mod_val(lazy[p].add * v);
            lazy[p].mul = mod_val(lazy[p].mul * v);
            return;
        }
        int M = (L+R) >> 1;
        push_down(L, M, R, p);
        if (l <= M) _update_mul(L, M, p<<1, l, r, v);
        if (r > M) _update_mul(M+1, R, p<<1|1, l, r, v);
        push_up(p);
    }

    ll _query(int L, int R, int p, int l, int r) {
        if (l <= L && R <= r) return tree[p];
        int M = (L+R) >> 1;
        push_down(L, M, R, p);
        ll res = 0;
        if (l <= M) res += _query(L, M, p<<1, l, r);
        if (r > M) res += _query(M+1, R, p<<1|1, l, r);
        return mod_val(res);
    }

public:
    // 初始化：传入原始数组（1-based）和模数（0表示不取模）
    LazySegmentTree(const vector<ll>& arr, ll m = 0) : mod(m), n(arr.size()-1), a(arr) {
        assert(arr.size() > 1 && "Array should be 1-based");
        build(1, n, 1);
    }

    // 区间加 [l, r] 闭区间
    void range_add(int l, int r, ll v) {
        _update_add(1, n, 1, l, r, v);
    }

    // 区间乘 [l, r] 闭区间
    void range_mul(int l, int r, ll v) {
        _update_mul(1, n, 1, l, r, v);
    }

    // 区间查询 [l, r] 闭区间
    ll range_query(int l, int r) {
        return _query(1, n, 1, l, r);
    }
};

// 使用示例：
// vector<ll> arr(n+1); // 1-based
// LazySegmentTree<100000> st(arr, mod);
// st.range_add(l, r, v);
// st.range_mul(l, r, v);
// ll sum = st.range_query(l, r);

主席树(可持久化线段树)

主席树求区间MEX(在线)

const int N = 2e5 + 10;
struct node {
    int l, r, v;
} tr[N * 30];
int cnt = 0, root[N];

inline void pushup(int x) {
    tr[x].v = min(tr[tr[x].l].v, tr[tr[x].r].v);
}

int update(int x, int v, int L, int R, int P) {
    if (L == R) {
        tr[++cnt].v = v;
        return cnt;
    }
    int nex = ++cnt, mid = (L + R) >> 1;
    tr[nex] = tr[P];
    if (x <= mid)  tr[nex].l = update(x, v, L, mid, tr[P].l);
    else tr[nex].r = update(x, v, mid + 1, R, tr[P].r);
    pushup(nex);
    return nex;
}

int query(int l, int L, int R, int P) {
    if (L == R) return L;
    int mid = (L + R) >> 1;
    if (tr[tr[P].l].v < l) return query(l, L, mid, tr[P].l);
    return query(l, mid + 1, R, tr[P].r);
}


void solve() {
    int n, q, tmp;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> tmp;
        root[i] = update(tmp + 1, i, 1, 2e5+1, root[i - 1]);
    }

    while(q--) {
        int l, r;
        cin >> l >> r;
        cout << query(l, 1, 2e5+1, root[r]) - query(l, 1, 2e5+1, root[l - 1]) << endl;
    }

}

链式前向星

const int MAXN = 5e5 + 5;  // 最大节点数
const int MAXM = 1e6 + 5;  // 最大边数（无向图*2）
struct Edge {
    int to, nex;
} e[MAXM];
int head[MAXN], cnt_edge;

inline void clear_edge(int n) {
    for (int i = 0; i <= n; ++i) head[i] = -1;
    cnt_edge = 0;

}

inline void add_edge(int u, int v) {
    e[++cnt_edge].to = v;
    e[cnt_edge].nex = head[u];
    head[u] = cnt_edge;
}

倍增LCA

constexpr int MAXN = 5e5 + 10;
constexpr int MAX_LOG = 20; // 需满足2^MAX_LOG > 最大深度



struct {
    int to, nex;
} e[MAXN << 1];

int head[MAXN << 1], cnt = 0;

inline void add(int x, int y) {
    e[++cnt].to = y;
    e[cnt].nex = head[x];
    head[x] = cnt;
}

void init(int n) {
    for (int i = 0; i <= n; ++i) head[i] = e[i].nex = -1;
    cnt = 0;
}

int depth[MAXN]; // 节点深度
int fa[MAXN][MAX_LOG]; // 倍增父亲数组

void dfs_lca(int u, int father) {
    depth[u] = depth[father] + 1;
    fa[u][0] = father;
    for (int i = 1; i < MAX_LOG; ++i)
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for (int i = head[u]; i != -1; i = e[i].nex) {
        int v = e[i].to;
        if (v != father) dfs_lca(v, u);
    }
}

/*
//非递归预处理
void dfs_lca(int root, int father) {
    stack<pair<int, int>> s;
    s.push({root, father});
    while (!s.empty()) {
        auto [u, f] = s.top();
        s.pop();
        depth[u] = depth[f] + 1;
        fa[u][0] = f;
        for (int i = 1; i < MAX_LOG; ++i)
            fa[u][i] = fa[fa[u][i-1]][i-1];
        for (int i = head[u]; i != -1; i = e[i].nex) {
            int v = e[i].to;
            if (v != f)
                s.push({v, u}); // 子节点入栈
        }
    }
}
*/

inline void init_lca(int root) { // 初始化LCA
    depth[0] = -1;
    dfs_lca(root, 0);
}

int get_lca(int x, int y) {
    if (depth[x] < depth[y]) swap(x, y);
    // 先跳到同一层
    for (int i = MAX_LOG - 1; i >= 0; --i)
        if (depth[x] - (1 << i) >= depth[y])
            x = fa[x][i];
    if (x == y) return x;
    // 同时往上跳
    for (int i = MAX_LOG - 1; i >= 0; --i)
        if (fa[x][i] != fa[y][i])
            x = fa[x][i], y = fa[y][i];
    return fa[x][0];
}

int get_dist(int x, int y) {
    int lca = get_lca(x, y);
    return depth[x] + depth[y] - 2 * depth[lca];
}

树链剖分

struct Edge {
    int to, nex;
} edge[200010];

int cnt = 0, head[200010], n;

void init() {
    for (int i = 0; i < 200010; ++i) {
        edge[i].to = edge[i].nex = head[i] = -1;
    }
}

void add(int x, int y) {
    edge[++cnt].to = y;
    edge[cnt].nex = head[x];
    head[x] = cnt;
}

int tree[400020], lazy[400020];

inline void pu(int p) {
    tree[p] = tree[p << 1] + tree[p << 1 | 1];
}

inline void pd(int L, int M, int R, int p) {
    if (lazy[p] && L != R) {
        if (lazy[p] == INT_MIN) {
            tree[p << 1] = tree[p << 1 | 1] = 0;
            lazy[p << 1] = lazy[p << 1 | 1] = INT_MIN;
            lazy[p] = 0;
            return;
        }
        tree[p << 1] = lazy[p] * (1 + M - L),
                tree[p << 1 | 1] = lazy[p] * (R - M);
        lazy[p << 1] = lazy[p], lazy[p << 1 | 1] = lazy[p];
        lazy[p] = 0;
    }
}

void update(int L, int R, int p, int l, int r) {
    if (l <= L && R <= r) {
        tree[p] = R - L + 1;
        lazy[p] = 1;
        return;
    }
    int M = L + ((R - L) >> 1);
    pd(L, M, R, p);
    if (l <= M) update(L, M, p << 1, l, r);
    if (r > M) update(M + 1, R, p << 1 | 1, l, r);
    pu(p);
}

void resett(int L, int R, int p, int l, int r) {
    if (l <= L && R <= r) {
        tree[p] = 0;
        lazy[p] = INT_MIN;
        return;
    }
    int M = L + ((R - L) >> 1);
    pd(L, M, R, p);
    if (l <= M) resett(L, M, p << 1, l, r);
    if (r > M) resett(M + 1, R, p << 1 | 1, l, r);
    pu(p);
}

int query(int L, int R, int p, int l, int r) {
    int M = L + ((R - L) >> 1), sum = 0;
    pd(L, M, R, p);
    if (L >= l && R <= r) {
        return tree[p];
    }

    if (l <= M) sum = query(L, M, p << 1, l, r);
    if (r > M) sum += query(M + 1, R, p << 1 | 1, l, r);
    return sum;
}

int son[100005], id[100005], fa[100005], deep[100005], siz[100005], top[100005];

void dfs1(int x, int father) {
    deep[x] = deep[father] + 1;
    fa[x] = father;
    siz[x] = 1;
    for (int i = head[x]; ~i; i = edge[i].nex) {
        int s = edge[i].to;
        if (s != father) {
            fa[s] = x;
            dfs1(s, x);
            siz[x] += siz[s];
            if (!son[x] || siz[son[x]] < siz[s]) son[x] = s;
        }
    }
}

int num = 0;

void dfs2(int x, int topx) {
    id[x] = ++num;
    top[x] = topx;
    if (!son[x]) return;
    dfs2(son[x], topx);
    for (int i = head[x]; ~i; i = edge[i].nex) {
        int y = edge[i].to;
        if (y != fa[x] && y != son[x]) dfs2(y, y);
    }
}

int query_range(int x, int y) { //查询树上路径 x 到 y 的和
    int ans = 0;
    while (top[x] != top[y]) {
        if (deep[top[x]] < deep[top[y]]) swap(x, y);
        ans += query(1, n, 1, id[top[x]], id[x]);
        x = fa[top[x]];
    }
    if (deep[x] > deep[y]) swap(x, y);
    ans += query(1, n, 1, id[x], id[y]);
    return ans;
}

void update_range(int x, int y) {  //将路径 x 到 y 的所有节点设为 1。
    while (top[x] != top[y]) {
        if (deep[top[x]] < deep[top[y]]) swap(x, y);
        update(1, n, 1, id[top[x]], id[x]);
        x = fa[top[x]];
    }
    if (deep[x] > deep[y]) swap(x, y);
    update(1, n, 1, id[x], id[y]);
}

void update_tree(int x) { //将子树 x 的所有节点设为 1。
    update(1, n, 1, id[x], id[x] + siz[x] - 1);
}

void reset_tree(int x) { //将子树 x 的所有节点设为 0。
    resett(1, n, 1, id[x], id[x] + siz[x] - 1);
}

int query_tree(int x) { //查询子树的和
    return query(1, n, 1, id[x], id[x] + siz[x] - 1);
}

并查集

int find(inx x) {
    return a[x] == x ? x : find(a[x]);
}

带权并查集

int find(int x) {
    if (a[x] != x) {
        int root = find(a[x]);
        w[x] += w[a[x]];
        a[x] = root;
    }
    return a[x];
}

void unite(int x, int y, int d) {
    int fx = find(x), fy = find(y);
    if (fx != fy) {
        a[fx] = fy;
        w[fx] = (d + w[y] - w[x];
    }
}
//x合并至y

字符串

KMP

void getNext(vector<int> &next, string s) {
    int m = s.size();
    next.clear();
    next.resize(m);
    for (int i = 1, j = 0; i < m; i++) {
        while (j > 0 && s[i] != s[j]) j = next[j - 1];
        if (s[i] == s[j]) j++;
        next[i] = j;
    }
}
//返回匹配的位置

vector<int> kmp(string &a, string &b) {
    vector<int> next, res;
    getNext(next, b);
    for (int i = 0, j = 0; i < a.size();) {
        if (j < b.size() && a[i] == b[j]) ++i, ++j;
        else while (a[i] != b[j]) {
                if (j == 0) {
                    ++i;
                    break;
                }
                j = next[j - 1];
            }
        if (j == b.size()) res.push_back(i - b.size() + 1);
    }
    //for (int i: res) cout << i << endl;
    //for (int i: next) cout << i << ' ';
    return res;
}

HASH

常用模数 $13331$，$131$

hash二分求回文子串数量

#define hash_t unsigned __int128
#define hash_tt unsigned long long


hash_t pre[100005], suf[100005], p[100005], base = 13333333111;
hash_tt  pre1[100005], suf1[100005], p1[100005], base1 = 13331;
int a[100005], v[100005];

void init(int n) {
    p[0] = p1[0] = 1;
    for (int i = 1; i <= n; i++) {
        pre[i] = pre[i-1] * base + a[i];
        pre1[i] = pre1[i-1] * base1 + a[i];
        p[i] = p[i-1] * base;
        p1[i] = p1[i-1] * base1;
    }

    for (int i = n; i >= 1; i--) {
        suf[i] = suf[i+1] * base + a[i];
        suf1[i] = suf1[i+1] * base1 + a[i];
    }
}

inline bool check(int l, int r) {
    if (suf[l] - suf[r+1] * p[r-l+1] == pre[r] - pre[l-1] * p[r-l+1] &&
    suf1[l] - suf1[r+1] * p1[r-l+1] == pre1[r] - pre1[l-1] * p1[r-l+1])
        return true;
    return false;
}

int count_huiwen(int n) {
    int count = 0;

    for (int i = 1; i <= n; ++i) {
        int l = 0, r = min(i - 1, n - i), ans = -1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (check(i - mid, i + mid)) ans = mid, l = mid + 1;
            else r = mid - 1;
        }
        count += ans + 1;
    }

    for (int i = 1; i <= n - 1; ++i) {
        int l = 1, r = min(i, n - i), ans = 0;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (i - mid + 1 < 1 || i + mid > n || i - mid + 1 > i + mid) {
                r = mid - 1;
                continue;
            }
            if (check(i - mid + 1, i + mid)) ans = mid, l = mid + 1;
            else r = mid - 1;
        }
        count += ans;
    }

    return count;
}

HASH求双回文子串长度(可求对应位置的前后回文长度)（代替马拉车）

参考题目，洛谷P4555，求字符串中双回文子串的最大长度。

#include <bits/stdc++.h>

#define PII pair<int,int>
#define LL long long
#define LD long double
#define ULL unsigned int
#define endl '\n'
using namespace std;

ULL base = 131;
vector<ULL> h1(100005), h2(100005), p(100005);
int mx_pre[100005], mx_suf[100005];

inline ULL pre_hash(int l, int r) {
    return h1[r] - h1[l - 1] * p[r - l + 1];
}

inline ULL suf_hash(int l, int r) {
    return h2[l] - h2[r+1] * p[r - l + 1];
}

void solve() {
    string str;
    int mx = 0;
    cin >> str;
    p[0] = mx_pre[1] = mx_suf[str.size()] = 1;;
    for (int i = 1; i < 100005; ++i) p[i] = p[i-1] * base;
    for (int i = 0; i < str.size(); ++i) h1[i+1] = h1[i] * base + static_cast<ULL>(str[i] - 'a' + 1);
    for (int i = str.size() - 1; i >= 0; --i) h2[i + 1] = h2[i + 2] * base + static_cast<ULL>(str[i] - 'a' + 1);

    for (int i = 2; i <= str.size(); ++i) {
        int tmp = min(i, mx_pre[i - 1] + 2);
        while(pre_hash(i - tmp + 1,i) != suf_hash(i - tmp + 1, i)) --tmp;
        mx_pre[i] = tmp;
    }

    for (int i = str.size() - 1; i ; --i) {
        int tmp = min((int)str.size() - i + 1, mx_suf[i + 1] + 2);
        while(pre_hash(i,i + tmp - 1) != suf_hash(i, i + tmp - 1)) --tmp;
        mx_suf[i] = tmp;
        mx = max(mx, mx_suf[i + 1] + mx_pre[i]);
    }
    cout << mx << endl;
}

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

矩阵哈希

参考洛谷P10474

#include <bits/stdc++.h>

#define LL long long
#define int long long
#define ULL unsigned long long
#define PII pair<LL,LL>
#define PCL pair<char,LL>
#define endl '\n'
using namespace std;

ULL base = 131, base2 = 113, h[1002][1002], p1[1005], p2[1005];

void init() {

}

set<ULL> st;

void solve() {
    int n, m, a, b;
    char ch;
    cin >> n >> m >> a >> b;
    p1[0] = p2[0] = 1;
    for (int i = 1; i < 1005; ++i) {
        p1[i] = p1[i - 1] * base;
        p2[i] = p2[i - 1] * base2;
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> ch;
            h[i][j] = h[i][j - 1] * base + (ULL) (ch - '0' + 1);
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; ++j) {
            h[i][j] = h[i - 1][j] * base2 + h[i][j];
        }
    }

    for (int i = a; i <= n; i++) {
        for (int j = a; j <= m; ++j) {
            st.insert(h[i][j] - h[i - a][j] * p2[a] - h[i][j - b] * p1[b] + h[i - a][j - b] * p1[b] * p2[a]);
        }
    }

    cin >> n;
    while (n--) {
        for (int i = 1; i <= a; ++i) {
            for (int j = 1; j <= b; ++j) {
                cin >> ch;
                h[i][j] = h[i][j - 1] * base + (ULL) (ch - '0' + 1);
            }
        }

        for (int i = 1; i <= a; i++) h[i][b] = h[i - 1][b] * base2 + h[i][b];

        cout << st.count(h[a][b]) << endl;
    }
}

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

Update date: 2025-05-14
Author: GuWolf
未解决问题: 暂无