GuWolf的ICPC算法模板

模板只有DS和一点点数学，因为DP和数学感觉没必要写在模板里(其实主要是懒OωO)
点击查看/下载: [GuWolf的模板.pdf][1]

PS: SAM(后缀自动机)是AI写的,要比赛了来不及~

# 杂项
## 快读
### 普通快读
```cpp
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 - '0', ch = getchar();
    return x * f;
}
```

### 优化快读
```cpp
char *p1, *p2, buf[100000];
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
int read() {
    int x = 0, f = 1;
    char ch = nc();
    while (ch < 48 || ch > 57) {
        if (ch == '-') f = -1;
        ch = nc();
    }
    while (ch >= 48 && ch <= 57) x = x * 10 + ch - 48, ch = nc();
    return x * f;
}
```

## 快写
```cpp
void write(int x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
```

## 超级快读写(待测试)

```cpp
namespace __Coel_FastIO {
	const int SIZE = 1 << 20;
	static char buf_r[SIZE], *p1 = buf_r, *p2 = buf_r;
	static char buf_w[SIZE], *p3 = buf_w, *p4 = buf_w + SIZE;
	static std::streambuf *inbuf = std::cin.rdbuf(), *outbuf = std::cout.rdbuf(); //流初始化
	inline static void gc(char &ch) { //这里三目运算符的效率略高一些
		ch = p1 == p2 && (p2 = (p1 = buf_r) + inbuf->sgetn(buf_r, SIZE), p1 == p2) ? EOF : *p1++;
		/*逻辑：先判断有没有读完一个缓存，如果缓存空了就继续往下读，
		否则用 sgetn 读入一个缓存，如果还是空的就返回 EOF*/
	}
	inline static void pc(char c) {
		p3 == p4 ? outbuf->sputn(p3 = buf_w, SIZE), *p3++ = c : *p3++ = c;
		/*逻辑差不多，如果写完整个缓存就全部输出，否则写入缓存*/
	}

inline static int Flush() { return outbuf->sputn(buf_w, p3 - buf_w), 0; } //清空数组

struct IOdesu {
		template<typename T> IOdesu& operator >>(T &x) {
			x = 0;
			int f = 1;
			char ch;
			gc(ch);
			while (ch < '0' || ch > '9') {
				if (ch == '-') f = -1;
				gc(ch);
			}
			while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', gc(ch);
			return x *= f, *this;
		}

template<typename T> IOdesu& operator <<(T x)  {
			if (x < 0) x = -x, pc('-');
			static int buf[35];
			int top = 0;
			do {
				buf[top++] = x % 10;
				x /= 10;
			} while (x);
			while (top) pc(buf[--top] + '0');
			return *this;
		}
		IOdesu& operator <<(char ch) { return pc(ch), *this; }
	} qwq;
}

/*
使用教程
qwq >> x;

qwq << x;
*/
```

## 卡时

有一个 clock() 函数，返回程序运行时间。
```cpp
while ((double)clock()/CLOCKS_PER_SEC < MAX_TIME) action();
```
这样子就会一直跑action，直到用时即将超过时间限制

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

## O1快速乘

### long double实现 (弃用，在支持__int128的场景应使用int128)
```
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;
}
```

## 随机数生成器

```cpp
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)

```cpp
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`
```cpp
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; }
};
```

# 数学

## 分数运算

```cpp
struct Frac {
    LL num, den;

constexpr Frac(LL n = 0, LL d = 1) : num(n), den(d) { norm(); }
    constexpr explicit Frac(LL n) : num(n), den(1) {}
    constexpr explicit Frac() : num(0), den(1) {}
    
