模板

记录一下自己比较容易写错的模板/kk. 线段树 & 树链剖分 ```cpp const int N = 1e6;int mod; struct Gragh{//压行一直爽，一直压行一直爽 int cnt = 0 , val[N] , head[N] , nex[N] , edge[N]; void add(int x, int y) {nex[++cnt] = head[x];head[x] = cnt;edge[cnt] = y;} void addd(int x, int y) {add(x , y); add(y , x);} void point(int x , int v) {val[x] = v;} }; struct Segment{//线段树总计52- 13 + 1 = 40行 struct node{node *lson , *rson;ll val , tag;}; node dizhi[N * 2 + 10] , *root = &dizhi[0]; ll sum[N] , cnt = 0; void inii(int *a , int n) { for(int i = 1; i <= n; i++)sum[i] = a[i]; } void pushup(node *rt) { rt->val = (rt->lson->val + rt->rson->val)%mod; } void pushdown(node *rt , int l , int r) { if(rt->tag == 0)return ;int mid = (l + r)>>1; rt->lson->tag += rt->tag;rt->rson->tag += rt->tag; rt->lson->val += rt->tag * (mid - l + 1);rt->rson->val += rt->tag * (r - mid); rt->lson->val %= mod; rt->rson->val %= mod; rt->lson->tag %= mod; rt->rson->tag %= mod; rt->tag = 0; } void build(node *rt , int l , int r) { if(l == r) {rt->val = sum[l];rt->tag = 0;return ;} int mid = (l + r)>>1; rt->lson = &dizhi[++cnt];rt->rson = &dizhi[++cnt]; build(rt->lson , l , mid); build(rt->rson , mid + 1 , r); pushup(rt); } void update(node *rt ,int L , int R, int l , int r , ll v) { if(L <= l && r <= R) {rt->val += (r - l + 1) * v; rt->tag += v;return ;} int mid = (l + r)>>1; pushdown(rt , l , r); if(L <= mid)update(rt->lson , L , R , l , mid , v); if(mid + 1 <= R)update(rt->rson , L , R , mid + 1 , r , v); pushup(rt); } ll query(node *rt , int L , int R , int l , int r) { if(L <= l && r <= R)return rt->val; int mid = (l + r)>>1; pushdown(rt , l , r);ll ans = 0; if(L <= mid)ans += query(rt->lson , L , R , l , mid); if(mid + 1 <= R)ans += query(rt->rson , L , R , mid + 1 , r); return ans; } }; struct TreeDecomposition{//树链剖分总计54行 Gragh G;Segment kkk; int n; int dep[N] , fa[N] , siz[N] , son[N]; int id[N] , top[N] , w[N] , cnt = 0; void inii(Gragh _G , int _n , int rt) { G = _G;n = _n; dfs1(rt , 0);dfs2(rt , rt); kkk.inii(w , n);kkk.build(kkk.root , 1 , n); } void dfs1(int now , int f) { dep[now] = dep[f] + 1;fa[now] = f; siz[now] = 1;//自己 int t = -1;//目前重儿子的儿子数量 for(int i = G.head[now];i; i = G.nex[i]) { if(G.edge[i] == f)continue; int v = G.edge[i];dfs1(v , now); siz[now] += siz[v]; if(siz[v] > t)t = siz[v] , son[now] = v; } } void dfs2(int now , int topf) { id[now] = ++cnt;//新编号 w[cnt] = G.val[now];top[now] = topf; if(!son[now])return;//叶子 dfs2(son[now] , topf);//重儿子 for(int i = G.head[now];i; i = G.nex[i]) { int v = G.edge[i]; if(v == fa[now] || v == son[now])continue; dfs2(v , v);//轻儿子链头从它自己开始 } } int query(int x , int y) { int ans = 0; while(top[x] != top[y]) {//两点不在同一条链上。 if(dep[top[x]] < dep[top[y]])std::swap(x , y); ans += kkk.query(kkk.root , id[top[x]] , id[x] , 1 , n ); ans = ans % mod; x = fa[top[x]]; }if(dep[x] > dep[y])std::swap(x , y); ans += kkk.query(kkk.root , id[x] , id[y], 1 , n); return ans % mod; } void update(int x , int y , int k) { k %= mod; while(top[x] != top[y]) {//两点不在同一条链上。 if(dep[top[x]] < dep[top[y]])std::swap(x , y); kkk.update(kkk.root , id[top[x]] , id[x] , 1 , n , k); x = fa[top[x]]; }if(dep[x] > dep[y])std::swap(x , y); kkk.update(kkk.root , id[x] , id[y], 1 , n , k); } int qson(int x) {return kkk.query(kkk.root , id[x] , id[x] + siz[x] - 1, 1 , n) % mod;} void uson(int x , int k) {kkk.update(kkk.root , id[x] , id[x] + siz[x] - 1 , 1 , n, k);} }kkksc; ``` 写这种码量的东西不压行是真的难受。 exgcd & 逆元 &中国剩余定理 ```cpp int gcd(int a , int b) { if(b == 0)return a; return gcd(b , a%b); } void exgcd(int a ,int b ,int &d , int &x , int &y) { if(b == 0) { d = a;x = 1; y = 0; return ; } exgcd(b , a%b , d , x , y); int xp = x , yp = y; x = yp; y = xp - a/b * yp; } // a在膜b意义下的逆元 int inv(int a , int b) { int x , y , d; if(gcd(a , b) != 1)return -1; exgcd(a , b , d , x , y); return (x + b)%b; } ll CRT(const ll *a , const ll *m , int n) { ll ans = 0 , M = 1; for(int i = 1; i <= n; i++)M = M*m[i]; for(int i = 1; i <= n; i++) { ll Mi = M / m[i]; ll ti = inv(Mi , m[i]); ans = (ans + a[i] * Mi * ti)%M; } return ans%M; } ``` 欧拉函数，留坑，以后再填 ```cpp ll phi(ll x) { ll ret = x; for(ll i = 2; i * i <= x; i++) if(x % i == 0) { while(x % i == 0)x /= i; ret = ret / i* (i - 1) ; } if(x != 1)ret = ret /x* (x - 1); return ret; } ```