Updata ： 小椛椛的板子们2
实在不愿意再做题了，这几天写写板子。
若想找特定模板，请按Ctrl + F搜索
FFT（大家都会的FFT，这个写法跑的贼慢，不过好写易懂，rank1没了sad）
#include <cstdio> #include <iostream> #include <cmath> #define Max 3000000 #define rg register inline void read (int &n) { rg char c = getchar (); for (n = 0; !isdigit (c); c = getchar ()); for (; isdigit (c); n = n * 10 + c - '0', c = getchar ()); } typedef double flo; const flo PI = acos (-1.0); struct Vec { flo x, y; Vec (flo a = 0, flo b = 0) : x (a), y (b) {} Vec operator * (const Vec &rhs) const { return Vec (x * rhs.x - y * rhs.y, x * rhs.y + y * rhs.x); } Vec operator * (const flo &k) const { return Vec (x * k, y * k); } Vec operator + (const Vec &rhs) const { return Vec (x + rhs.x, y + rhs.y); } Vec operator - (const Vec &rhs) const { return Vec (x - rhs.x, y - rhs.y); } Vec &operator /= (const flo &k) { return x /= k, y /= k, *this; } }; using std :: swap; Vec a[Max], b[Max]; int N, M, Maxn, rd[Max]; void FFT (Vec *a, int N, int f = 1) { rg int i, j, k; for (i = 1; i < N; ++ i) if (rd[i] > i) swap (a[i], a[rd[i]]); for (k = 1; k < N; k <<= 1) { Vec wn (cos (PI / k), f * sin (PI / k)); for (j = 0; j < N; j += k << 1) { Vec w (1, 0), t; for (i = j; i < j + k; ++ i, w = w * wn) t = w * a[i + k], a[i + k] = a[i] - t, a[i] = a[i] + t; } } if (f == -1) for (i = 0; i < N; ++ i) a[i] /= N; } int main (int argc, char *argv[]) { read (N), read (M); rg int i; int x; ++ N, ++ M, Maxn = 1 << int (ceil (log2 (N + M))); for (i = 0; i < N; ++ i) read (x), a[i].x = x; for (i = 0; i < M; ++ i) read (x), b[i].x = x; for (i = 1; i < Maxn; ++ i) rd[i] = rd[i >> 1] >> 1 | (i & 1) * (Maxn >> 1); FFT (a, Maxn), FFT (b, Maxn); for (i = 0; i < Maxn; ++ i) a[i] = a[i] * b[i]; N = N + M - 2; for (FFT (a, Maxn, -1), i = 0; i <= N; ++ i) printf ("%d ", int (round (a[i].x))); return 0; }
Lucas 卢卡斯
#include <cstdio> #include <iostream> #define rg register inline void read (long long &n) { rg char c = getchar (); for (n = 0; !isdigit (c); c = getchar ()); for (; isdigit (c); n = n * 10 + c - '0', c = getchar ()); } #define Max 1213231 typedef long long LL; LL fac[Max]; LL Pow (LL x, LL p, LL mo) { LL a = x, res = 1; for (; p; p >>= 1, a *= a, a %= mo) if (p & 1) res *= a, res %= mo; return res % mo; } LL C (LL N, LL M, LL p) { return M > N ? 0 : ((fac[N] * Pow (fac[M], p - 2, p)) % p * Pow (fac[N - M], p - 2, p) % p); } LL Lucas (LL N, LL M, LL P) { return !M ? 1 : (C (N % P, M % P, P) * Lucas (N / P, M / P, P)) % P; } int main (int argc, char *argv[]) { LL T, x, y, p, L; read (T); rg int i; for (fac[0] = 1; T; -- T) { read (x), read (y), read (p); for (i = 1; i <= p; ++ i) fac[i] = fac[i - 1] * i, fac[i] %= p; printf ("%lld\n", Lucas (x + y, x, p)); } return 0; }
快速排序
虽然说不让用sort，但是我这种懒癌晚期的人怎么可能去手写sort呢？【其实是不会写
觉得过意不去，就写了快读和快输
#include <cstdio> #include <iostream> #include <algorithm> struct io { static const int BUF = 12310330; char p[BUF], *s, e[BUF], *t; int a[24]; io () : s(p), t(e) { fread (s, 1, sizeof p, stdin); } ~io () { fwrite (e, 1, t - e, stdout); } operator int() { static int v,j; v = 0,j = 1; for (v = 0, j = 1; *s < 48; j = *s++ ^ 45); do v = v * 10 + *s++ - 48; while (*s > 32); return j ? v : -v; } void print(int v) { static int *q = a; if (!v) *t++ = 48; else { if (v < 0) *t++ = 45, v *= -1; for (; v; *q++ = v % 10 + 48, v /= 10); for (; q != a; *t++ = *--q); } *t++ = 32; } } ip; #define Max 100007 int a[Max]; int main (int argc, char *argv[]) { #define rg register int N = ip; rg int i; for (i = 1; i <= N; ++ i) a[i] = ip; std :: sort (a + 1, a + 1 + N); for (i = 1; i <= N; ++ i) ip.print (a[i]); return 0; }
负环
递归spfa判负环
#include <cstdio> #include <iostream> #include <cstring> #define rg register struct IO { static const int BUF = 32312312; char p[BUF], *s; IO () : s (p) { fread (s, 1, sizeof p, stdin); } operator int () { rg int v, j = 1; for (v = 0, j = 1; *s < 48; j = *s ++ ^ 45); do v = v * 10 + *s ++ - 48; while (*s > 32); return j ? v : -v; } } ip; #define Max 400007 int N, M; bool is[Max], F; int _n[Max << 1], _v[Max << 1], list[Max], EC, _d[Max << 1], dis[Max]; inline void In (int u, int v, int d) { _v[++ EC] = v, _n[EC] = list[u], list[u] = EC, _d[EC] = d; } void Check (int n) { if (F) return ; is[n] = true; for (rg int i = list[n], v; i; i = _n[i]) if (dis[v = _v[i]] > dis[n] + _d[i]) { dis[v] = dis[n] + _d[i]; if (!is[v]) Check (v); else { F = true; return ; } } is[n] = false; } int main (int argc, char *argv[]) { rg int i, j; int x, y, z; for (int T = ip; T; -- T) { N = ip, M = ip; F = false; for (i = 1; i <= N; ++ i) dis[i] = list[i] = is[i] = false; for (i = 1, EC = 0; i <= M; ++ i) { x = ip, y = ip, z = ip; if (z < 0) In (x, y, z); else In (x, y, z), In (y, x, z); } for (i = 1; i <= N && !F; Check (i ++)); puts (F ? "YE5" : "N0"); } return 0; }
Tarjan强连通分量+缩点+拓扑最长路
#include <cstdio> #include <iostream> #include <stack> #include <queue> #define rg register struct IO { static const int BUF = 12312123; char p[BUF], *s; IO () : s (p) { fread (s, 1, sizeof p, stdin); } operator int () { rg int v = 0, f = true; for (; *s < 48; f = *s ++ ^ 45); do v = v * 10 + *s ++ - 48; while (*s > 32); return f ? v : -v; } } ip; int N; #define Max 10004 int _n[Max * 20], _v[Max * 20], list[Max], EC, key[Max]; inline void In (int u, int v) { _v[++ EC] = v, _n[EC] = list[u], list[u] = EC; } int dfn[Max], low[Max], DC, SC, scc[Max], val[Max]; std :: stack <int> S; inline void cmin (int &a, int b) { if (b < a) a = b; } void Tarjan (int n) { dfn[n] = low[n] = ++ DC; S.push (n); rg int v; for (rg int i = list[n]; i; i = _n[i]) if (!dfn[v = _v[i]]) Tarjan (v), cmin (low[n], low[v]); else if (!scc[v]) cmin (low[n], dfn[v]); if (low[n] == dfn[n]) { ++ SC; rg int r; for (r = n + 1; r != n; S.pop ()) scc[r = S.top ()] = SC, val[SC] += key[r]; } } int ev[Max], en[Max], el[Max], dis[Max], ec, in[Max]; inline void ei (int u, int v) { ev[++ ec] = v, en[ec] = el[u], el[u] = ec; ++ in[v]; } int f[Max]; inline void cmax (int &a, int b) { if (b > a) a = b; } void Topsort () { rg int i, v; std :: queue <int> Q; int s = 0; for (i = 1; i <= SC; ++ i) if (in[i] == 0) Q.push (i), f[i] = val[i], cmax (s, f[i]); for (int n; !Q.empty (); Q.pop ()) for (i = el[n = Q.front ()]; i; i = en[i]) { v = ev[i], cmax (f[v], f[n] + val[v]); if ((-- in[v]) == 0) Q.push (v); cmax (s, f[v]); } printf ("%d", s); } int main (int argc, char *argv[]) { int M; N = ip, M = ip; int x, y, z; rg int i; for (i = 1; i <= N; ++ i) key[i] = ip; for (i = 1; i <= M; ++ i) In (ip, ip); for (i = 1; i <= N; ++ i) if (!dfn[i]) Tarjan (i); for (int n = 1; n <= N; ++ n) for (i = list[n]; i; i = _n[i]) if (scc[_v[i]] != scc[n]) ei (scc[n], scc[_v[i]]); Topsort (); return 0; }
割点（顶）
#include <cstdio> #include <iostream> #define rg register struct IO { static const int BUF = 12312332; char p[BUF], *s; IO () : s (p) { fread (s, 1, sizeof p, stdin); } operator int () { rg int v = 0, j = 1; for (; *s < 48; j = *s ++ ^ 45); do v = v * 10 + *s ++ - 48; while (*s >= 48); return j ? v : -v; } } ip; #define Max 2000007 int N, Rt, is[Max]; inline void cmin (int &a, int b) { if (b < a) a = b; } int _n[Max], _v[Max], list[Max], EC, dfn[Max], low[Max], DC; inline void In (int u, int v) { _v[++ EC] = v, _n[EC] = list[u], list[u] = EC; } void Dfs (int n) { low[n] = dfn[n] = ++ DC; rg int i, v, r = 0; for (i = list[n]; i; i = _n[i]) { v = _v[i]; if (!dfn[v]) { Dfs (v), cmin (low[n], low[v]); if (low[v] >= dfn[n] && n != Rt) is[n] = true; if (n == Rt) ++ r; } cmin (low[n], dfn[v]); } if (r >= 2 && n == Rt) is[Rt] = true; } int main (int argc, char *argv[]) { int M, x, y; N = ip, M = ip; rg int i, s = 0; for (i = 1; i <= M; ++ i) x = ip, y = ip, In (x, y), In (y, x); for (Rt = 1; Rt <= N; ++ Rt) if (!dfn[Rt]) Dfs (Rt); for (i = 1; i <= N; ++ i) if (is[i]) ++ s; for (i = 1, printf ("%d\n", s); i <= N; ++ i) if (is[i]) printf ("%d ", i); return 0; }
高斯消元
#include <cstdio> #include <iostream> #include <algorithm> #define EPS 1e-8 #define rg register int N; #define Max 200 typedef double flo; flo a[Max][Max]; inline flo abs (flo x) { return x < 0 ? -x : x; } inline void swap (flo &a, flo &b) { flo c = a; a = b, b = c; } bool Gauss () { rg int i, j, k; flo n; for (i = 0; i < N; ++ i) { for (j = i + 1, k = i; j < N; ++ j) if (abs (a[j][i]) > abs (a[k][i])) k = j; if ((abs (n = a[k][i])) < EPS) return true; for (j = i; j <= N; ++ j) swap (a[i][j], a[k][j]); for (j = i; j <= N; ++ j) a[i][j] /= n; for (k = 0; k < N; ++ k) if (k != i) for (n = a[k][i], j = i; j <= N; ++ j) a[k][j] -= a[i][j] * n; } return false; } int main (int argc, char *argv[]) { scanf ("%d", &N); rg int i, j; for (i = 0; i < N; ++ i) for (j = 0; j <= N; ++ j) scanf ("%lf", &a[i][j]); if (Gauss ()) return puts ("No Solution"), 0; for (i = 0; i < N; ++ i) printf ("%.2lf\n", a[i][N]); return 0; }
st表
#include <cstdio> #include <iostream> #define rg register struct io { static const int BUF = 32310330; char p[BUF], *s, e[BUF], *t; int a[24]; io () : s (p), t (e) { fread (s, 1, sizeof p, stdin); } ~io () { fwrite (e, 1, t - e, stdout); } operator int () { static int v, j; v = 0,j = 1; for (v = 0, j = 1; *s < 48; j = *s ++ ^ 45); do v = v * 10 + *s++ - 48; while (*s > 32); return j ? v : -v; } void pt (int v) { static int *q = a; if (!v) *t ++ = 48; else { if (v < 0) *t ++ = 45, v *= -1; for (; v; *q ++ = v % 10 + 48, v /= 10); for (; q != a; *t ++ = *--q); } *t++ = '\n'; } } ip; #define Max 100005 int f[Max][22]; int lg[Max]; inline int max (int a, int b) { return a > b ? a : b; } int main (int argc, char *argv[]) { int N = ip, M = ip; rg int i, j; for (i = 1; i <= N; ++ i) f[i][0] = ip; for (lg[0] = 1, i = 2; i <= N; ++ i) { lg[i] = lg[i - 1]; if ((1 << lg[i] + 1) == i) ++ lg[i]; } for (i = N; i; -- i) for (j = 1; (i + (1 << j) - 1) <= N; ++ j) f[i][j] = max (f[i][j - 1], f[i + (1 << j - 1)][j - 1]); for (int x, y, l; M; -- M) { x = ip, y = ip; l = lg [y - x + 1]; ip.pt (max (f[x][l], f[y - (1 << l) + 1][l])); } return 0; }
高精
#include <cstdio> #include <iostream> #include <vector> #include <iomanip> #include <cassert> #include <algorithm> #include <cstring> const int Big_B = 10; const int Big_L = 1; inline int intcmp_ (int a, int b) { if (a > b) return 1; return a < b ? -1 : 0; } struct Int { #define rg register inline int max (int a, int b) { return a > b ? a : b; } inline int min (int a, int b) { return a < b ? a : b; } std :: vector <int> c; Int () {} typedef long long LL; Int (int x) { for (; x > 0; c.push_back (x % Big_B), x /= Big_B); } Int (LL x) { for (; x > 0; c.push_back (x % Big_B), x /= Big_B); } inline void CrZ () { for (; !c.empty () && c.back () == 0; c.pop_back ()); } inline Int &operator += (const Int &rhs) { c.resize (max (c.size (), rhs.c.size ())); rg int i, t = 0, S; for (i = 0, S = rhs.c.size (); i < S; ++ i) c[i] += rhs.c[i] + t, t = c[i] >= Big_B, c[i] -= Big_B & (-t); for (i = rhs.c.size (), S = c.size (); t && i < S; ++ i) c[i] += t, t = c[i] >= Big_B, c[i] -= Big_B & (-t); if (t) c.push_back (t); return *this; } inline Int &operator -= (const Int &rhs) { c.resize (max (c.size (), rhs.c.size ())); rg int i, t = 0, S; for (i = 0, S = rhs.c.size (); i < S; ++ i) c[i] -= rhs.c[i] + t, t = c[i] < 0, c[i] += Big_B & (-t); for (i = rhs.c.size (), S = c.size (); t && i < S; ++ i) c[i] -= t, t = c[i] < 0, c[i] += Big_B & (-t); CrZ (); return *this; } inline Int &operator *= (const Int &rhs) { rg int na = c.size (), i, j, S, ai; c.resize (na + rhs.c.size ()); LL t; for (i = na - 1; i >= 0; -- i) { ai = c[i], t = 0, c[i] = 0; for (j = 0, S = rhs.c.size (); j < S; ++ j) { t += c[i + j] + (LL) ai * rhs.c[j]; c[i + j] = t % Big_B, t /= Big_B; } for (j = rhs.c.size (), S = c.size (); t != 0 && i + j < S; ++ j) t += c[i + j], c[i + j] = t % Big_B, t /= Big_B; assert (t == 0); } CrZ (); return *this; } inline Int &operator /= (const Int &rhs) { return *this = div (rhs); } inline Int &operator %= (const Int &rhs) { return div (rhs), *this; } inline Int &shlb (int l = 1) { if (c.empty ()) return *this; c.resize (c.size () + l);rg int i; for (i = c.size () - 1; i >= l; -- i) c[i] = c[i - l]; for (i = 0; i < l; ++ i) c[i] = 0; return *this; } inline Int &shrb (int l = 1) { for (rg int i = 0; i < c.size () - l; ++ i) c[i] = c[i + l]; c.resize (max (c.size () - l, 0)); return *this; } inline Int div (const Int &rhs) { assert (!rhs.c.empty ()); Int q, r; rg int i; if (rhs > *this) return 0; q.c.resize (c.size () - rhs.c.size () + 1); rg int _l, _r, mid; for (i = c.size () - 1; i > c.size () - rhs.c.size (); -- i) r.shlb (), r += c[i]; for (i = c.size () - rhs.c.size (); i >= 0; -- i) { r.shlb (); r += c[i]; if (r.Comp (rhs) < 0) q.c[i] = 0; else { _l = 0, _r = Big_B; for (; _l != _r; ) { mid = _l + _r >> 1; if ((rhs * mid).Comp (r) <= 0) _l = mid + 1; else _r = mid; } q.c[i] = _l - 1, r -= rhs * q.c[i]; } } q.CrZ (), *this = r; return q; } inline int Comp (const Int &rhs) const { if (c.size () != rhs.c.size ()) return intcmp_ (c.size (), rhs.c.size ()); for (rg int i = c.size () - 1; i >= 0; -- i) if (c[i] != rhs.c[i]) return intcmp_ (c[i], rhs.c[i]); return 0; } friend inline Int operator + (const Int &lhs, const Int &rhs) { Int res = lhs; return res += rhs; } inline friend Int operator - (const Int &lhs, const Int &rhs) { if (lhs < rhs) { putchar ('-'); Int res = rhs; return res -= lhs; } else { Int res = lhs; return res -= rhs; } } friend inline Int operator * (const Int &lhs, const Int &rhs) { Int res = lhs; return res *= rhs; } friend inline Int operator / (const Int &lhs, const Int &rhs) { Int res = lhs; return res.div (rhs); } friend inline Int operator % (const Int &lhs, const Int &rhs) { Int res = lhs; return res.div (rhs), res; } friend inline std :: ostream &operator << (std :: ostream &out, const Int &rhs) { if (rhs.c.size () == 0) out << "0"; else { out << rhs.c.back (); for (rg int i = rhs.c.size () - 2; i >= 0; -- i) out << std :: setfill ('0') << std :: setw (Big_L) << rhs.c[i]; } return out; } friend inline std :: istream &operator >> (std :: istream &in, Int &rhs) { static char s[100000]; in >> s + 1; int Len = strlen (s + 1); int v = 0; LL r = 0, p = 1; for (rg int i = Len; i >= 1; -- i) { ++ v; r = r + (s[i] - '0') * p, p *= 10; if (v == Big_L) rhs.c.push_back (r), r = 0, v = 0, p = 1; } if (v != 0) rhs.c.push_back (r); return in; } friend inline bool operator < (const Int &lhs, const Int &rhs) { return lhs.Comp (rhs) < 0; } friend inline bool operator <= (const Int &lhs, const Int &rhs) { return lhs.Comp (rhs) <= 0; } friend inline bool operator > (const Int &lhs, const Int &rhs) { return lhs.Comp (rhs) > 0; } friend inline bool operator >= (const Int &lhs, const Int &rhs) { return lhs.Comp (rhs) >= 0; } friend inline bool operator == (const Int &lhs, const Int &rhs) { return lhs.Comp (rhs) == 0; } friend inline bool operator != (const Int &lhs, const Int &rhs) { return lhs.Comp (rhs) != 0; } #undef rg }; int Main () { return 0; } int ZlycerQan = Main (); int main (int argc, char *argv[]) {;}
主席树（区间第k小）
#include <cstdio> #include <iostream> #include <algorithm> #define rg register struct IO { static const int BUF = 12312332; char p[BUF], *s, *t, e[BUF]; int a[24]; IO () : s (p), t (e) { fread (s, 1, BUF, stdin); } ~IO () { fwrite (e, 1, t - e, stdout); } operator int () { rg int v = 0, j = 1; for (; *s < 48; j = *s ++ ^ 45); do v = v * 10 + *s ++ - 48; while (*s >= 48); return j ? v : -v; } void pt (int v) { static int *q = a; if (!v) *t ++ = 48; else { if (v < 0) *t ++ = 45; for (; v; *q ++ = v % 10 + 48, v /= 10); for (; q != a; *t ++ = *-- q); } *t ++ = '\n'; } } ip; #define Max 600006 namespace pr { int c[Max * 20][2], C, v[Max * 20], rt[Max]; void Updata (int pre, int &n, int l, int r, int t) { n = ++ C; v[n] = v[pre] + 1; if (l == r) return ; int m = l + r >> 1; if (t <= m) Updata (c[pre][0], c[n][0], l, m, t), c[n][1] = c[pre][1]; else Updata (c[pre][1], c[n][1], m + 1, r, t), c[n][0] = c[pre][0]; } int Query (int pre, int &n, int l, int r, int k) { if (l == r) return l; int m = l + r >> 1, res = v[c[n][0]] - v[c[pre][0]]; if (k <= res) return Query (c[pre][0], c[n][0], l, m, k); return Query (c[pre][1], c[n][1], m + 1, r, k - res); } } int a[Max], data[Max], C; int main (int argc, char *argv[]) { int N = ip, M = ip; rg int i; for (i = 1; i <= N; ++ i) a[i] = ip, data[++ C] = a[i]; std :: sort (data + 1, data + 1 + N); int S = std :: unique (data + 1, data + 1 + N) - data - 1; for (i = 1; i <= N; ++ i) { a[i] = std :: lower_bound (data + 1, data + 1 + S, a[i]) - data; pr :: Updata (pr :: rt[i - 1], pr :: rt[i], 1, S, a[i]); } int x, y, z; for (i = 1; i <= M; ++ i) { x = ip, y = ip, z = ip; ip.pt (data[pr :: Query (pr :: rt[x - 1], pr :: rt[y], 1, S, z)]); } return 0; }
树状数组（单点修改，区间求和）
#include <cstdio> #include <iostream> #define rg register struct IO { static const int BUF = 12312313; char *s, *t, p[BUF], e[BUF]; int a[24]; IO () : s (p), t (e) { fread (s, 1, BUF, stdin); } ~IO () { fwrite (e, 1, t - e, stdout); } operator int () { rg int v = 0, j = 1; for (; *s < 48; j = *s ++ ^ 45); do v = v * 10 + *s ++ - 48; while (*s >= 48); return j ? v : -v; } void pt (int v) { static int *q = a; if (!v) *t ++ = 48; else { if (v < 0) *t ++ = 45; for (; v; *q ++ = v % 10 + 48, v /= 10); for (; q != a; *t ++ = *-- q); } *t ++ = '\n'; } } ip; #define Max 1325630 namespace bit { int v[Max], N; inline void Pre (int x) { N = x; } int Query (int l, int r) { rg int i, res = 0; for (i = l - 1; i; i -= i & -i) res -= v[i]; for (i = r; i; i -= i & -i) res += v[i]; return res; } void Change (int p, int t) { for (rg int i = p; i <= N; i += i & -i) v[i] += t; return ; } } int main (int argc, char *argv[]) { int N = ip, M = ip; rg int i; bit :: Pre (N); for (i = 1; i <= N; ++ i) bit :: Change (i, ip); for (int t, x, y; M; -- M) { t = ip, x = ip, y = ip; if (t == 1) bit :: Change (x, y); else ip.pt (bit :: Query (x, y)); } return 0; }
LCA （树剖）
#include <cstdio> #include <iostream> #define rg register struct IO { static const int BUF = 12312313; char *s, *t, p[BUF], e[BUF]; int a[24]; IO () : s (p), t (e) { fread (s, 1, BUF, stdin); } ~IO () { fwrite (e, 1, t - e, stdout); } operator int () { rg int v = 0, j = 1; for (; *s < 48; j = *s ++ ^ 45); do v = v * 10 + *s ++ - 48; while (*s >= 48); return j ? v : -v; } void pt (int v) { static int *q = a; if (!v) *t ++ = 48; else { if (v < 0) *t ++ = 45; for (; v; *q ++ = v % 10 + 48, v /= 10); for (; q != a; *t ++ = *-- q); } *t ++ = '\n'; } } ip; #define Max 500009 int _n[Max << 1], _v[Max << 1], list[Max], EC; inline void In (int u, int v) { _v[++ EC] = v, _n[EC] = list[u], list[u] = EC; } int up[Max], son[Max], s[Max], f[Max], d[Max]; void Dfs_1 (int n, int F) { f[n] = F, d[n] = d[F] + 1, s[n] = 1; rg int i, v; for (i = list[n]; i; i = _n[i]) if ((v = _v[i]) != F) { Dfs_1 (v, n), s[n] += s[v]; if (s[son[n]] < s[v]) son[n] = v; } } void Dfs_2 (int n, int c) { up[n] = c; if (son[n]) Dfs_2 (son[n], c); else return ; for (rg int i = list[n], v; i; i = _n[i]) if ((v = _v[i]) != f[n] && v != son[n]) Dfs_2 (v, v); } inline void swap (int &a, int &b) { int c = a; a = b, b = c; } int Lca (int x, int y) { for (; up[x] != up[y]; x = f[up[x]]) if (d[up[x]] < d[up[y]]) swap (x, y); return d[x] < d[y] ? x : y; } int main (int argc, char *argv[]) { int N = ip, M = ip, Rt = ip, x, y; rg int i; for (i = 1; i < N; ++ i) x = ip, y = ip, In (x, y), In (y, x); Dfs_1 (Rt, 0), Dfs_2 (Rt, Rt); for (; M; -- M) ip.pt (Lca (ip, ip)); return 0; }
最短路（堆dij）
#include <cstdio> #include <iostream> #include <queue> #include <cstring> #define rg register struct IO { static const int BUF = 12312332; char p[BUF], *s; IO () : s (p) { fread (s, 1, sizeof p, stdin); } operator int () { rg int v = 0, j = 1; for (; *s < 48; j = *s ++ ^ 45); do v = v * 10 + *s ++ - 48; while (*s >= 48); return j ? v : -v; } } ip; struct D { int id, d; D (int a = 0, int b = 0) : id (a), d (b) {} bool operator < (const D &rhs) const { return d > rhs.d; } }; #define Max 100000 bool is[Max]; int _v[Max], _n[Max], list[Max], _d[Max], d[Max], EC; void Dij (int S, int T) { std :: priority_queue <D> Q; Q.push (D (S, 0)); rg int i, n, v; for (D res; !Q.empty (); ) { res = Q.top (); Q.pop (); if (is[res.id]) is[res.id] = true; if (res.id == T) return ; for (n = res.id, i = list[n]; i; i = _n[i]) if (d[v = _v[i]] > d[n] + _d[i]) d[v] = d[n] + _d[i], Q.push (D (v, d[v])); } } inline void In (int u, int v, int d) { _v[++ EC] = v, _n[EC] = list[u], list[u] = EC, _d[EC] = d; } int main (int argc, char *argv[]) { int N = ip, M = ip, S = ip, T = ip, x, y, z; rg int i; memset (d, 0x3f, sizeof d); for (i = 1; i <= M; ++ i) x = ip, y = ip, z = ip, In (x, y, z), In (y, x, z); Dij (S, T); printf ("%d", d[T]); return 0; }
线段树（区间加，区间乘，区间求和）
#include <cstdio> #include <iostream> typedef long long LL; #define rg register inline void read (LL &n) { rg char c = getchar (); for (n = 0; !isdigit (c); c = getchar ()); for (; isdigit (c); n = n * 10 + c - '0', c = getchar ()); } #define Max 100009 int L[Max << 2], R[Max << 2]; LL sm[Max << 2], tag1[Max << 2], tag2[Max << 2]; LL a[Max], P; void Build (int n, int l, int r) { L[n] = l, R[n] = r, tag2[n] = 1; if (l == r) { sm[n] = a[l], tag2[n] = 1; return ; } int m = l + r >> 1; Build (n << 1, l, m), Build (n << 1 | 1, m + 1, r); (sm[n] = sm[n << 1] + sm[n << 1 | 1]) %= P; } inline void Down (int n) { int lc = n << 1, rc = n << 1 | 1; if (tag2[n] != 1) { LL &t = tag2[n]; (tag1[lc] *= t) %= P, (tag1[rc] *= t) %= P; (tag2[lc] *= t) %= P, (tag2[rc] *= t) %= P; (sm[lc] *= t) %= P, (sm[rc] *= t) %= P; t = 1; } if (tag1[n]) { LL &t = tag1[n]; (tag1[lc] += t) %= P, (tag1[rc] += t) %= P; (sm[lc] += (R[lc] - L[lc] + 1) * t) %= P, (sm[rc] += (R[rc] - L[rc] + 1) * t) %= P; t = 0; } } void Modi (int n, int l, int r, bool t, LL to) { if (l <= L[n] && R[n] <= r) { if (t == false) (tag1[n] += to) %= P, (sm[n] += (R[n] - L[n] + 1) * to) %= P; else (tag1[n] *= to) %= P, (tag2[n] *= to) %= P, (sm[n] *= to) %= P; return ; } Down (n); int m = L[n] + R[n] >> 1; if (l <= m) Modi (n << 1, l, r, t, to); if (r > m) Modi (n << 1 | 1, l, r, t, to); (sm[n] = sm[n << 1] + sm[n << 1 | 1]) %= P; } LL Query (int n, int l, int r) { if (l <= L[n] && R[n] <= r) return sm[n]; Down (n); LL res = 0; int m = L[n] + R[n] >> 1; (sm[n] = sm[n << 1] + sm[n << 1 | 1]) %= P; if (l <= m) res = Query (n << 1, l, r); if (r > m) res += Query (n << 1 | 1, l, r); return res % P; } int main (int argc, char *argv[]) { int N, M; scanf ("%d%d", &N, &M); read (P); LL t, x, y, z; for (rg int i = 1; i <= N; ++ i) read (a[i]); for (Build (1, 1, N); M; -- M) { read (t), read (x), read (y); if (t == 1) read (z), Modi (1, x, y, true, z); else if (t == 2) read (z), Modi (1, x, y, false, z); else printf ("%lld\n", Query (1, x, y)); } return 0; }