    void norm() {
        if (num == 0) return;
        if (den < 0) num = -num, den = -den;
        LL g = std::gcd(num, den);
        if (g) num /= g, den /= g;
    }

Frac &operator+=(const Frac &rhs) {
        num = num * rhs.den + rhs.num * den;
        den *= rhs.den;
        norm();
        return *this;
    }

Frac &operator-=(const Frac &rhs) {
        num = num * rhs.den - rhs.num * den;
        den *= rhs.den;
        norm();
        return *this;
    }

Frac &operator*=(const Frac &rhs) {
        num *= rhs.num;
        den *= rhs.den;
        norm();
        return *this;
    }

Frac &operator/=(const Frac &rhs) {
        num *= rhs.den;
        den *= rhs.num;
        norm();
        return *this;
    }

friend Frac operator+(Frac lhs, const Frac &rhs) { return lhs += rhs; }
    friend Frac operator-(Frac lhs, const Frac &rhs) { return lhs -= rhs; }
    friend Frac operator*(Frac lhs, const Frac &rhs) { return lhs *= rhs; }
    friend Frac operator/(Frac lhs, const Frac &rhs) { return lhs /= rhs; }

Frac operator-() const { return Frac(-num, den); }

friend bool operator<(const Frac &a, const Frac &b) { return (__int128) a.num * b.den < (__int128) b.num * a.den; }
    friend bool operator>(const Frac &a, const Frac &b) { return b < a; }
    friend bool operator<=(const Frac &a, const Frac &b) { return !(b < a); }
    friend bool operator>=(const Frac &a, const Frac &b) { return !(a < b); }
    friend bool operator==(const Frac &a, const Frac &b) { return a.num == b.num && a.den == b.den; }
    friend bool operator!=(const Frac &a, const Frac &b) { return !(a == b); }
};
```

## 线筛(附一种快速分解质因数的思路)

以下代码和普通线筛的区别就是把用于标记是否为合数的bool数组改为存储当前数的最小质因数，每次我们只需要对当前数字的最小质因数的数字进行整除到不能再整除，继续用得到的新数字除到mnz为0，所得的数即为最后一个质因数(最大质因数)
```cpp
struct prime {
    vector<int> zs, mnz;
    prime(int x) {
        mnz.resize(x + 1);
        zs.reserve(static_cast<int>(x / log(x)) + (x / 100) + 100);
        for (int i = 2; i <= x; ++i) {
            if (!mnz[i]) zs.push_back(i), mnz[i] = i;
            for (int j : zs) {
                if (i * j > x) break;
                mnz[i * j] = j;
                if (j == mnz[i]) break;
            }
        }
    }
};
```

快速分解质因数代码

```cpp
vector<PII> factorize(int n, const Prime& S) {
    vector<PII> res;
    while (n > 1) {
        int p = S.mnz[n], cnt = 0;
        do { n /= p; ++cnt; } while (n % p == 0);
        res.emplace_back(p, cnt);
    }
    return res;
}
```

# 数据结构

## 单调队列
```cpp
deque<int> q;
for (int i = 1; i <= n; i++) {
    while (!q.empty() && a[q.back()] >= a[i]) q.pop_back();
    q.push_back(i);
    if (i - q.front() >= k) q.pop_front();
    if (i >= k) cout << a[q.front()] << " ";
}
```

## 单调栈维护当前大于等于某个值的最靠近当前位置的下标

```cpp
for (int i = 0; i < n; ++i) {
    if (A[i] == B[i]) ans += (i + 1ll) * (n - i);
    else {
        auto it = st.rend();
        if (!st.empty()) it = lower_bound(st.rbegin(), st.rend(), PII{max(A[i], B[i]), 0});
        ans += it != st.rend() ? (it->second + 1ll) * (n - i) : 0ll;
    }

while (!st.empty() && st.back().first <= A[i]) st.pop_back();
    st.emplace_back(A[i], i);
}
```

## 动态求中位数 (红黑树顶红黑树)

```cpp
struct Med {
    multiset<int, greater<>> L; // 左半（含中位数）
    multiset<int> R;               // 右半
    long long sL = 0, sR = 0;      // 和

void clear() { L.clear(); R.clear(); sL = sR = 0; }
    int med() const { return *L.begin(); }    //Lmed
    int cntL() const { return (int)L.size() - 1; }
    int cntR() const { return (int)R.size(); }
    long long sumL() const { return sL - *L.begin(); }
    long long sumR() const { return sR; }

void bal() {
        if (L.size() < R.size()) {
            auto it = R.begin(); int x = *it; R.erase(it); sR -= x;
            L.insert(x); sL += x;
        } else if (L.size() > R.size() + 1) {
            auto it = L.begin(); int x = *it; L.erase(it); sL -= x;
            R.insert(x); sR += x;
        }
    }
    void add(int x) {
        if (L.empty() || x <= *L.begin()) L.insert(x), sL += x;
        else R.insert(x), sR += x;
        bal();
    }
    void del(int x) {
        auto it = L.find(x);
        if (it != L.end()) { L.erase(it); sL -= x; }
        else { it = R.find(x); if (it != R.end()) { R.erase(it); sR -= x; } }
        bal();
    }
};
```

## 莫队

### 基础莫队(极限数据量 $5 \times 10^5$/s)
```cpp
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(离线)
```cpp
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;
    }
}
```

### 带修莫队
```cpp
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

```cpp
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; i < s.size(); ++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; i < s.size(); ++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; i < s.size(); ++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; i < s.size(); ++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 求最大异或值

```cpp
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

```cpp
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;
    }
};

```

## 树状数组

### 普通树状数组(单点修改, 区间查询)
```cpp
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); }
};
```
### 普通树状数组区间修改
```cpp
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); }
};
```

### 二维树状数组
```cpp
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);
    }
};
```

### 二维树状数组区间修改
```cpp

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);

*/
};

```

## 线段树

### 线段树区间加减乘
```cpp
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);
```

### 动态开点
```cpp
constexpr int N = 2e5 + 10;

struct node {
    int l, r, lazy, v;
} tr[N * 30];

int cnt = 0;

inline int new_node() {
    tr[++cnt] = {};
    return cnt;
}

inline void pushup(int p) { tr[p].v = (tr[p].l ? tr[tr[p].l].v : 0) + (tr[p].r ? tr[tr[p].r].v : 0); }

void pushdown(int l, int m, int r, int p) {
    if (l != r && tr[p].lazy) {
        if (!tr[p].l) tr[p].l = new_node();
        if (!tr[p].r) tr[p].r = new_node();
        tr[tr[p].l].lazy += tr[p].lazy, tr[tr[p].l].v += tr[p].lazy * (m - l + 1);
        tr[tr[p].r].lazy += tr[p].lazy, tr[tr[p].r].v += tr[p].lazy * (r - m);
        tr[p].lazy = 0;
    }
}

void update(int l, int r, int p, int ql, int qr, int v) {
    if (ql <= l && r <= qr) {
        tr[p].lazy += v;
        tr[p].v += v * (r - l + 1);
        return;
    }

int m = (l + r) >> 1;
    pushdown(l, m, r, p);
    if (ql <= m) {
        if (!tr[p].l) tr[p].l = new_node();
        update(l, m, tr[p].l, ql, qr, v);
    }

if (qr > m) {
        if (!tr[p].r) tr[p].r = new_node();
        update(m + 1, r, tr[p].r, ql, qr, v);
    }
    pushup(p);
}

int query(int l, int r, int p, int ql, int qr) {
    if (ql <= l && r <= qr) return tr[p].v;
    int m = (l + r) >> 1, sum = 0;
    pushdown(l, m, r, p);
    if (ql <= m && tr[p].l) sum = query(l, m, tr[p].l, ql, qr);
    if (qr > m && tr[p].r) sum += query(m + 1, r, tr[p].r, ql, qr);
    return sum;
}
```

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

#### 主席树求区间MEX(在线)
```cpp
constexpr 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 ql, int l, int r, int p) {
    if (l == r) return l;
    int mid = (l + r) >> 1;
    if (tr[tr[p].l].v < ql) return query(ql, l, mid, tr[p].l);
    return query(ql, 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]) - 1 << endl;
    }
}
```

## 链式前向星

```cpp
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

```cpp
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];
}

int lca_with_root(int u, int v, int r) {
    int a = get_lca(u, v), b = get_lca(u, r), c = get_lca(v, r);
    if (a == b) return c;
    if (a == c) return b;
    return a;
}

```

## ST表

```cpp
template<typename T, T (*op)(T, T)>
struct ST {
    vector<vector<T> > st;
    vector<int> log_table;
    int n{};

void init(const vector<T> &v) {
        n = v.size();
        log_table.resize(n + 1);
        log_table[1] = 0;
        for (int i = 2; i <= n; i++) log_table[i] = log_table[i >> 1] + 1;

int k = log_table[n] + 1;
        st.assign(n, vector<T>(k));

for (int i = 0; i < n; i++)
            st[i][0] = v[i];

for (int j = 1; j < k; j++) {
            for (int i = 0; i + (1 << j) <= n; i++) {
                st[i][j] = op(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
            }
        }
    }

T query(int l, int r) {
        int j = log_table[r - l + 1];
        return op(st[l][j], st[r - (1 << j) + 1][j]);
    }
};

int max(int a, int b) { return a > b ? a : b; }

/*
用法
ST<LL, max> st;
ST<int, __gcd> st;
*/
```

## 树链剖分

```cpp
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);
}

```

## 并查集

### 新版本-单数组+路径折半 (常数小)
```cpp
// 1-base
struct DSU {
    vector<int> p;
    int cnt;

DSU(int n = 0) { init(n); }

void init(int n) {
        p.assign(n + 1, -1);
        cnt = n;
    }

int find(int x) {
        while (p[x] >= 0) {
            int px = p[x];
            if (p[px] >= 0) p[x] = p[px];
            x = px;
        }
        return x;
    }

bool unite(int a, int b) {
        a = find(a), b = find(b);
        if (a == b) return false;
        if (p[a] > p[b]) swap(a, b);
        p[a] += p[b];
        p[b] = a;
        --cnt;
        return true;
    }

int siz(int x) { return -p[find(x)]; }
    int comps() const { return cnt; }
};
```

### 老版本-完全路径压缩版
```cpp
struct DSU {
    vector<int> p, sz;
    DSU(int n = 0) { init(n); }
 
    void init(int n) {
        p.resize(n + 1);
        iota(p.begin(), p.end(), 0);
        sz.assign(n + 1, 1);
    }
 
    int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
 
    bool unite(int a,int b) {
        a = find(a), b = find(b);
        if (a == b) return false;
        if (sz[a] < sz[b]) swap(a, b);
        p[b] = a, sz[a] += sz[b];
        return true;
    }
};
```

## 带权并查集

```cpp
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

```cpp
void getNext(const string &p, vector<int> &lps) {
    int m = p.size();
    lps.assign(m, 0);
    for (int i = 1, j = 0; i < m; ++i) {
        while (j > 0 && p[i] != p[j]) j = lps[j - 1];
        if (p[i] == p[j]) ++j;
        lps[i] = j;
    }
}

vector<int> kmp(const string &s, const string &p) {
    vector<int> res;
    int n = s.size(), m = p.size();
    if (m == 0) return res; // 视题意处理空模式
    vector<int> lps;
    getNext(p, lps);
    for (int i = 0, j = 0; i < n; ++i) {
        while (j > 0 && s[i] != p[j]) j = lps[j - 1];
        if (s[i] == p[j]) ++j;
        if (j == m) {
            res.push_back(i - m + 1); // 0-based 起始位置；若要 1-based 用 i - m + 2
            j = lps[j - 1];
        }
    }
    return res;
}
```

## Z函数（拓展KMP）

```cpp
vector<int> Z(string s) {
    int n = s.size();
    std::vector<int> z(n + 1);
    z[0] = n;
    for (int i = 1, j = 1; i < n; i++) {
        z[i] = max(0, min(j + z[j] - i, z[i - j]));
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
        if (i + z[i] > j + z[j]) j = i;
    }
    return z;
}
```

## AC自动机

### 以求模式串出现次数为示例的AC自动机模板

```cpp
constexpr int N = 1000005;
constexpr LL mod = 998'244'353;

int cnt[N], endpos[N];

struct AC {

int zz = 0;
    queue<int> q;
    struct node {
        int ch[26], fail, ans;
    } trie[N];

int insert(const string& s) {
        int u = 0;
        for (char c : s) {
            int v = c - 'a';
            if (!trie[u].ch[v]) trie[u].ch[v] = ++zz;
            u = trie[u].ch[v];
        }
        return u;
    }

void build() {
        for (int c = 0; c < 26; ++c) {
            int v = trie[0].ch[c];
            if (v) q.push(v);
        }
        while (!q.empty()) {
            int u = q.front();q.pop();
            for (int i = 0; i < 26; ++i) {
                int v = trie[u].ch[i], fail = trie[u].fail;
                if (!v) trie[u].ch[i] = trie[fail].ch[i];
                else {
                    trie[v].fail = trie[fail].ch[i];
                    ++cnt[trie[v].fail];
                    q.push(v);
                }
            }
        }

//----- 建fail树 ----
        // for (int v = 1; v <= zz; ++v) {
        //     int f = trie[v].fail;
        //     tree[f].push_back(v);
        // }
        
    }

void query(const string& s) {
        int u = 0;
        for (char i : s) {
            int v = i - 'a';
            u = trie[u].ch[v];
            ++trie[u].ans;
        }
    }

void get_ans() {
        for (int i = 0; i <= zz; ++i)
            if (!cnt[i]) q.push(i);
        while (!q.empty()) {
            int u = q.front();q.pop();
            trie[trie[u].fail].ans += trie[u].ans;
            if (--cnt[trie[u].fail] == 0) q.push(trie[u].fail);
        }
    }

} ac;

string str[N];
void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> str[i];
        endpos[i] = ac.insert(str[i]);
    }
    ac.build();
    cin >> str[0];
    ac.query(str[0]);
    ac.get_ans();
    for (int i = 1; i <= n; ++i) cout << ac.trie[endpos[i]].ans << endl;

}
```

## HASH

常用模数 **$13331$**，**$131$**
### hash二分求回文子串数量

```cpp
#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，求字符串中双回文子串的最大长度。
```cpp
#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

```cpp
#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;
}
```

## SAM
```cpp
struct SAM {
    /* ========= 常量定义 ========= */
    static constexpr int MAXN = 100'000;   // 原串最大长度
    static constexpr int SIGMA = 26;         // 字符集大小

struct Node {
        //int ch[SIGMA]{};  // 初始化为 0
        map<int, int> ch;
        int fa = 0;
        int len = 0;
        int sz  = 0;
    };

/* ========= 成员 ========= */
    Node  st[MAXN * 2 + 5];
    long long dp[MAXN * 2 + 5];         // 用于 get_rank
    int  bucket[MAXN + 5];              // 基数排序桶
    int  topo[MAXN * 2 + 5];            // 拓扑序
    int  last = 1, tot = 1;             // root = 1
    int  n = 0;                         // 原串长度
    long long distinct_substr = 0;

/* ========= 基础操作 ========= */
    void clear() {                      // 多 case 使用
        last = tot = 1;
        st[1] = Node();                 // 重新置 0
    }

void extend(int c) {                // 插入字符编号 c
        int p = last;
        int np = last = ++tot;
        st[np].sz = 1;
        st[np].len = st[p].len + 1;

while (p && !st[p].ch.count(c)) {
            st[p].ch[c] = np;
            p = st[p].fa;
        }

if (!p) {
            st[np].fa = 1;
        } else {
            int q = st[p].ch[c];
            if (st[q].len == st[p].len + 1) {
                st[np].fa = q;
            } else {                                    // case 3 (clone)
                int nq = ++tot;
                st[nq] = st[q];        // 拷贝所有信息
                st[nq].len = st[p].len + 1;
                st[nq].sz  = 0;        // clone 节点不对应 endpos
                st[q].fa = st[np].fa = nq;
                while (p && st[p].ch[c] == q) {
                    st[p].ch[c] = nq;
                    p = st[p].fa;
                }
            }
        }
        distinct_substr += st[np].len - st[st[np].fa].len;
    }

/* ========= 输入 / 预处理 ========= */
    void build_from_string(const string& s) {
        clear();
        n = (int)s.size();
        for (char ch: s) extend(ch - 'a');

radix_sort();   // 获得 topo 序
        calc_sz();      // 统计 sz
        //calc_distinct_substr();
    }

/* ========= 基数排序 (按 len) ========= */
    void radix_sort() {
        fill(bucket, bucket + n + 1, 0);
        for (int i = 1; i <= tot; ++i) ++bucket[st[i].len];
        for (int i = 1; i <= n;   ++i) bucket[i] += bucket[i - 1];
        for (int i = tot; i >= 1; --i) topo[bucket[st[i].len]--] = i;
    }

/* ========= 求 sz ========= */
    void calc_sz() {
        for (int i = tot; i >= 1; --i) {
            int u  = topo[i];
            int fa = st[u].fa;
            if (fa) st[fa].sz += st[u].sz;
        }
    }

/* ========= 本质不同子串数量 ========= */
    // void calc_distinct_substr() {
    //     distinct_substr = 0;
    //     for (int i = 2; i <= tot; ++i)           // 从 2 开始可省一次访问 root
    //         distinct_substr += st[i].len - st[st[i].fa].len;
    // }

/* ========= 常用查询 ========= */
    int count_occurrence(const string& t) {
        int u = 1;
        for (char ch : t) {
            int idx = ch - 'a';
            if (!st[u].ch[idx]) return 0;
            u = st[u].ch[idx];
        }
        return st[u].sz;
    }

int longest_repeated_substring() const {
        int ans = 0;
        for (int i = 2; i <= tot; ++i)
            if (st[i].sz >= 2) ans = max(ans, st[i].len);
        return ans;
    }

long long substring_rank(const string& t) { // 若不存在返回 -1
        /* 先在 topo 序中自底向上做一次 dp，不需要 memset */
        for (int i = 1; i <= tot; ++i) dp[i] = 1;  // 自身空串
        for (int i = tot; i >= 1; --i) {
            int u = topo[i];
            for (int k = 0; k < SIGMA; ++k)
                if (int v = st[u].ch[k]) dp[u] += dp[v];
        }

long long ans = 0;
        int u = 1;
        for (char ch : t) {
            int idx = ch - 'a';
            for (int k = 0; k < idx; ++k)
                if (int v = st[u].ch[k]) ans += dp[v];
            if (!st[u].ch[idx]) return -1;
            u = st[u].ch[idx];
        }
        return ans + 1;
    }

/* ========= DEMO ========= */
    void demo_solve() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        string s;
        if (!(cin >> s)) return;
        build_from_string(s);
        long long best = 0;
        for (int i = 2; i <= tot; ++i)                 // i=1 为根
            best = max(best, 1LL * st[i].sz * st[i].len);
        cout << best << '\n';
    }
};
```

```TEXT
Update date: 2025-10-21
Author: GuWolf
```

[1]: https://www.guwolf.com/usr/uploads/2025/12/1307036924.pdf