[关闭]
@jason-fan 2023-07-30T13:51:11.000000Z 字数 112222 阅读 137

OI Algorithm

jasonfan 的算法模板。

目录

DS

DLX.cpp - DS

  1. /*
  2.     Dancing Links X : 舞蹈链优化 X 算法
  3.     干啥的 --> 求解精准覆盖问题
  4.     Oi-wiki(Dancing Links) --> https://oi-wiki.org/search/dlx/
  5. */
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8. const int N = 505;
  9. int n, m, a[N][N];
  10. namespace DLX { // 舞蹈链，这实际上是个双十字循环链表
  11.     const int N = 10010;
  12.     int tot, fir[N], siz[N];
  13.     int L[N], R[N], U[N], D[N];
  14.     int col[N], row[N], st[N], ans;
  15.     void Remove(int c) {
  16.         L[R[c]] = L[c], R[L[c]] = R[c];
  17.         for (int i = D[c]; i != c; i = D[i]) for (int j = R[i]; j != i;
  18.                     j = R[j]) U[D[j]] = U[j], D[U[j]] = D[j], --siz[col[j]];
  19.     }
  20.     void Recover(int c) {
  21.         for (int i = U[c]; i != c; i = U[i]) for (int j = L[i]; j != i;
  22.                     j = L[j]) U[D[j]] = D[U[j]] = j, ++siz[col[j]];
  23.         L[R[c]] = R[L[c]] = c;
  24.     }
  25.     void Insert(int r, int c) {
  26.         ++tot; row[tot] = r; col[tot] = c; ++siz[c];
  27.         U[tot] = c; D[tot] = D[c]; U[D[c]] = tot; D[c] = tot;
  28.         if (!fir[r])
  29.             fir[r] = L[tot] = R[tot] = tot;
  31.         else {
  32.             L[tot] = fir[r]; R[tot] = R[fir[r]];
  33.             L[R[fir[r]]] = tot; R[fir[r]] = tot;
  34.         }
  35.     }
  36.     void Build(int r, int c) {
  37.         for (int i = 0; i <= c; ++i) L[i] = i - 1, R[i] = i + 1, U[i] = D[i] = i;
  38.         L[0] = c, R[c] = 0; tot = c;
  39.         memset(fir, 0, sizeof(fir));
  40.         memset(siz, 0, sizeof(siz));
  41.     }
  42.     bool Dance(int dep) {
  43.         int c = R[0];
  44.         if (!R[0]) { ans = dep; return 1;}
  45.         for (int i = R[0]; i != 0; i = R[i]) if (siz[i] < siz[c]) c = i;
  46.         Remove(c);
  47.         for (int i = D[c]; i != c; i = D[i]) {
  48.             st[dep] = row[i];
  49.             for (int j = R[i]; j != i; j = R[j]) Remove(col[j]);
  50.             if (Dance(dep + 1)) return 1;
  51.             for (int j = L[i]; j != i; j = L[j]) Recover(col[j]);
  52.         }
  53.         Recover(c);
  54.         return 0;
  55.     }
  56. }
  57. void solve() {
  58.     using namespace DLX;
  59.     Build(n, m);
  60.     for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) if (a[i][j] == 1) Insert(i, j);
  61.     bool fg = Dance(1);
  62.     if (!fg) puts("No Solution!");
  63.     else {
  64.         for (int i = 1; i < ans; ++i) printf("%d ", st[i]);
  65.         printf("\n");
  66.     }
  67. }
  68. int main() {
  69.     scanf("%d%d", &n, &m);
  70.     for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) scanf("%d", &a[i][j]);
  71.     solve();
  72. }

fenwick.cpp - DS

  1. // 树状数组(Fenwick Tree) 区间加减，区间求和
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. typedef long long ll;
  5. const int N = 1000010;
  6. struct fenwick {
  7.     ll s1[N], s2[N]; int n;
  8.     void _add(int p, int v) {for (int x = p; x <= n; x += x & -x) s1[x] += v, s2[x] += (ll)v * p;}
  9.     ll ask(int p) {ll r = 0; for (int x = p; x > 0; x -= x & -x) r += (ll)(p + 1) * s1[x] - s2[x]; return r;}
  10.     ll query(int l, int r) {return ask(r) - ask(l - 1);}
  11.     void modify(int l, int r, int v) {_add(l, v); _add(r + 1, -v);}
  12.     void init(int n, int a[]) {
  13.         fenwick::n = n;
  14.         for (int i = 1, j; i <= n; ++i) {
  15.             s1[i] += a[i] - a[i - 1]; s2[i] += (ll)(a[i] - a[i - 1]) * i;
  16.             j = i + (i & -i);
  17.             if (j <= n) s1[j] += s1[i], s2[j] += s2[i];
  18.         }
  19.     }
  20. } T;
  21. int n, q, a[N];
  22. int main() {
  23.     scanf("%d%d", &n, &q);
  24.     for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  25.     T.init(n, a);
  26.     while (q--) {
  27.         int op, l, r, x;
  28.         scanf("%d%d%d", &op, &l, &r);
  29.         if (op == 1) {
  30.             scanf("%d", &x);
  31.             T.modify(l, r, x);
  32.         } else
  33.             printf("%lld\n", T.query(l, r));
  34.     }
  35.     return 0;
  36. }

fhqTreap.cpp - DS

  1. // fhq - treap 简易模板
  2. #include <bits/stdc++.h>
  3. #define ls(p) t[p].l
  4. #define rs(p) t[p].r
  5. #define mid ((l+r)>>1)
  6. using namespace std;
  7. const int N = 100010;
  8. mt19937 rd(random_device{}()); // random maker
  9. struct node {
  10.     int l, r, siz, rnd, val, tag; /* other data/tags */
  11. } t[N]; int tot, root;
  12. /* ---------- for recycle nodes ------------
  13. int cyc[N],cyccnt;
  14. inline void delnode(int p) {cyc[++cyccnt]=p;}
  15. inline void newnode(int val) {
  16.     int id=(cyccnt>0)?cyc[cyccnt--]:++tot;
  17.     t[id]={0,0,1,(int)(rd()),val}; return id;
  18. }
  19. */
  20. inline int newnode(int val) { t[++tot] = {0, 0, 1, (int)(rd()), val}; return tot;} // create a new node
  21. inline void updata(int p) {t[p].siz = t[ls(p)].siz + t[rs(p)].siz + 1; /* pushup other datas */ }
  22. inline void pushtag(int p, int vl) { /* tag to push */ }
  23. inline void pushdown(int p) {
  24.     if (t[p].tag != std_tag) {
  25.         if (ls(p)) pushtag(ls(p), t[p].tag);
  26.         if (rs(p)) pushtag(rs(p), t[p].tag);
  27.         t[p].tag = std_tag;
  28.     }
  29. }
  30. int merge(int p, int q) {
  31.     if (!p || !q) return p + q;
  32.     if (t[p].rnd < t[q].rnd) {
  33.         pushdown(p);
  34.         rs(p) = merge(rs(p), q);
  35.         updata(p); return p;
  36.     } else {
  37.         pushdown(q);
  38.         ls(q) = merge(p, ls(q));
  39.         updata(q); return q;
  40.     }
  41. }
  42. void split(int p, int k, int &x, int &y) {
  43.     if (!p) x = 0, y = 0;
  44.     else {
  45.         pushdown(p);
  46.         if (t[ls(p)].siz >= k) y = p, split(ls(p), k, x, ls(p));
  47.         else x = p, split(rs(p), k - t[ls(p)].siz - 1, rs(p), y);
  48.         updata(p);
  49.     }
  50. }
  51. int build(int l, int r) { // build tree on a[l..r], return the root
  52.     if (l > r) return 0;
  53.     return merge(build(l, mid - 1), merge(newnode(a[mid]), build(mid + 1, r)));
  54. }
  55. /*
  56.     other functions base on split() and merge()
  58. */
  59. int main() {
  60. }

fhq_treap.cpp - DS

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. template<typename DataType, int N = 100010>
  4. struct fhq_Treap {
  5.   private:
  6.     const DataType inf; //inf的定义
  7.     struct node {
  8.         DataType key; int rnd;
  9.         int siz, l, r;
  10.     } d[N];
  11.     int rt = 0, tot;
  12.     void updata(int t) {
  13.         d[t].siz = d[d[t].l].siz + d[d[t].r].siz + 1;
  14.     }
  15.     pair<int, int> split(int t, int p) {
  16.         pair<int, int> res(0, 0);
  17.         if (t == 0) return res;
  18.         if (p <= d[d[t].l].siz) {
  19.             res = split(d[t].l, p);
  20.             d[t].l = res.second;
  21.             updata(t);
  22.             res.second = t;
  23.         } else {
  24.             res = split(d[t].r, p - 1 - d[d[t].l].siz);
  25.             d[t].r = res.first;
  26.             updata(t);
  27.             res.first = t;
  28.         }
  29.         return res;
  30.     }
  31.     int merge(int a, int b) {
  32.         if (a == 0) return b;
  33.         if (b == 0) return a;
  34.         if (d[a].rnd < d[b].rnd) {
  35.             d[a].r = merge(d[a].r, b);
  36.             updata(a);
  37.             return a;
  38.         }
  39.         d[b].l = merge(a, d[b].l);
  40.         updata(b);
  41.         return b;
  42.     }
  43.     int x_rank(int t, DataType key) {
  44.         if (t == 0) return 1;
  45.         if (!(d[t].key < key)) return x_rank(d[t].l, key); //key<=d[t].key
  46.         return d[d[t].l].siz + 1 + x_rank(d[t].r, key);
  47.     }
  48.     DataType getkey(int t, int rk) {
  49.         if (rk <= d[d[t].l].siz) return getkey(d[t].l, rk);
  50.         if (rk == d[d[t].l].siz + 1) return d[t].key;
  51.         return getkey(d[t].r, rk - d[d[t].l].siz - 1);
  52.     }
  53.     int pre(int t, DataType key, int res = 0) {
  54.         if (t == 0) return res;
  55.         if (d[t].key < key) return pre(d[t].r, key, t);
  56.         return pre(d[t].l, key, res);
  57.     }
  58.     int nxt(int t, DataType key, int res = 0) {
  59.         if (t == 0) return res;
  60.         if (key < d[t].key) return nxt(d[t].l, key, t);
  61.         return nxt(d[t].r, key, res);
  62.     }
  63.     int newnode(DataType key) {
  64.         d[++tot] = {key, rand(), 1, 0, 0};
  65.         return tot;
  66.     }
  67.   public:
  68.     void build() {
  69.         rt = tot = 0;
  70.         srand(time(0));
  71.         rt = newnode(inf); //这里需要修改
  72.         d[rt].l = newnode(-inf);
  73.         updata(rt);
  74.     }
  75.     void insert(DataType key) {
  76.         int k = x_rank(rt, key);
  77.         pair<int, int> a = split(rt, k - 1);
  78.         rt = merge(merge(a.first, newnode(key)), a.second);
  79.     }
  80.     void remove(DataType key) {
  81.         int k = x_rank(rt, key);
  82.         pair<int, int> a = split(rt, k - 1), b = split(a.second, 1);
  83.         rt = merge(a.first, b.second);
  84.     }
  85.     int getrank(DataType key) {
  86.         return x_rank(rt, key);
  87.     }
  88.     DataType getpre(DataType key) {
  89.         return d[pre(rt, key)].key;
  90.     }
  91.     DataType getnxt(DataType key) {
  92.         return d[nxt(rt, key)].key;
  93.     }
  94.     DataType getkey(int rk) {
  95.         return getkey(rt, rk);
  96.     }
  97.     int getroot() {
  98.         return rt;
  99.     }
  100. };

hashtable.cpp - DS

  1. #include <cstring>
  2. typedef long long ll;
  4. namespace hashtable1 {
  5.     const int M = 19260817;
  6.     const int MAX_SIZE = 2000000;
  7.     struct Hash_map {
  8.         struct data {
  9.             int nxt;
  10.             ll key, value; // (key,value)
  11.         } e[MAX_SIZE];
  12.         int head[M], size;
  13.         inline int f(ll key) { return key % M; } // 哈希函数
  14.         ll &operator[](const ll &key) { // 重载[]
  15.             int ky = f(key);
  16.             for (int i = head[ky]; i != -1; i = e[i].nxt)
  17.                 if (e[i].key == key) return e[i].value;
  18.             return e[++size] = data{head[ky], key, 0}, head[ky] = size, e[size].value;
  19.         }
  20.         void clear() { // 清空
  21.             memset(head, -1, sizeof(head));
  22.             size = 0;
  23.         }
  24.         Hash_map() {clear();} // 初始化清空
  25.     };
  26. }
  28. namespace hashtable2 {
  29.     const int M = 19260817;
  30.     const int MAX_SIZE = 2000000;
  31.     struct Hash {
  32.         struct data {
  33.             int nxt;
  34.             ll key, value;
  35.         } e[MAX_SIZE];
  36.         int head[M], size;
  37.         inline int f(ll key) { return key % M; } // 哈希函数
  38.         void clear() { // 清空
  39.             memset(head, -1, sizeof(head));
  40.             size = 0;
  41.         }
  42.         ll query(ll key) { // 查询
  43.             for (int i = head[f(key)]; i != -1; i = e[i].nxt)
  44.                 if (e[i].key == key) return e[i].value;
  45.             return -1;
  46.         }
  47.         ll modify(ll key, ll value) { // 修改
  48.             for (int i = head[f(key)]; i != -1; i = e[i].nxt)
  49.                 if (e[i].key == key) return e[i].value = value;
  50.             return -1;
  51.         }
  52.         ll insert(ll key, ll value) { // 插入
  53.             if (query(key) != -1) return -1;
  54.             e[++size] = data{head[f(key)], key, value};
  55.             head[f(key)] = size;
  56.             return value;
  57.         }
  58.     };
  59. }

KDTree1.cpp - DS

  1. /*
  2.     luogu P4357 [CQOI2016]K 远点对
  3.     K-D Tree 二维平面邻域查询
  4.     题意：平面上 N (1e5) 个点，求第 K (1e2) 远点对距离
  5. */
  6. #include <bits/stdc++.h>
  7. template <typename T>
  8. inline void red(T &x) {
  9.     x = 0; bool f = 0; char ch = getchar();
  10.     while (ch < '0' || ch > '9') {if (ch == '-') f ^= 1; ch = getchar();}
  11.     while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (T)(ch ^ 48), ch = getchar();
  12.     if (f) x = -x;
  13. }
  14. using namespace std;
  15. typedef double db;
  16. typedef long long ll;
  17. const int N = 100010;
  18. int n, k;
  19. priority_queue<ll, vector<ll>, greater<ll> >q;
  20. template <typename _Tp> inline void umin(_Tp &x, _Tp y) {(x > y) &&(x = y);}
  21. template <typename _Tp> inline void umax(_Tp &x, _Tp y) {(x < y) &&(x = y);}
  22. namespace KDTree {
  23.     struct node {
  24.         int X[2];
  25.         int &operator[](const int k) {return X[k];}
  26.     } p[N];
  27.     int nowd;
  28.     bool cmp(node a, node b) {return a.X[nowd] < b.X[nowd];}
  29.     int lc[N], rc[N], L[N][2], R[N][2]; // lc/rc 左右孩子；L/R 对应超矩形各个维度范围
  30.     inline ll sqr(int x) {return 1ll * x * x;}
  31.     void pushup(int x) { // 更新该点所代表空间范围
  32.         L[x][0] = R[x][0] = p[x][0];
  33.         L[x][1] = R[x][1] = p[x][1];
  34.         if (lc[x]) {
  35.             umin(L[x][0], L[lc[x]][0]); umax(R[x][0], R[lc[x]][0]);
  36.             umin(L[x][1], L[lc[x]][1]); umax(R[x][1], R[lc[x]][1]);
  37.         }
  38.         if (rc[x]) {
  39.             umin(L[x][0], L[rc[x]][0]); umax(R[x][0], R[rc[x]][0]);
  40.             umin(L[x][1], L[rc[x]][1]); umax(R[x][1], R[rc[x]][1]);
  41.         }
  42.     }
  43.     int build(int l, int r) {
  44.         if (l > r) return 0;
  45.         int mid = (l + r) >> 1;
  46.         // >>> 方差建树
  47.         db av[2] = {0, 0}, va[2] = {0, 0}; // av 平均数，va 方差
  48.         for (int i = l; i <= r; ++i) av[0] += p[i][0], av[1] += p[i][1];
  49.         av[0] /= (r - l + 1); av[1] /= (r - l + 1);
  50.         for (int i = l; i <= r; ++i) {
  51.             va[0] += sqr(av[0] - p[i][0]);
  52.             va[1] += sqr(av[1] - p[i][1]);
  53.         }
  54.         if (va[0] > va[1]) nowd = 0;
  55.         else nowd = 1; // 找方差大的维度划分
  56.         // >>> 轮换建树 nowd=dep%D
  57.         nth_element(p + l, p + mid, p + r + 1, cmp); // 以该维度中位数分割
  58.         lc[mid] = build(l, mid - 1); rc[mid] = build(mid + 1, r);
  59.         pushup(mid);
  60.         return mid;
  61.     }
  62.     ll dist(int a, int x) { // 估价函数，点 a 到树上 x 点对应空间最远距离
  63.         return max(sqr(p[a][0] - L[x][0]), sqr(p[a][0] - R[x][0])) +
  64.                max(sqr(p[a][1] - L[x][1]), sqr(p[a][1] - R[x][1]));
  65.     }
  66.     void query(int l, int r, int a) { // 点 a 邻域查询
  67.         if (l > r) return ;
  68.         int mid = (l + r) >> 1;
  69.         ll t = sqr(p[mid][0] - p[a][0]) + sqr(p[mid][1] - p[a][1]);
  70.         if (t > q.top()) q.pop(), q.push(t); // 更新答案
  71.         ll disl = dist(a, lc[mid]), disr = dist(a, rc[mid]);
  72.         if (disl > q.top() && disr > q.top()) // 两边都有机会更新，优先搜大的
  73.             (disl > disr) ? (query(l, mid - 1, a), query(mid + 1, r, a)) : (query(mid + 1, r, a), query(l, mid - 1, a));
  75.         else
  76.             (disl > q.top()) ? query(l, mid - 1, a) : query(mid + 1, r, a);
  77.     }
  78. }
  79. using namespace KDTree;
  80. int main() {
  81.     red(n); red(k); k *= 2;
  82.     for (int i = 1; i <= k; ++i) q.push(0);
  83.     for (int i = 1; i <= n; ++i) red(p[i][0]), red(p[i][1]);
  84.     build(1, n);
  85.     for (int i = 1; i <= n; ++i) query(1, n, i);
  86.     printf("%lld\n", q.top());
  87. }

KDTree2.cpp - DS

  1. /*
  2.     K-D Tree 维护空间权值 (单点修改 & 空间查询)
  3.     时间复杂度 O(log n) ~ O(n^(1-1/k))
  4. */
  5. #include <bits/stdc++.h>
  6. template <typename T>
  7. inline void red(T &x) {
  8.     x = 0; bool f = 0; char ch = getchar();
  9.     while (ch < '0' || ch > '9') {if (ch == '-') f ^= 1; ch = getchar();}
  10.     while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (T)(ch ^ 48), ch = getchar();
  11.     if (f) x = -x;
  12. }
  13. using namespace std;
  14. const int N = 200010;
  15. typedef double db;
  16. template <typename _Tp> void umin(_Tp &x, _Tp y) {if (x > y) x = y;}
  17. template <typename _Tp> void umax(_Tp &x, _Tp y) {if (x < y) x = y;}
  18. template <typename _Tp> _Tp sqr(_Tp x) {return x * x;}
  19. namespace KDT {
  20.     struct dat {
  21.         int X[2];
  22.         int &operator[](const int k) {return X[k];}
  23.     } p[N];
  24.     db alp = 0.725; // 重构常数
  25.     int nowd;
  26.     bool cmp(int a, int b) {return p[a][nowd] < p[b][nowd];}
  27.     int root, cur, d[N], lc[N], rc[N], L[N][2], R[N][2], siz[N], sum[N], val[N];
  28.     //  root:根 cur:总点数 d:当前分割维度 lc/rc:左右儿子 L/R:当前空间范围 siz:子树大小  sum/val 空间的值,单点的值
  29.     int g[N], t; // 用于重构的临时数组
  30.     void pushup(int x) {
  31.         siz[x] = siz[lc[x]] + siz[rc[x]] + 1;
  32.         sum[x] = sum[lc[x]] + sum[rc[x]] + val[x];
  33.         L[x][0] = R[x][0] = p[x][0];
  34.         L[x][1] = R[x][1] = p[x][1];
  35.         if (lc[x]) {
  36.             umin(L[x][0], L[lc[x]][0]); umax(R[x][0], R[lc[x]][0]);
  37.             umin(L[x][1], L[lc[x]][1]); umax(R[x][1], R[lc[x]][1]);
  38.         }
  39.         if (rc[x]) {
  40.             umin(L[x][0], L[rc[x]][0]); umax(R[x][0], R[rc[x]][0]);
  41.             umin(L[x][1], L[rc[x]][1]); umax(R[x][1], R[rc[x]][1]);
  42.         }
  43.     }
  44.     int build(int l, int r) { // 对 g[1...t] 进行建树 ，！！注意了，对应点都是 g[x]
  45.         if (l > r) return 0;
  46.         int mid = (l + r) >> 1;
  47.         db av[2] = {0, 0}, va[2] = {0, 0};
  48.         for (int i = l; i <= r; ++i) av[0] += p[g[i]][0], av[1] += p[g[i]][1];
  49.         av[0] /= (r - l + 1); av[1] /= (r - l + 1);
  50.         for (int i = l; i <= r; ++i) va[0] += sqr(av[0] - p[g[i]][0]), va[1] += sqr(av[1] - p[g[i]][1]);
  51.         if (va[0] > va[1]) d[g[mid]] = nowd = 0;
  52.         else d[g[mid]] = nowd = 1;
  53.         nth_element(g + l, g + mid, g + r + 1, cmp);
  54.         lc[g[mid]] = build(l, mid - 1); rc[g[mid]] = build(mid + 1, r);
  55.         pushup(g[mid]);
  56.         return g[mid];
  57.     }
  58.     void expand(int x) { // 将子树展开到临时数组里
  59.         if (!x) return;
  60.         expand(lc[x]);
  61.         g[++t] = x;
  62.         expand(rc[x]);
  63.     }
  64.     void rebuild(int &x) { // x 所在子树重构
  65.         t = 0; expand(x);
  66.         x = build(1, t);
  67.     }
  68.     bool chk(int x) {return alp * siz[x] <= (db)max(siz[lc[x]], siz[rc[x]]);} // 判断失衡
  69.     void insert(int &x, int a) { // 插入点 a , p[a],val[a] 为其信息
  70.         if (!x) { x = a; pushup(x); d[x] = rand() & 1; return; }
  71.         if (p[a][d[x]] <= p[x][d[x]]) insert(lc[x], a);
  72.         else insert(rc[x], a);
  73.         pushup(x);
  74.         if (chk(x)) rebuild(x); // 失衡暴力重构
  75.     }
  76.     dat Lt, Rt; // 询问一块空间的值(为了减小常数把参数放在外面)
  77.     int query(int x) {
  78.         if (!x || Rt[0] < L[x][0] || Lt[0] > R[x][0] || Rt[1] < L[x][1]
  79.             || Lt[1] > R[x][1]) return 0; // 结点为空或与询问取间无交
  80.         if (Lt[0] <= L[x][0] && R[x][0] <= Rt[0] && Lt[1] <= L[x][1]
  81.             && R[x][1] <= Rt[1]) return sum[x]; // 区间完全覆盖
  82.         int ret = 0;
  83.         if (Lt[0] <= p[x][0] && p[x][0] <= Rt[0] && Lt[1] <= p[x][1]
  84.             && p[x][1] <= Rt[1]) ret += val[x]; // 当前点在区间内
  85.         return query(lc[x]) + query(rc[x]) + ret;
  86.     }
  87. }
  88. using namespace KDT;
  89. int n, lstans;
  90. int main() {
  91.     red(n);
  92.     for (int op;;) {
  93.         red(op);
  94.         switch (op) {
  95.         case 1:
  96.             ++cur; red(p[cur][0]); red(p[cur][1]); red(val[cur]);
  97.             p[cur][0] ^= lstans; p[cur][1] ^= lstans; val[cur] ^= lstans;
  98.             insert(root, cur);
  99.             break;
  100.         case 2:
  101.             red(Lt[0]); red(Lt[1]); red(Rt[0]); red(Rt[1]);
  102.             Lt[0] ^= lstans; Lt[1] ^= lstans; Rt[0] ^= lstans; Rt[1] ^= lstans;
  103.             printf("%d\n", lstans = query(root));
  104.             break;
  105.         case 3: return 0; break;
  106.         }
  107.     }
  108.     return 0;
  109. }

LCT.cpp - DS

  1. // Link Cut Tree
  2. #include <cstdio>
  3. template <typename T>
  4. inline void red(T &x) {
  5.     x = 0; bool f = 0; char ch = getchar();
  6.     while (ch < '0' || ch > '9') {if (ch == '-') f ^= 1; ch = getchar();}
  7.     while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (T)(ch ^ 48), ch = getchar();
  8.     if (f) x = -x;
  9. }
  10. template <typename _Tp> void swap(_Tp &x, _Tp &y) {_Tp tmp = x; x = y; y = tmp;}
  11. const int N = 100010;
  12. namespace LCT {
  13.     int ch[N][2], f[N], sum[N], val[N], tag[N], dat[N]; // dat 维护的链信息, val 点上信息
  14.     inline void PushUp(int x) {
  15.         dat[x] = dat[ch[x][0]] ^ dat[ch[x][1]] ^ val[x];
  16.     }
  17.     inline void PushRev(int x) {swap(ch[x][0], ch[x][1]); tag[x] ^= 1;}
  18.     inline void PushDown(int x) {
  19.         if (tag[x] == 0) return ;
  20.         PushRev(ch[x][0]); PushRev(ch[x][1]); tag[x] = 0;
  21.     }
  22.     inline bool Get(int x) {return ch[f[x]][1] == x;} // 是父亲的哪个儿子
  23.     inline bool IsRoot(int x) {return (ch[f[x]][1] != x && ch[f[x]][0] != x);} // 是否是当前 Splay 的根
  24.     inline void Rotate(int x) { // Splay 旋转
  25.         int y = f[x], z = f[y], k = Get(x);
  26.         if (!IsRoot(y)) ch[z][Get(y)] = x;
  27.         ch[y][k] = ch[x][k ^ 1]; f[ch[x][k ^ 1]] = y;
  28.         ch[x][k ^ 1] = y; f[y] = x; f[x] = z;
  29.         PushUp(y); PushUp(x);
  30.     }
  31.     void Updata(int x) { // Splay 中从上到下 PushDown
  32.         if (!IsRoot(x)) Updata(f[x]);
  33.         PushDown(x);
  34.     }
  35.     inline void Splay(int x) { // Splay 上把 x 转到根
  36.         Updata(x);
  37.         for (int fa; fa = f[x], !IsRoot(x); Rotate(x)) {
  38.             if (!IsRoot(fa)) Rotate(Get(fa) == Get(x) ? fa : x);
  39.         }
  40.         PushUp(x);
  41.     }
  42.     inline void Access(int x) { // 辅助树上打通 x 到根的路径(即 x 到根变为实链)
  43.         for (int p = 0; x; p = x, x = f[x]) {
  44.             Splay(x); ch[x][1] = p; PushUp(x);
  45.         }
  46.     }
  47.     inline void MakeRoot(int x) { // 钦定 x 为辅助树根
  48.         Access(x); Splay(x); PushRev(x);
  49.     }
  50.     inline int FindRoot(int x) { // 找 x 所在辅助树根
  51.         Access(x); Splay(x);
  52.         while (ch[x][0]) PushDown(x), x = ch[x][0];
  53.         Splay(x); // 不加复杂度会假
  54.         return x;
  55.     }
  56.     inline void Split(int x, int y) { // 把 x 到 y 的路径提出来, 并以 y 为 Splay 根
  57.         MakeRoot(x); Access(y); Splay(y);
  58.     }
  59.     inline bool Link(int x, int y) { // 连接 x,y 两点
  60.         MakeRoot(x);
  61.         if (FindRoot(y) == x) return false;
  62.         f[x] = y;
  63.         return true;
  64.     }
  65.     inline bool Cut(int x, int y) { // x,y 断边
  66.         MakeRoot(x);
  67.         if (FindRoot(y) == x && f[y] == x && !ch[y][0]) {
  68.             f[y] = ch[x][1] = 0; PushUp(x);
  69.             return true;
  70.         }
  71.         return false;
  72.     }
  73.     // 如果保证合法
  74.     /*
  75.     inline void Link(int x,int y) {
  76.         MakeRoot(x); MakeRoot(y); f[x]=y;
  77.     }
  78.     inline void Cut(int x,int y) {
  79.         MakeRoot(x); Access(y); Splay(y); ch[y][0]=f[x]=0;
  80.     }
  81.     */
  82.     /*
  83.     void Print(int x) {
  84.         if(ch[x][0]) Print(ch[x][0]);
  85.         printf("%d,",x);
  86.         if(ch[x][1]) Print(ch[x][1]);
  87.     }
  88.     */
  89. }
  90. using namespace LCT;
  91. int n, m;
  92. int main() {
  93.     red(n); red(m);
  94.     for (int i = 1; i <= n; ++i) red(val[i]);
  95.     for (int i = 1; i <= m; ++i) {
  96.         int op, x, y; red(op); red(x); red(y);
  97.         switch (op) {
  98.         case 0: Split(x, y); printf("%d\n", dat[y]); break;
  99.         case 1: Link(x, y); break;
  100.         case 2: Cut(x, y); break;
  101.         case 3: Splay(x); val[x] = y; break;
  102.         }
  103.     }
  104. }

leftist-tree.cpp - DS

  1. /* 左偏树 (可并堆)
  2. + 左偏树是一棵二叉树，有堆的性质
  3. + 每个节点左儿子dist >= 右儿子dist
  4. + 每个节点的 dist 都等于其右儿子的 dist 加一
  5. */
  6. #include <bits/stdc++.h>
  7. #define ls(x) t[x].ch[0]
  8. #define rs(x) t[x].ch[1]
  9. using namespace std;
  10. const int N = 100010;
  11. struct node {
  12.     int rt, ch[2], d, val;
  13.     /* other tags */
  14.     node() {}
  15. } t[N];
  16. int n, m;
  17. void settag(int x, int vl) {
  18.     if (!x) { /* set tag */ }
  19. }
  20. void pushdown(int x) {
  21.     /* pushdown tags */
  22. }
  23. int merge(int x, int y) {
  24.     if (!x || !y) return x + y;
  25.     if (t[x].val > t[y].val || (t[x].val == t[y].val && x > y)) swap(x, y);
  26.     pushdown(x); rs(x) = merge(rs(x), y); t[x].rt = t[ls(x)].rt = t[rs(x)].rt = x;
  27.     if (t[ls(x)].d < t[rs(x)].d) swap(ls(x), rs(x));
  28.     t[x].d = t[rs(x)].d + 1;
  29.     return x;
  30. }
  31. int pop(int x) {
  32.     pushdown(x);
  33.     return merge(t[x].ch[0], t[x].ch[1]);
  34. }
  35. int findrt(int u) {return u == t[u].rt ? u : t[u].rt = findrt(t[u].rt);}
  37. int main() {
  38.     return 0;
  39. }

li-chao-tree.cpp - DS

  1. // 李超线段树 luogu-P4097 [HEOI2013]Segment
  2. #include <bits/stdc++.h>
  3. #define ls (x<<1)
  4. #define rs (x<<1|1)
  5. template<typename _Tp>
  6. inline void red(_Tp &x) {
  7.     x = 0; bool fg = 0; char ch = getchar();
  8.     while (ch < '0' || ch > '9') {if (ch == '-') fg ^= 1; ch = getchar();}
  9.     while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (_Tp)(ch ^ 48), ch = getchar();
  10.     if (fg) x = -x;
  11. }
  12. using namespace std;
  13. typedef long long ll;
  14. typedef double db;
  15. const int N = 100010;
  16. const int M = 40000;
  17. struct line {
  18.     db k, b;
  19. } lin[N];
  20. db val(int id, db X) {return lin[id].k * X + lin[id].b;}
  21. int D[N << 2], n, id;
  22. void modify(int L, int R, int id, int l = 1, int r = M - 1, int x = 1) {
  23.     if (L <= l && r <= R) {
  24.         int mid = (l + r) >> 1, lid = D[x];
  25.         db lst = val(D[x], mid), now = val(id, mid);
  26.         if (l == r) {if (now > lst) D[x] = id; return ;}
  27.         if (lin[id].k > lin[D[x]].k) {
  28.             if (now > lst) D[x] = id, modify(L, R, lid, l, mid, ls); // id->lid
  29.             else modify(L, R, id, mid + 1, r, rs);
  30.         } else if (lin[id].k < lin[D[x]].k) {
  31.             if (now > lst) D[x] = id, modify(L, R, lid, mid + 1, r, rs); // id->lid
  32.             else modify(L, R, id, l, mid, ls);
  33.         } else if (lin[id].b > lin[D[x]].k) D[x] = id;
  34.         return ;
  35.     }
  36.     int mid = (l + r) >> 1;
  37.     if (L <= mid) modify(L, R, id, l, mid, x << 1);
  38.     if (R > mid) modify(L, R, id, mid + 1, r, x << 1 | 1);
  39. }
  40. int gmax(int x, int y, int ps) {
  41.     if (val(x, ps) > val(y, ps)) return x;
  42.     if (val(x, ps) < val(y, ps)) return y;
  43.     return (x < y) ? x : y;
  44. }
  45. int query(int ps, int l = 1, int r = M - 1, int x = 1) {
  46.     if (l == r) return D[x];
  47.     int mid = (l + r) >> 1, ret = D[x], t = 0;
  48.     if (ps <= mid)
  49.         t = query(ps, l, mid, ls);
  51.     else
  52.         t = query(ps, mid + 1, r, rs);
  53.     return gmax(ret, t, ps);
  54. }
  55. int main() {
  56.     red(n);
  57.     int lstans = 0, tot = 0;
  58.     for (int i = 1; i <= n; ++i) {
  59.         int op; red(op);
  60.         if (op == 0) {
  61.             ++tot; int k; red(k); // 询问 x=k 最大交点
  62.             k = (k + lstans - 1) % 39989 + 1;
  63.             lstans = query(k);
  64.             printf("%d\n", lstans);
  65.         } else {
  66.             int x0, y0, x1, y1; ++id; // 添加线段
  67.             red(x0); red(y0); red(x1); red(y1);
  68.             x0 = (x0 + lstans - 1) % 39989 + 1; x1 = (x1 + lstans - 1) % 39989 + 1;
  69.             y0 = (y0 + lstans - 1) % (int)(1e9) + 1; y1 = (y1 + lstans - 1) % (int)(1e9) + 1;
  70.             if (x0 > x1) swap(x0, x1), swap(y0, y1);
  71.             if (x0 == x1) {
  72.                 lin[id].k = 0; lin[id].b = max(y1, y0);
  73.             } else {
  74.                 lin[id].k = (db)(y1 - y0) / (db)(x1 - x0);
  75.                 lin[id].b = (db)y1 - lin[id].k * (db)x1;
  76.             }
  77.             modify(x0, x1, id);
  78.         }
  79.     }
  80.     return 0;
  81. }

pbds_heap.cpp - DS

  1. /*
  2. __gnu_pbds :: priority_queue 堆 使用指南
  3. ========================================================================================================
  4. __gnu_pbds ::priority_queue<_Tv, Cmp_Fn = std::less<_Tv>, Tag = pairing_heap_tag,
  5.                            Allocator = std::allocator<char> >
  7. _Tv:          储存的元素类型
  8. Cmp_Fn:       比较函子，默认 std::less<_Tv> 为大根堆
  9. Tag:          堆的类型（默认且建议 pairing_heap_tag）
  10. Allocator:    空间分配器类型（不用改）
  12. push(),pop(),top(),size(),empty() 与 std::priority_queue 类似
  13. join(other)         将 other 加入当前堆，other 堆被删除（前提是两棵树的类型一样）
  14. modify(it, key)     修改迭代器 it 所指的 key，并对底层储存结构进行排序
  15. erase(it)           把迭代器 it 位置的键值从堆中擦除
  16. begin(),end()       返回可以用来遍历的迭代器，不保证有序！且只要进行过修改操作就会变
  17. ========================================================================================================
  18. */
  19. #include <bits/stdc++.h>
  20. #include <ext/pb_ds/priority_queue.hpp>
  21. using namespace std;
  22. const int N = 100010;
  23. __gnu_pbds::priority_queue<pair<int, int>, greater<pair<int, int>>> Q[N];
  24. // 以下是用 pb_ds::tree 实现的 【模板】左偏树（可并堆） https://www.luogu.com.cn/problem/P3377
  25. int fa[N], n, m;
  26. bool del[N];
  27. int find(int u) { 
  28.     return fa[u] == u ? u : fa[u] = find(fa[u]);
  29. }
  30. int main() {
  31.     scanf("%d%d", &n, &m);
  32.     for (int i = 1; i <= n; ++i) {
  33.         int x; scanf("%d", &x);
  34.         fa[i] = i, Q[i].push({x, i});
  35.     }
  36.     while (m--) {
  37.         int op, x, y;
  38.         scanf("%d", &op);
  39.         if (op == 1) {
  40.             scanf("%d%d", &x, &y);
  41.             if (del[x] || del[y]) continue;
  42.             x = find(x), y = find(y);
  43.             if (x != y) {
  44.                 fa[x] = y;
  45.                 Q[y].join(Q[x]);
  46.             }
  47.         } else {
  48.             scanf("%d", &x);
  49.             if (del[x]) {
  50.                 puts("-1");
  51.                 continue;
  52.             }
  53.             x = find(x);
  54.             printf("%d\n", Q[x].top().first);
  55.             del[Q[x].top().second] = 1;
  56.             Q[x].pop();
  57.         }
  58.     }
  59. }

pbds_tree.cpp - DS

  1. /*
  2. __gnu_pbds :: tree 平衡树 使用指南
  3. ========================================================================================================
  4. __gnu_pbds ::tree<Key, Mapped, Cmp_Fn = std::less<Key>, Tag = rb_tree_tag,
  5.                   Node_Update = null_tree_node_update,
  6.                   Allocator = std::allocator<char> >
  8. Key:          储存的元素类型
  9. Mapped:       填 null_type 当成 std::set， 填其他类型当成 std::map
  10. Cmp_Fn:       比较函子
  11. Tag:          树的类型（建议 rb_tree_tag）
  12. Node_Update:  更新节点的策略，默认是 null_tree_node_update
  13.               使用 tree_order_statistics_node_update 来允许 order_of_key，find_by_order 方法
  14. Allocator:    空间分配器类型（不用改）
  16. insert(),erase(),lower_bound(),upper_bound(),find(),empty(),size(),begin(),end() 与 std::set 类似
  17. join(other)         将 other 加入当前树，other 树被删除（前提是两棵树的类型一样）
  18. split(val, other)   以 Cmp_Fn 比较，小于等于 val 的属于当前树，其余的属于 other 树
  19. order_of_key(x)     返回 x 以 Cmp_Fn 比较的排名（从 0 开始）
  20. find_by_order(x)    返回 Cmp_Fn 比较的排名所对应元素的迭代器 （从 0 开始）
  21. ========================================================================================================
  22. */
  23. #include <bits/stdc++.h>
  24. #include <ext/pb_ds/assoc_container.hpp>
  25. #include <ext/pb_ds/tree_policy.hpp>
  26. using namespace std;
  27. __gnu_pbds::tree<std::pair<int, int>, __gnu_pbds::null_type, std::less<std::pair<int, int>>,
  28.     __gnu_pbds::rb_tree_tag,
  29.     __gnu_pbds::tree_order_statistics_node_update> T;
  31. // 以下是用 pb_ds::tree 实现的 【模板】普通平衡树 https://www.luogu.com.cn/problem/P3369
  32. int Q;
  33. int main() {
  34.     scanf("%d", &Q);
  35.     while (Q--) {
  36.         int opt, x; scanf("%d%d", &opt, &x);
  37.         switch (opt) {
  38.         case 1: {
  39.             auto it = T.lower_bound({x + 1, 0});
  40.             if (it != T.begin() && (--it)->first != x) T.insert({x, 1});
  41.             else T.insert({x, it->second + 1});
  42.             break;
  43.         }
  44.         case 2: {
  45.             auto it1 = --T.lower_bound({x + 1, 0});
  46.             T.erase(it1);
  47.             break;
  48.         }
  49.         case 3: {
  50.             int rk = T.order_of_key({x, 1});
  51.             printf("%d\n", rk + 1);
  52.             break;
  53.         }
  54.         case 4: {
  55.             auto it = T.find_by_order(x - 1);
  56.             printf("%d\n", it->first);
  57.             break;
  58.         }
  59.         case 5: {
  60.             auto it = --T.lower_bound({x, 0});
  61.             printf("%d\n", it->first);
  62.             break;
  63.         }
  64.         case 6: {
  65.             auto it = T.lower_bound({x + 1, 0});
  66.             printf("%d\n", it->first);
  67.             break;
  68.         }
  69.         default:
  70.             break;
  71.         }
  72.         // for (auto i : T) {
  73.         //     printf("%d[%d] ", i.first, i.second);    
  74.         // }
  75.         // puts("");
  76.     }      
  77.     return 0;
  78. }

pds_array.cpp - DS

  1. // 可持久化数组
  2. #include <cstdio>
  3. #define ls(p) tr[p].lc
  4. #define rs(p) tr[p].rc
  5. #define re register
  6. template <typename T>
  7. inline void red(T &x) {
  8.     x = 0; bool f = 0; char ch = getchar();
  9.     while (ch < '0' || ch > '9') {if (ch == '-') f ^= 1; ch = getchar();}
  10.     while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (T)(ch ^ 48), ch = getchar();
  11.     if (f) x = -x;
  12. }
  13. using namespace std;
  14. const int N = 1000010;
  15. struct node {
  16.     int lc, rc, val;
  17. } tr[N * 21]; int tot;
  18. int root[N];
  19. int n, m, a[N];
  20. int newnode() {
  21.     tr[++tot] = {0, 0, 0};
  22.     return tot;
  23. }
  24. void build(int p, int l = 1, int r = n) {
  25.     if (l == r) return tr[p].val = a[l], void();
  26.     int mid = (l + r) >> 1;
  27.     build(ls(p) = newnode(), l, mid);
  28.     build(rs(p) = newnode(), mid + 1, r);
  29. }
  30. void modify(int p, int q, int pos, int val, int l = 1, int r = n) {
  31.     if (l == r) return tr[q].val = val, void();
  32.     int mid = (l + r) >> 1;
  33.     if (pos <= mid) {
  34.         modify(ls(p), ls(q) = newnode(), pos, val, l, mid);
  35.         rs(q) = rs(p);
  36.     } else {
  37.         modify(rs(p), rs(q) = newnode(), pos, val, mid + 1, r);
  38.         ls(q) = ls(p);
  39.     }
  40. }
  41. int query(int p, int pos, int l = 1, int r = n) {
  42.     if (l == r) return tr[p].val;
  43.     int mid = (l + r) >> 1;
  44.     if (pos <= mid) return query(ls(p), pos, l, mid);
  45.     else return query(rs(p), pos, mid + 1, r);
  46. }
  47. int main() {
  48.     red(n); red(m);
  49.     for (re int i = 1; i <= n; ++i) red(a[i]);
  50.     root[0] = newnode(); build(root[0]);
  51.     for (re int i = 1; i <= m; ++i) {
  52.         re int v, op, loc, vl;
  53.         red(v); red(op); red(loc);
  54.         if (op == 1) {
  55.             red(vl);
  56.             modify(root[v], root[i] = newnode(), loc, vl);
  57.         } else {
  58.             printf("%d\n", query(root[v], loc));
  59.             root[i] = root[v];
  60.         }
  61.     }
  62. }

pds_dsu.cpp - DS

  1. #include <cstdio>
  2. #include <iostream>
  3. #define ls(p) tr[p].lc
  4. #define rs(p) tr[p].rc
  5. #define re register
  6. using namespace std;
  7. const int N = 200010;
  8. struct node {
  9.     int lc, rc, val, siz;
  10. } tr[N * 41];
  11. int root[N], tot;
  12. int n, m;
  13. int newnode() {
  14.     tr[++tot] = {0, 0, 0};
  15.     return tot;
  16. }
  17. void build(int p, int l = 1, int r = n) {
  18.     if (l == r) return tr[p].val = l, tr[p].siz = 1, void();
  19.     int mid = (l + r) >> 1;
  20.     build(ls(p) = newnode(), l, mid);
  21.     build(rs(p) = newnode(), mid + 1, r);
  22. }
  23. void modify_fa(int p, int q, int pos, int val, int l = 1, int r = n) {
  24.     if (l == r) return tr[q].val = val, tr[q].siz = tr[p].siz, void();
  25.     int mid = (l + r) >> 1;
  26.     if (pos <= mid) {
  27.         modify_fa(ls(p), ls(q) ? ls(q) : ls(q) = newnode(), pos, val, l, mid);
  28.         if (rs(q) == 0)rs(q) = rs(p);
  29.     } else {modify_fa(rs(p), rs(q) ? rs(q) : rs(q) = newnode(), pos, val, mid + 1, r); if (ls(q) == 0)ls(q) = ls(p);}
  30. }
  31. void modify_dep(int p, int q, int pos, int siz, int l = 1, int r = n) {
  32.     if (l == r) return tr[q].siz = siz, tr[q].val = tr[p].val, void();
  33.     int mid = (l + r) >> 1;
  34.     if (pos <= mid) {
  35.         modify_dep(ls(p), ls(q) ? ls(q) : ls(q) = newnode(), pos, siz, l, mid);
  36.         if (rs(q) == 0)rs(q) = rs(p);
  37.     } else {modify_dep(rs(p), rs(q) ? rs(q) : rs(q) = newnode(), pos, siz, mid + 1, r); if (ls(q) == 0)ls(q) = ls(p);}
  38. }
  39. // return the node number
  40. int query(int p, int pos, int l = 1, int r = n) {
  41.     if (l == r) return p;
  42.     int mid = (l + r) >> 1;
  43.     if (pos <= mid) return query(ls(p), pos, l, mid);
  44.     else return query(rs(p), pos, mid + 1, r);
  45. }
  46. int find(int rt, int u) {
  47.     int pa = query(rt, u);
  48.     if (tr[pa].val == u) return u;
  49.     return find(rt, tr[pa].val);
  50. }
  51. int main() {
  52.     scanf("%d%d", &n, &m);
  53.     root[0] = newnode(); build(root[0]);
  54.     for (re int i = 1; i <= m; ++i) {
  55.         re int opt, a, b;
  56.         scanf("%d%d", &opt, &a);
  57.         if (opt == 1) { // 合并 a,b
  58.             scanf("%d", &b);
  59.             root[i] = newnode();
  60.             int f1 = find(root[i - 1], a), f2 = find(root[i - 1], b);
  61.             int sz1 = tr[query(root[i - 1], f1)].siz, sz2 = tr[query(root[i - 1], f2)].siz;
  62.             if (f1 != f2) {
  63.                 if (sz1 > sz2) swap(f1, f2), swap(sz1, sz2);
  64.                 modify_fa(root[i - 1], root[i], f1, f2);
  65.                 modify_dep(root[i - 1], root[i], f2, sz1 + sz2);
  66.             } else
  67.                 root[i] = root[i - 1];
  68.         }
  69.         if (opt == 2) // 回到状态 a
  70.             root[i] = root[a];
  71.         if (opt == 3) { // 询问 a,b 是否在同一集合
  72.             scanf("%d", &b);
  73.             root[i] = root[i - 1];
  74.             int f1 = find(root[i], a), f2 = find(root[i], b);
  75.             printf("%d\n", f1 == f2);
  76.         }
  77.     }
  78.     return 0;
  79. }

pds_segtree.cpp - DS

  1. // 主席树，区间第 k 大
  2. #include <cstdio>
  3. #include <algorithm>
  4. #define ls(p) tr[p].lc
  5. #define rs(p) tr[p].rc
  6. #define re register
  7. template <typename T>
  8. inline void red(T &x) {
  9.     x = 0; bool f = 0; char ch = getchar();
  10.     while (ch < '0' || ch > '9') {if (ch == '-') f ^= 1; ch = getchar();}
  11.     while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (T)(ch ^ 48), ch = getchar();
  12.     if (f) x = -x;
  13. }
  14. using namespace std;
  15. const int N = 200010;
  16. struct node {
  17.     int cnt, lc, rc;
  18. } tr[N * 18]; int root[N], tot;
  19. int a[N], b[N], tt, n, q;
  20. int newnode() { tr[++tot] = {0, 0, 0}; return tot;}
  21. void pushup(int p) {tr[p].cnt = tr[ls(p)].cnt + tr[rs(p)].cnt;}
  22. void modify(int p, int q, int val, int l = 1, int r = tt) {
  23.     if (l == r) return (p == 0) ? tr[q].cnt = 1 : tr[q].cnt = tr[p].cnt + 1, void();
  24.     int mid = (l + r) >> 1;
  25.     if (val <= mid) {
  26.         modify(ls(p), ls(q) = newnode(), val, l, mid);
  27.         rs(q) = rs(p);
  28.     } else {
  29.         modify(rs(p), rs(q) = newnode(), val, mid + 1, r);
  30.         ls(q) = ls(p);
  31.     }
  32.     pushup(q);
  33. }
  34. int query(int p, int q, int k, int l = 1, int r = tt) {
  35.     if (l == r) return b[l];
  36.     int mid = (l + r) >> 1, t = tr[ls(q)].cnt - tr[ls(p)].cnt;
  37.     return (k <= t) ? query(ls(p), ls(q), k, l, mid) : query(rs(p), rs(q), k - t, mid + 1, r);
  38. }
  39. int main() {
  40.     red(n); red(q);
  41.     for (re int i = 1; i <= n; ++i) red(a[i]), b[i] = a[i];
  42.     sort(b + 1, b + n + 1);
  43.     tt = unique(b + 1, b + n + 1) - b - 1;
  44.     for (re int i = 1; i <= n; ++i) a[i] = lower_bound(b + 1, b + tt + 1, a[i]) - b;
  45.     root[0] = newnode();
  46.     for (re int i = 1; i <= n; ++i) {
  47.         root[i] = newnode();
  48.         modify(root[i - 1], root[i], a[i]);
  49.     }
  50.     for (re int i = 1; i <= q; ++i) {
  51.         re int l, r, k; red(l); red(r); red(k);
  52.         printf("%d\n", query(root[l - 1], root[r], k));
  53.     }
  54.     return 0;
  55. }

RMQ.cpp - DS

  1. // 期望 O(n)-O(1) RMQ
  2. // luogu P3793 由乃救爷爷
  3. #include <cstdio>
  4. #define re register
  5. // -------------- ReadIN ----------------
  6. namespace GenHelper {
  7.     unsigned z1, z2, z3, z4, b;
  8.     unsigned rand_() {
  9.         b = ((z1 << 6)^z1) >> 13;
  10.         z1 = ((z1 & 4294967294U) << 18)^b;
  11.         b = ((z2 << 2)^z2) >> 27;
  12.         z2 = ((z2 & 4294967288U) << 2)^b;
  13.         b = ((z3 << 13)^z3) >> 21;
  14.         z3 = ((z3 & 4294967280U) << 7)^b;
  15.         b = ((z4 << 3)^z4) >> 12;
  16.         z4 = ((z4 & 4294967168U) << 13)^b;
  17.         return (z1 ^ z2 ^ z3 ^ z4);
  18.     }
  19. }
  20. void srand(unsigned x) {using namespace GenHelper; z1 = x; z2 = (~x) ^ 0x233333333U; z3 = x ^ 0x1234598766U; z4 = (~x) + 51;}
  21. int read() {
  22.     using namespace GenHelper;
  23.     int a = rand_() & 32767;
  24.     int b = rand_() & 32767;
  25.     return a * 32768 + b;
  26. }
  27. // ----------- END ReadIN -------------
  29. typedef unsigned long long ull;
  30. int n, m, s;
  31. // ------------ BEGIN RMQ -------------
  32. const int N = 20000010;
  33. int a[N];
  34. namespace RMQ {
  35.     inline int gmax(int x, int y) {return a[x] > a[y] ? x : y;}
  36.     const int B = 4434; // B 大概取 log2(n) or sqrt(n) ??  怕被卡的话随机微调块长
  37.     const int M = 16;
  38.     int bl[N], F[M][N / B + 10], ps[N], pre[N], suf[N], LOG[N], tot;
  39.     // bl 属于哪个块，F 块间ST表 ps块内最值下标 pre/suf 块内前缀/后缀最值
  40.     void init() {
  41.         for (re int i = 1; i <= n; ++i) bl[i] = (i - 1) / B + 1;
  42.         for (re int i = 1; i <= n;
  43.              ++i)(bl[i] != bl[i - 1]) ? (pre[i] = i, ps[bl[i - 1]] = pre[i - 1]) : (pre[i] = gmax(pre[i - 1], i));
  44.         for (re int i = 1, j = B; j <= n; ++i, j += B) ps[i] = pre[j];
  45.         tot = bl[n]; ps[tot] = pre[n];
  46.         for (re int i = n; i >= 1; --i)(bl[i] != bl[i + 1]) ? (suf[i] = i) : (suf[i] = gmax(suf[i + 1], i));
  47.         LOG[0] = -1;
  48.         for (re int i = 1; i <= tot; ++i) LOG[i] = LOG[i >> 1] + 1;
  49.         for (re int i = 1; i <= tot; ++i) F[0][i] = ps[i];
  50.         for (re int j = 1; j <= LOG[tot]; ++j) {
  51.             for (re int i = 1; i <= tot; ++i) {
  52.                 if (i + (1 << j) - 1 > tot) break;
  53.                 F[j][i] = gmax(F[j - 1][i], F[j - 1][i + (1 << (j - 1))]);
  54.             }
  55.         }
  56.     }
  57.     inline int ask(int l, int r) { // 返回区间最值位置
  58.         if (bl[l] == bl[r]) {
  59.             int p = l;
  60.             for (re int i = l + 1; i <= r; ++i) p = gmax(p, i);
  61.             return p;
  62.         }
  63.         if (bl[l] + 1 == bl[r]) return gmax(suf[l], pre[r]);
  64.         int L = bl[l] + 1, R = bl[r] - 1;
  65.         int k = LOG[R - L + 1];
  66.         return gmax(gmax(F[k][L], F[k][R - (1 << k) + 1]), gmax(suf[l], pre[r]));
  67.     }
  68. }
  69. // -------------- END RMQ --------------
  70. inline void swap(int &l, int &r) {l ^= r; r ^= l; l ^= r;}
  71. int main() {
  72.     scanf("%d%d%d", &n, &m, &s);
  73.     srand(s);
  74.     for (re int i = 1; i <= n; ++i) a[i] = read();
  75.     RMQ::init();
  76.     ull ANS = 0;
  77.     for (re int i = 1, l, r; i <= m; ++i) {
  78.         l = read() % n + 1, r = read() % n + 1;
  79.         (l > r) &&(swap(l, r), 1);
  80.         ANS += a[RMQ::ask(l, r)];
  81.     }
  82.     printf("%llu\n", ANS);
  83. }

seg-beats.cpp - DS

  1. /*
  2.  * seg-beats 吉司机线段树
  3.  * 区间最值操作
  4.  * 支持 区间取min，区间取max，区间加减，区间求和，区间最小/大
  5.  * 复杂度 O(m log n)
  6.  */
  8. #include <bits/stdc++.h>
  9. #define ls (x << 1)
  10. #define rs (x << 1 | 1)
  11. #define mid ((l + r) >> 1)
  12. template <typename Tp>
  13. inline void read(Tp &x) {
  14.     x = 0; bool fg = 0; char ch = getchar();
  15.     while (ch < '0' || ch > '9') { if (ch == '-') fg ^= 1; ch = getchar(); }
  16.     while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (Tp)(ch ^ 48), ch = getchar();
  17.     if (fg) x = -x;
  18. }
  19. template <typename Tp, typename... Args>
  20. void read(Tp &t, Args &...args) { read(t); read(args...); }
  21. template <typename Tp>
  22. inline void write(Tp x, char ch = '\n') {
  23.     static char buf[128]; int tot = 0;
  24.     if (x < 0) x = -x, putchar('-');
  25.     while (x) buf[tot++] = '0' + x % 10, x /= 10;
  26.     if (tot == 0) putchar('0');
  27.     while (tot--) putchar(buf[tot]);
  28.     if (ch) putchar(ch);
  29. }
  30. using namespace std;
  31. typedef long long ll;
  32. const int N = 500010;
  33. const int inf = 0x3f3f3f3f;
  34. struct datmn {
  35.     int fi, se, cnt;
  36.     datmn() {fi = se = inf; cnt = 0;}
  37.     void ins(int x, int c) {
  38.         if (x < fi) se = fi, cnt = c, fi = x;
  39.         else if (x == fi) cnt += c;
  40.         else if (x < se) se = x;
  41.     }
  42.     friend datmn operator+(const datmn &a, const datmn &b) {
  43.         datmn r = a; r.ins(b.fi, b.cnt); r.ins(b.se, 0); return r;
  44.     }
  45. };
  46. struct datmx {
  47.     int fi, se, cnt;
  48.     datmx() {fi = se = -inf; cnt = 0;}
  49.     void ins(int x, int c) {
  50.         if (x > fi) se = fi, cnt = c, fi = x;
  51.         else if (x == fi) cnt += c;
  52.         else if (x > se) se = x;
  53.     }
  54.     friend datmx operator+(const datmx &a, const datmx &b) {
  55.         datmx r = a; r.ins(b.fi, b.cnt); r.ins(b.se, 0); return r;
  56.     }
  57. };
  59. struct node {
  60.     datmn mn; datmx
  61.     mx; // mn: (最小值，严格次小值，最小值个数) , mx: (最大值，严格次大值，最大值个数)
  62.     ll sum; int addmn, addmx, add,
  63.     len; // sum 区间和，addmn 最小值lazytag，addmx 最大值lazytag，add 其他数 lazytag，len 区间长度
  64. } t[N << 2];
  65. // ostream &operator<<(ostream& out, const datmx &d) {
  66. //     return out << "dat{ " << d.fi << " (" << d.cnt << ") ," << d.se << " } ";
  67. // }
  68. // ostream &operator<<(ostream& out, const datmn &d) {
  69. //     return out << "dat{ " << d.fi << " (" << d.cnt << ") ," << d.se << " } ";
  70. // }
  71. // ostream &operator<<(ostream& out, const node &d) {
  72. //     return out << "mn" << d.mn << "mx" << d.mx << " sum=" << d.sum << " addmn=" << d.addmn << " addmx=" << d.addmx << " add=" << d.add << " ";
  73. // }
  74. int n, m, a[N];
  75. void pushup(int x) {
  76.     t[x].mx = t[ls].mx + t[rs].mx;
  77.     t[x].mn = t[ls].mn + t[rs].mn;
  78.     t[x].sum = t[ls].sum + t[rs].sum;
  79. }
  80. void build(int l = 1, int r = n, int x = 1) {
  81.     t[x].add = t[x].addmn = t[x].addmx = 0;
  82.     t[x].len = r - l + 1;
  83.     if (l == r) {
  84.         t[x].mx = datmx(); t[x].mx.ins(a[l], 1);
  85.         t[x].mn = datmn(); t[x].mn.ins(a[l], 1);
  86.         t[x].sum = a[l];
  87.         return;
  88.     }
  89.     build(l, mid, ls); build(mid + 1, r, rs);
  90.     pushup(x);
  91. }
  92. void update(int x, int vn, int vx, int v) { // vn: addmn, vx: addmx, v: add
  93.     if (t[x].mn.fi ==
  94.         t[x].mx.fi) { // 所有数相同特判，此时最大值 tag 和最小值 tag 应该相同且不等于其他值 tag
  95.         if (vn == v) vn = vx;
  96.         else vx = vn;
  97.         t[x].sum += (ll)vn * t[x].mn.cnt;
  98.     } else t[x].sum += (ll)vn * t[x].mn.cnt + (ll) vx * t[x].mx.cnt + (ll)v * (t[x].len - t[x].mn.cnt -
  99.                            t[x].mx.cnt);
  100.     if (t[x].mn.se == t[x].mx.fi) t[x].mn.se += vx; // 次小值 = 最大值，应该用最大值 tag 处理
  101.     else if (t[x].mn.se != inf) t[x].mn.se += v;
  102.     if (t[x].mx.se == t[x].mn.fi) t[x].mx.se += vn; // 次大值同理
  103.     else if (t[x].mx.se != -inf) t[x].mx.se += v;
  104.     t[x].mn.fi += vn; t[x].mx.fi += vx;
  105.     t[x].addmn += vn; t[x].addmx += vx; t[x].add += v;
  106. }
  107. void pushdown(int x) {
  108.     int mn = min(t[ls].mn.fi, t[rs].mn.fi);
  109.     int mx = max(t[ls].mx.fi, t[rs].mx.fi);
  110.     update(ls, (mn == t[ls].mn.fi) ? t[x].addmn : t[x].add, (mx == t[ls].mx.fi) ? t[x].addmx : t[x].add,
  111.            t[x].add);
  112.     update(rs, (mn == t[rs].mn.fi) ? t[x].addmn : t[x].add, (mx == t[rs].mx.fi) ? t[x].addmx : t[x].add,
  113.            t[x].add);
  114.     t[x].add = t[x].addmn = t[x].addmx = 0;
  115. }
  117. void modifyadd(int L, int R, int v, int l = 1, int r = n, int x = 1) {
  118.     if (r < L || R < l) return ;
  119.     if (L <= l && r <= R) return update(x, v, v, v);
  120.     pushdown(x);
  121.     modifyadd(L, R, v, l, mid, ls);
  122.     modifyadd(L, R, v, mid + 1, r, rs);
  123.     pushup(x);
  124. }
  125. void modifymin(int L, int R, int v, int l = 1, int r = n, int x = 1) {
  126.     if (r < L || R < l) return ;
  127.     if (L <= l && r <= R && v > t[x].mx.se) {
  128.         if (v >= t[x].mx.fi) return ;
  129.         update(x, 0, v - t[x].mx.fi, 0);
  130.         return;
  131.     }
  132.     pushdown(x);
  133.     modifymin(L, R, v, l, mid, ls);
  134.     modifymin(L, R, v, mid + 1, r, rs);
  135.     pushup(x);
  136. }
  137. void modifymax(int L, int R, int v, int l = 1, int r = n, int x = 1) {
  138.     if (r < L || R < l) return ;
  139.     if (L <= l && r <= R && v < t[x].mn.se) {
  140.         if (v <= t[x].mn.fi) return;
  141.         update(x, v - t[x].mn.fi, 0, 0);
  142.         return;
  143.     }
  144.     pushdown(x);
  145.     modifymax(L, R, v, l, mid, ls);
  146.     modifymax(L, R, v, mid + 1, r, rs);
  147.     pushup(x);
  148. }
  149. int querymax(int L, int R, int l = 1, int r = n, int x = 1) {
  150.     if (r < L || R < l) return -inf;
  151.     if (L <= l && r <= R) return t[x].mx.fi;
  152.     pushdown(x);
  153.     return max(querymax(L, R, l, mid, ls), querymax(L, R, mid + 1, r, rs));
  154. }
  155. int querymin(int L, int R, int l = 1, int r = n, int x = 1) {
  156.     if (r < L || R < l) return inf;
  157.     if (L <= l && r <= R) return t[x].mn.fi;
  158.     pushdown(x);
  159.     return min(querymin(L, R, l, mid, ls), querymin(L, R, mid + 1, r, rs));
  160. }
  161. ll querysum(int L, int R, int l = 1, int r = n, int x = 1) {
  162.     if (r < L || R < l) return 0;
  163.     if (L <= l && r <= R) return t[x].sum;
  164.     pushdown(x);
  165.     return querysum(L, R, l, mid, ls) + querysum(L, R, mid + 1, r, rs);
  166. }
  167. void print(int l = 1, int r = n, int x = 1) {
  168.     if (l == r) {
  169.         cerr << t[x].sum << " ";
  170.         return ;
  171.     }
  172.     pushdown(x);
  173.     print(l, mid, ls);
  174.     print(mid + 1, r, rs);
  175. }
  176. signed main() {
  177.     read(n);
  178.     for (int i = 1; i <= n; ++i) read(a[i]);
  179.     build();
  180.     read(m);
  181.     for (int i = 1; i <= m; ++i) {
  182.         int op, l, r, x;
  183.         read(op, l, r);
  184.         if (op <= 3) read(x);
  185.         switch (op) {
  186.         case 1:
  187.             modifyadd(l, r, x);
  188.             break;
  189.         case 2:
  190.             modifymax(l, r, x);
  191.             break;
  192.         case 3:
  193.             modifymin(l, r, x);
  194.             break;
  195.         case 4:
  196.             write(querysum(l, r));
  197.             break;
  198.         case 5:
  199.             write(querymax(l, r));
  200.             break;
  201.         case 6:
  202.             write(querymin(l, r));
  203.             break;
  204.         }
  205.     }
  206.     return 0;
  207. }

seg-in-seg.cpp - DS

  1. // 线段树套主席树
  2. #include <bits/stdc++.h>
  3. #define ls(p) t[p].l
  4. #define rs(p) t[p].r
  5. #define lc (x << 1)
  6. #define rc (x << 1 | 1)
  7. #define mid ((l + r) >> 1)
  8. using namespace std;
  9. template <typename Tp> void read(Tp &x) {
  10.     x = 0; char ch = getchar(); int f = 0;
  11.     while (ch < '0' || ch > '9') { if (ch == '-') f ^= 1; ch = getchar(); }
  12.     while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (Tp)(ch ^ 48), ch = getchar();
  13.     if (f) x = -x;
  14. }
  15. template <typename Tp, typename... Args>
  16. void read(Tp &t, Args &... args) { read(t); read(args...); }
  18. const int N = 50010;
  19. const int INF = 2147483647;
  20. const int MAX = 1e8;
  21. const int MIN = -1e8;
  23. int n, m, a[N];
  24. struct node {
  25.     int l, r, sum;
  26. } t[N * 450];
  27. int rt[N << 2], tot;
  29. int newnode() {
  30.     t[++tot] = { 0, 0, 0 };
  31.     return tot;
  32. }
  34. void modify(int &p, int val, int cnt, int l = MIN, int r = MAX) {
  35.     if (!p) p = newnode();
  36.     if (l == r) return t[p].sum += cnt, void();
  37.     if (val <= mid) modify(ls(p), val, cnt, l, mid);
  38.     else modify(rs(p), val, cnt, mid + 1, r);
  39.     t[p].sum = t[ls(p)].sum + t[rs(p)].sum;
  40. }
  42. int query(int p, int L, int R, int l = MIN, int r = MAX) {
  43.     if (!p || L > R) return 0;
  44.     if (L <= l && r <= R) return t[p].sum;
  45.     if (L <= mid && R > mid) return query(ls(p), L, R, l, mid) + query(rs(p), L, R, mid + 1, r);
  46.     return (L <= mid) ? query(ls(p), L, R, l, mid) : query(rs(p), L, R, mid + 1, r);
  47. }
  49. void Build(int l = 1, int r = n, int x = 1) {
  50.     for (int i = l; i <= r; ++i) modify(rt[x], a[i], 1);
  51.     if (l == r) return ;
  52.     Build(l, mid, lc);
  53.     Build(mid + 1, r, rc);
  54. }
  56. // 返回 [L, R] 中 <= k 的个数
  57. int Rank(int L, int R, int k, int l = 1, int r = n, int x = 1) {
  58.     if (L <= l && r <= R) return query(rt[x], 0, k);
  59.     int ret = 0;
  60.     if (L <= mid) ret = Rank(L, R, k, l, mid, lc);
  61.     if (R > mid) ret += Rank(L, R, k, mid + 1, r, rc);
  62.     return ret;
  63. }
  65. vector<int> nods;
  66. void work(int L, int R, int l = 1, int r = n, int x = 1) {
  67.     if (L <= l && r <= R) return nods.push_back(rt[x]);
  68.     if (L <= mid) work(L, R, l, mid, lc);
  69.     if (R > mid) work(L, R, mid + 1, r, rc);
  70. }
  72. // 返回 [L, R] 中排名第 k 的数，不合法则 -INF
  73. int Kth(int L, int R, int k) {
  74.     if (k <= 0 || k > R - L + 1) return -INF;
  75.     nods.clear();
  76.     work(L, R);
  77.     int l = MIN, r = MAX, cnt;
  78.     while (l < r) {
  79.         cnt = 0;
  80.         for (int i = 0; i < (int)nods.size(); ++i) cnt += t[ls(nods[i])].sum;
  81.         if (cnt >= k) {
  82.             for (int i = 0; i < (int)nods.size(); ++i) nods[i] = ls(nods[i]);
  83.             r = mid;
  84.         } else {
  85.             for (int i = 0; i < (int)nods.size(); ++i) nods[i] = rs(nods[i]);
  86.             l = mid + 1;
  87.             k -= cnt;
  88.         }
  89.     }
  90.     return l;
  91. }
  93. void Modify(int pos, int lst, int val, int l = 1, int r = n, int x = 1) {
  94.     modify(rt[x], lst, -1);
  95.     modify(rt[x], val, 1);
  96.     if (l == r) return ;
  97.     if (pos <= mid) Modify(pos, lst, val, l, mid, lc);
  98.     else Modify(pos, lst, val, mid + 1, r, rc);
  99. }
  102. int main() {
  103.     read(n, m);
  104.     for (int i = 1; i <= n; ++i) read(a[i]);
  105.     Build();
  106.     for (int cs = 1; cs <= m; ++cs) {
  107.         int op, x, y, z, k;
  108.         read(op, x, y);
  109.         switch (op) {
  110.         case 1:
  111.             read(z);
  112.             printf("%d\n", Rank(x, y, z - 1) + 1);
  113.             break;
  114.         case 2:
  115.             read(z);
  116.             printf("%d\n", Kth(x, y, z));
  117.             break;
  118.         case 3:
  119.             Modify(x, a[x], y); a[x] = y;
  120.             break;
  121.         case 4:
  122.             read(z);
  123.             k = Kth(x, y, Rank(x, y, z - 1));
  124.             printf("%d\n", k == -INF ? -INF : k);
  125.             break;
  126.         case 5:
  127.             read(z);
  128.             k = Kth(x, y, Rank(x, y, z) + 1);
  129.             printf("%d\n", k == -INF ? INF : k);
  130.             break;
  131.         }
  132.     }
  133.     return 0;
  134. }
  136. /*
  137. 1. [l, r] k 排名
  138. 找每个区间比 k 小的个数
  139. 2. [l, r] 排名为 k
  140. 所有区间捞出来，线段树二分？
  141. 3. 单点修改下标 pos 的数改为 k
  142. 改就是了
  143. 4. [l, r] x 的前驱
  144. Kth(Rank(z - 1))
  145. 5. [l, r] x 的后继
  146. Kyh(Rank(z) + 1)
  147. */

seg_tree.cpp - DS

  1. // 区间加/乘法
  2. #include <stdio.h>
  3. #include <iostream>
  4. using namespace std;
  5. const int N = 100000;
  6. int n, m;
  7. long long mod;
  8. long long sum[N << 2], mult[N << 2], add[N << 2], a[N];
  9. void pushup(int x);
  10. void pushdown(int x, int l, int r, int m);
  11. void build(int x, int l, int r) {
  12.     add[x] = 0; mult[x] = 1;
  13.     if (l == r) {
  14.         sum[x] = a[l];
  15.         return ;
  16.     }
  17.     int m = (l + r) >> 1;
  18.     build(x << 1, l, m);
  19.     build(x << 1 | 1, m + 1, r);
  20.     pushup(x);
  21. }
  22. void init() {
  23.     scanf("%d%d%lld", &n, &m, &mod);
  24.     for (int i = 1; i <= n; i++)
  25.         scanf("%lld", &a[i]);
  26.     build(1, 1, n);
  27. }
  28. void pushup(int x) {
  29.     sum[x] = (sum[x << 1] + sum[x << 1 | 1]) % mod;
  30. }
  31. void pushdown(int x, int l, int r, int m) {
  32.     //left son
  33.     sum[x << 1] = (sum[x << 1] * mult[x] + (m - l + 1) * add[x]) % mod;
  34.     mult[x << 1] = (mult[x << 1] * mult[x]) % mod;
  35.     add[x << 1] = (add[x << 1] * mult[x] + add[x]) % mod;
  36.     //right son
  37.     sum[x << 1 | 1] = (sum[x << 1 | 1] * mult[x] + (r - m) * add[x]) % mod;
  38.     mult[x << 1 | 1] = (mult[x << 1 | 1] * mult[x]) % mod;
  39.     add[x << 1 | 1] = (add[x << 1 | 1] * mult[x] + add[x]) % mod;
  40.     //clear
  41.     add[x] = 0;
  42.     mult[x] = 1;
  43. }
  44. void modify(int L, int R, long long val, int x, int l, int r) { //add
  45.     if (L <= l && r <= R) {
  46.         add[x] = (add[x] + val) % mod;
  47.         sum[x] = (sum[x] + val * (long long)(r - l + 1)) % mod;
  48.         return ;
  49.     }
  50.     int m = (l + r) >> 1;
  51.     pushdown(x, l, r, m);
  52.     if (L <= m)
  53.         modify(L, R, val, x << 1, l, m);
  54.     if (R > m)
  55.         modify(L, R, val, x << 1 | 1, m + 1, r);
  56.     pushup(x);
  57. }
  58. void modify1(int L, int R, long long val, int x, int l, int r) { //mult
  59.     if (L <= l && r <= R) {
  60.         sum[x] = (sum[x] * val) % mod;
  61.         add[x] = (add[x] * val) % mod;
  62.         mult[x] = (mult[x] * val) % mod;
  63.         return ;
  64.     }
  65.     int m = (l + r) >> 1;
  66.     pushdown(x, l, r, m);
  67.     if (L <= m)
  68.         modify1(L, R, val, x << 1, l, m);
  69.     if (R > m)
  70.         modify1(L, R, val, x << 1 | 1, m + 1, r);
  71.     pushup(x);
  72. }
  73. long long query(int L, int R, int x, int l, int r) {
  74.     if (L <= l && r <= R)
  75.         return sum[x] % mod;
  76.     int m = (l + r) >> 1;
  77.     pushdown(x, l, r, m);
  78.     long long ret = 0;
  79.     if (L <= m)
  80.         ret += query(L, R, x << 1, l, m);
  81.     if (R > m)
  82.         ret += query(L, R, x << 1 | 1, m + 1, r);
  83.     return ret % mod;
  84. }
  85. int main() {
  86.     init();
  87.     while (m--) {
  88.         int op, x, y;
  89.         long long k;
  90.         scanf("%d", &op);
  91.         if (op == 1) { //mult
  92.             scanf("%d%d%lld", &x, &y, &k);
  93.             modify1(x, y, k, 1, 1, n);
  94.         }
  95.         if (op == 2) { //add
  96.             scanf("%d%d%lld", &x, &y, &k);
  97.             modify(x, y, k, 1, 1, n);
  98.         }
  99.         if (op == 3) { //query
  100.             scanf("%d%d", &x, &y);
  101.             printf("%lld\n", query(x, y, 1, 1, n));
  102.         }
  103.     }
  104. }

Treap.cpp - DS

  1. /*
  2.     数组实现的普通Treap
  3.     2020-6-19
  4.     by fxz
  5. */
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8. struct treap {
  9.   private:
  10.     // N 为节点数
  11.     const static int N = 100010;
  12.     const static int INF = 0x7fffffff;
  13.     // l,r左右儿子下标 val节点关键码 rnd随机权值 cnt副本数 siz子树大小 tot节点数 root树根
  14.     int l[N], r[N], val[N], rnd[N], cnt[N], siz[N], tot, root;
  15.     // 回收利用删除节点
  16.     int eat[N], et;
  17.     //回收节点
  18.     void del(int &p) {
  19.         eat[++et] = p; p = 0;
  20.     }
  21.     //开点
  22.     int newn(int vl) {
  23.         int t = et > 0 ? eat[et--] : ++tot;
  24.         val[t] = vl;
  25.         rnd[t] = rand();
  26.         cnt[t] = siz[t] = 1;
  27.         return t;
  28.     }
  29.     //上载，更新节点
  30.     void updata(int p) {
  31.         siz[p] = siz[l[p]] + siz[r[p]] + cnt[p];
  32.     }
  33.     //右旋
  34.     void zig(int &p) {
  35.         int q = l[p]; l[p] = r[q]; r[q] = p; p = q; updata(r[p]), updata(p);
  36.     }
  37.     //左旋
  38.     void zag(int &p) {
  39.         int q = r[p]; r[p] = l[q]; l[q] = p; p = q; updata(l[p]), updata(p);
  40.     }
  41.     //获取排名
  42.     int rank(int vl, int p) {
  43.         if (p == 0) return 0;
  44.         if (vl == val[p]) return siz[l[p]];
  45.         if (vl < val[p]) return rank(vl, l[p]);
  46.         return rank(vl, r[p]) + siz[l[p]] + cnt[p];
  47.     }
  48.     //获取数值
  49.     int value(int rk, int p) {
  50.         if (p == 0) return INF;
  51.         if (siz[p[l]] >= rk) return value(rk, l[p]);
  52.         if (siz[p[l]] + cnt[p] >= rk) return val[p];
  53.         return value(rk - siz[l[p]] - cnt[p], r[p]);
  54.     }
  55.     //插入
  56.     void _insert(int vl, int &p) {
  57.         if (p == 0) {
  58.             p = newn(vl);
  59.             return ;
  60.         }
  61.         if (vl == val[p]) {
  62.             cnt[p]++; updata(p);
  63.             return ;
  64.         }
  65.         if (vl < val[p]) {
  66.             _insert(vl, l[p]);
  67.             if (rnd[p] < rnd[l[p]]) zig(p);
  68.         } else {
  69.             _insert(vl, r[p]);
  70.             if (rnd[p] < rnd[r[p]]) zag(p);
  71.         }
  72.         updata(p);
  73.     }
  74.     //删除
  75.     void _remove(int vl, int &p) {
  76.         if (p == 0) return ;
  77.         if (vl == val[p]) {
  78.             if (cnt[p] > 1) {
  79.                 cnt[p]--; updata(p);
  80.                 return ;
  81.             }
  82.             if (l[p] || r[p]) {
  83.                 if (r[p] == 0 || rnd[l[p]] > rnd[r[p]]) zig(p), _remove(vl, r[p]);
  84.                 else zag(p), _remove(vl, l[p]);
  85.                 updata(p);
  86.             } else del(p);
  87.             return ;
  88.         }
  89.         vl < val[p] ? _remove(vl, l[p]) : _remove(vl, r[p]);
  90.         updata(p);
  91.     }
  92.   public:
  93.     //重置，初始化
  94.     void build() {
  95.         tot = et = 0;
  96.         newn(-INF), newn(INF);
  97.         root = 1, r[1] = 2;
  98.         updata(root);
  99.     }
  100.     //获取某值的排名(定义为比它小的个数+1)
  101.     int getrank(int vl) {
  102.         return rank(vl, root);
  103.     }
  104.     //获取排名为rk值
  105.     int getval(int rk) {
  106.         return value(rk + 1, root);
  107.     }
  108.     //插入一个值，可重复
  109.     void insert(int vl) {
  110.         _insert(vl, root);
  111.     }
  112.     //输出某值前驱，若无则-INF
  113.     int getpre(int vl) {
  114.         int ret = 1, p = root; // val[1]==-INF
  115.         while (p) {
  116.             if (vl == val[p]) {
  117.                 if (l[p] > 0) {
  118.                     p = l[p];
  119.                     while (r[p] > 0) p = r[p];
  120.                     ret = p;
  121.                 }
  122.             }
  123.             if (val[p] < vl && val[p] > val[ret]) ret = p;
  124.             p = vl < val[p] ? l[p] : r[p];
  125.         }
  126.         return val[ret];
  127.     }
  128.     //输出某值后继，若无则INF
  129.     int getnxt(int vl) {
  130.         int ret = 2, p = root; //val[2]=INF
  131.         while (p) {
  132.             if (vl == val[p]) {
  133.                 if (r[p] > 0) {
  134.                     p = r[p];
  135.                     while (l[p] > 0) p = l[p];
  136.                     ret = p;
  137.                 }
  138.             }
  139.             if (val[p] > vl && val[p] < val[ret]) ret = p;
  140.             p = vl < val[p] ? l[p] : r[p];
  141.         }
  142.         return val[ret];
  143.     }
  144.     //删除某值，如果出现多个只删一个
  145.     void remove(int vl) {
  146.         _remove(vl, root);
  147.     }
  148.     //返回元素个数，包括重复元素
  149.     int size() {
  150.         return siz[root] - 2;
  151.     }
  152.     //判断是否为空
  153.     bool empty() {
  154.         return size() == 0;
  155.     }
  156. } tp;
  157. int n;
  158. int main() {
  159.     tp.build();
  160.     scanf("%d", &n);
  161.     while (n--) {
  162.         int op, x;
  163.         scanf("%d%d", &op, &x);
  164.         switch (op) {
  165.         case 1:
  166.             tp.insert(x); break;
  167.         case 2:
  168.             tp.remove(x); break;
  169.         case 3:
  170.             printf("%d\n", tp.getrank(x)); break;
  171.         case 4:
  172.             printf("%d\n", tp.getval(x)); break;
  173.         case 5:
  174.             printf("%d\n", tp.getpre(x)); break;
  175.         case 6:
  176.             printf("%d\n", tp.getnxt(x)); break;
  177.         }
  178.     }
  179. }

XOR01trie.cpp - DS

  1. /*
  2.     维护异或和的 01 trie
  3.     支持插入，删除，修改，全局+1
  4. */
  5. #include <bits/stdc++.h>
  8. namespace trie {
  9. #define ls(x) ch[x][0]
  10. #define rs(x) ch[x][1]
  11.     const int N = 600010;
  12.     const int DEP = 22;
  13.     int ch[N * DEP][2], w[N * DEP], xorw[N * DEP], sz;
  14.     int newnode() {++sz; ch[sz][0] = ch[sz][1] = 0; w[sz] = xorw[sz] = 0; return sz;}
  15.     void pushup(int p) {
  16.         w[p] = xorw[p] = 0;
  17.         if (ls(p)) {
  18.             w[p] += w[ls(p)];
  19.             xorw[p] ^= xorw[ls(p)] << 1;
  20.         }
  21.         if (rs(p)) {
  22.             w[p] += w[rs(p)];
  23.             xorw[p] ^= (xorw[rs(p)] << 1) | (w[rs(p)] & 1);
  24.         }
  25.     }
  26.     void insert(int &p, int x, int d = 0) {
  27.         if (!p) p = newnode();
  28.         if (d >= DEP) return ++w[p], void();
  29.         insert(ch[p][x & 1], x >> 1, d + 1);
  30.         pushup(p);
  31.     }
  32.     void erase(int p, int x, int d = 0) {
  33.         if (d >= DEP) return --w[p], void();
  34.         erase(ch[p][x & 1], x >> 1, d + 1);
  35.         pushup(p);
  36.     }
  37.     // merge q to p
  38.     int merge(int p, int q) {
  39.         if (!p || !q) return p + q;
  40.         w[p] += w[q]; xorw[p] ^= xorw[q];
  41.         ls(p) = merge(ls(p), ls(q));
  42.         rs(p) = merge(rs(p), rs(q));
  43.         return p;
  44.     }
  45.     void addall(int p) {
  46.         swap(ls(p), rs(p));
  47.         if (ls(p)) addall(ls(p));
  48.         pushup(p);
  49.     }
  50.     int xorsum(int p) {return xorw[p];}
  51. }
  53. int main() {
  54.     return 0;
  55. }

GEOMETRY

convex-hull.cpp - GEOMETRY

  1. #include <bits/stdc++.h>
  2. #define il inline
  3. using namespace std;
  4. typedef double db;
  5. const db eps = 1e-8;
  6. il int sign(const db &num) {return (num > eps) - (num < -eps);} // 判断符号，为正则 1 为负则 -1 为零则零
  7. il int cmp(const db &a, const db &b) {return sign(a - b);} // 比较大小
  8. struct vec { // Vector & Point
  9.     db x, y;
  10.     void input() {scanf("%lf%lf", &x, &y);}
  11.     vec(const db &_x = 0, const db &_y = 0): x(_x), y(_y) {}
  12.     il vec operator+(const vec &v) const {return vec(x + v.x, y + v.y);}
  13.     il vec operator-(const vec &v) const {return vec(x - v.x, y - v.y);}
  14.     il vec operator*(const db &a) const {return vec(x * a, y * a);}
  15.     il vec operator/(const db &a) const {return vec(x / a, y / a);}
  16.     il db len2() const {return x * x + y * y;}
  17.     il db len() const {return hypot(x, y);} // 模长
  18.     il vec turnc(db r) const {db l = len(); if (!sign(l)) return *this; r /= l; return (*this) * r;} // 改变长度
  19.     bool operator<(const vec t) const {return (cmp(x, t.x) == 0) ? (cmp(y, t.y) < 0) : (cmp(x, t.x) < 0);}
  20.     bool operator==(const vec t) const {return cmp(x, t.x) == 0 && cmp(y, t.y) == 0;}
  21. };
  22. typedef vec poi;
  23. il db dot(const vec &a, const vec &b) {return a.x * b.x + a.y * b.y;} // 点积
  24. il db crs(const vec &a, const vec &b) {return a.x * b.y - a.y * b.x;} // 叉积
  25. il db dis(const poi &a, const poi &b) {return (b - a).len();} // 两点距离
  26. vector<poi> pts, pois; int n;
  27. poi O;
  28. bool cmpv(poi a, poi b) { // 极角排序（这个 cmp 需要保证所有点在原点一侧）
  29.     int k = sign(crs(a - O, b - O));
  30.     return (k == 0) ? ((a - O).len2() < (b - O).len2()) : (k > 0);
  31. }
  32. int relat(const poi &a, const poi &b, const poi &c) { // 三点关系，判断是凸还是凹
  33.     return sign(crs(b - a, c - b));
  34. }
  35. void Graham(vector<poi> pt, vector<poi> &res) { // Graham 求凸包 (极角排序+单调栈)
  36.     res.clear();
  37.     for (int i = 1; i < (int)pt.size(); ++i) if (pt[i] < pt[0]) swap(pt[i], pt[0]);
  38.     O = pt[0];
  39.     sort(pt.begin() + 1, pt.end(), cmpv);
  40.     for (int i = 0; i < (int)pt.size(); ++i) {
  41.         while (res.size() >= 2 && relat(res[res.size() - 2], res[res.size() - 1], pt[i]) <= 0) res.pop_back();
  42.         res.push_back(pt[i]);
  43.     }
  44. }
  45. db Aera(vec a, vec b, vec c) {return abs(crs(b - a, c - a));} // 三角形面积 |(*2)|
  46. db Diam(vector<poi> pt) { // 凸包直径 Diameter “旋转卡壳”
  47.     int n = pt.size(), j = 0; db res = 0;
  48.     if (pt.size() == 2) return (pt[0] - pt[1]).len2();
  49.     pt.push_back(pt[0]);
  50.     for (int i = 0; i < n; ++i) {
  51.         while (Aera(pt[i], pt[i + 1], pt[(j + 1) % n]) >= Aera(pt[i], pt[i + 1], pt[j])) j = (j + 1) % n;
  52.         res = max(res, max((pt[j] - pt[i]).len2(), (pt[j] - pt[i + 1]).len2()));
  53.     }
  54.     return res;
  55. }
  56. db Perim(vector<poi> pt) { // 凸包周长 Perimeter
  57.     db res = 0; int n = pois.size();
  58.     for (int i = 0; i < n; ++i) res += dis(pois[(i == 0) ? (n - 1) : (i - 1)], pois[i]);
  59.     return res;
  60. }
  61. db Area(const vector<poi> &pts) { // 任意多边形面积  (有向面积：顺负逆正)
  62.     db res = 0; int n = pts.size();
  63.     for (int i = 1; i < n - 1; ++i) res += crs(pts[i] - pts[0], pts[i + 1] - pts[0]);
  64.     return res / 2.0;
  65. }
  66. poi Grav(const vector<poi> &pts) { // Center of Gravity  多边形质心
  67.     poi g; db sumarea = 0; int n = pts.size();
  68.     for (int i = 2; i < n; ++i) {
  69.         db S = crs(pts[i - 1] - pts[0], pts[i] - pts[0]);
  70.         g = g + (pts[0] + pts[i - 1] + pts[i]) * S;
  71.         sumarea += S;
  72.     }
  73.     return g / (sumarea * 3);
  74. }
  75. int main() {
  76.     // Readin
  77.     scanf("%d", &n); pts.resize(n);
  78.     for (int i = 0; i < n; ++i) pts[i].input();
  79. }

half-plane.cpp - GEOMETRY

  1. /*
  2.     半平面交
  3.     本代码 --> 求凸多边形面积并
  4. */
  5. #include <bits/stdc++.h>
  6. #define il inline
  7. using namespace std;
  9. typedef double db;
  10. const db Pi = acos(-1.0);
  11. const db eps = 1e-7;
  13. il int sign(db num) {return (num > eps) - (num < -eps);}
  14. il int cmp(db a, db b) {return sign(a - b);}
  16. struct vec {
  17.     db x, y;
  18.     vec(db _x = 0, db _y = 0): x(_x), y(_y) {}
  19.     il void input() {scanf("%lf%lf", &x, &y);}
  20.     il vec operator+(const vec &t) const {return vec(x + t.x, y + t.y);}
  21.     il vec operator-(const vec &t) const {return vec(x - t.x, y - t.y);}
  22.     il vec operator*(const db  &t) const {return vec(x * t, y * t);}
  23.     il vec operator/(const db  &t) const {return vec(x / t, y / t);}
  24.     il db len2() const {return x * x + y * y;}
  25.     il db len()  const {return hypot(x, y);}
  26.     bool operator<(const vec &t) const {return (cmp(x, t.x) == 0) ? (cmp(y, t.y) < 0) : (cmp(x, t.x) < 0);}
  27. };
  28. typedef vec poi;
  29. il db dot(const vec &a, const vec &b) {return a.x * b.x + a.y * b.y;}
  30. il db crs(const vec &a, const vec &b) {return a.x * b.y - a.y * b.x;}
  31. il db dis(const vec &a, const vec &b) {return (a - b).len();}
  32. struct lin {
  33.     poi s, e; db k;
  34.     lin(poi _s, vec _e): s(_s), e(_e), k(atan2((e - s).y, (e - s).x)) {}
  35.     il poi operator()() const {return e - s;}
  36. };
  37. il poi cross(const lin &l1, const lin &l2) {return l1.s + l1() * crs(l2.s - l1.s, l2()) / crs(l1(), l2());}
  38. vector<lin> L; // 半平面们，统一向量左侧为半平面
  39. vector<poi> P, pts; // 多边形们
  40. int n, m;
  41. bool cmpl(lin a, lin b) { // 极角排序，极角相同靠左优先
  42.     if (cmp(a.k, b.k) == 0) return sign(crs(b.e-a.s, a())) > 0;
  43.     return cmp(a.k, b.k) < 0;
  44. }
  45. bool Onright(lin a, lin b, lin c) { // a,b 交点在 c 右边
  46.     poi p = cross(a, b);
  47.     return sign(crs(c(), p - c.s)) <= 0;
  48. }
  49. void Halfplane(vector<lin> Ls, vector<poi> &res) { // 半平面交
  50.     res.clear();
  51.     sort(Ls.begin(), Ls.end(), cmpl);
  52.     deque<int> q;
  53.     for (int i = 0; i < (int)Ls.size(); ++i) {
  54.         if (i != 0 && cmp(Ls[i].k, Ls[i - 1].k) == 0) continue;
  55.         while (q.size() >= 2 && Onright(Ls[q[q.size() - 2]], Ls[q.back()], Ls[i])) q.pop_back();
  56.         while (q.size() >= 2 && Onright(Ls[q.front()], Ls[q[1]], Ls[i])) q.pop_front();
  57.         q.push_back(i);
  58.     }
  59.     while (q.size() >= 2 && Onright(Ls[q[q.size() - 2]], Ls[q.back()], Ls[q.front()])) q.pop_back();
  60.     while (q.size() >= 2 && Onright(Ls[q[0]], Ls[q[1]], Ls[q.back()])) q.pop_front();
  61.     if (q.size() >= 2) res.push_back(cross(Ls[q.back()], Ls[q.front()]));
  62.     while (q.size() >= 2) {
  63.         res.push_back(cross(Ls[q[0]], Ls[q[1]]));
  64.         q.pop_front();
  65.     }
  66. }
  67. db Area(const vector<poi> &pts) { //多边形面积
  68.     db res = 0;
  69.     for (int i = 1; i < (int)pts.size() - 1; ++i) res += crs(pts[i] - pts[0], pts[i + 1] - pts[0]);
  70.     return res / 2.0;
  71. }
  72. int main() {
  73.     scanf("%d", &n);
  74.     for (int i = 1; i <= n; ++i) {
  75.         scanf("%d", &m);
  76.         pts.resize(m);
  77.         for (int i = 0; i < m; ++i) pts[i].input();
  78.         for (int i = 0; i < m; ++i) L.push_back(lin(pts[i], pts[(i + 1) % m]));
  79.     }
  80.     Halfplane(L, P);
  81.     db ans = Area(P);
  82.     printf("%.3lf\n", ans);
  83.     return 0;
  84. }

six_in_one.cpp - GEOMETRY

  1. /*
  2.     https://vjudge.net/problem/UVA-12304
  3.     计算几何 基du础liu题  点线圆相关
  5.     计算几何板子 v1.0
  6. */
  7. #include <bits/stdc++.h>
  8. #define il inline
  9. using namespace std;
  10. typedef double db;
  12. const db eps = 1e-10;
  13. il int sign(const db &num) {return (num > eps) - (num < -eps);} // 判断符号，为正则 1 为负则 -1 为零则零
  14. il int cmp(const db &a, const db &b) {return sign(a - b);} // 比较大小
  16. const db Pi = acos(-1);
  17. il db R_to_D(const db &rad) {return 180.0 / Pi * rad;}
  18. il db D_to_R(const db &deg) {return Pi / 180.0 * deg;}
  20. struct vec { // Vector & Point
  21.     db x, y;
  22.     void input() {scanf("%lf%lf", &x, &y);}
  23.     vec(const db &_x = 0, const db &_y = 0): x(_x), y(_y) {}
  24.     il vec operator+(const vec &v) const {return vec(x + v.x, y + v.y);}
  25.     il vec operator-(const vec &v) const {return vec(x - v.x, y - v.y);}
  26.     il vec operator*(const db &a) const {return vec(x * a, y * a);}
  27.     il vec operator/(const db &a) const {return vec(x / a, y / a);}
  28.     il db len2() const {return x * x + y * y;}
  29.     il db len() const {return hypot(x, y);} // 模长
  30.     il vec unit() const {db l = len(); return (sign(l) == 0) ? (vec(0, 0)) : (*this / l); } // 单位化
  31.     il vec turnc(db r) const {db l = len(); if (!sign(l)) return *this; r /= l; return (*this) * r;} // 改变长度
  32.     il db angle() const { db k = atan2(y, x); if (sign(k) < 0) k += Pi; if (cmp(k, Pi) == 0) k -= Pi; return k;}
  33.     bool operator<(const vec t) const {return (cmp(x, t.x) == 0) ? (cmp(y, t.y) < 0) : (cmp(x, t.x) < 0);}
  34.     bool operator==(const vec t) const {return cmp(x, t.x) == 0 && cmp(y, t.y) == 0;}
  35. };
  36. typedef vec poi;
  37. struct cir { // Circle
  38.     poi O; db r;
  39.     cir() {}
  40.     cir(const poi &_O, const db &_r): O(_O), r(_r) {}
  41.     void input() {O.input(); scanf("%lf", &r);}
  42. };
  43. struct lin { // Line & Ray
  44.     poi p; vec v;
  45.     lin() {}
  46.     lin(const poi &_p, const vec &_v): p(_p), v(_v) {} // 直线上点p，方向向量v
  47.     lin(const db &_x1, const db &_y1, const db &_x2, const db &_y2): p(_x1, _y1), v(_x2 - _x1,
  48.                 _y2 - _y1) {} // 直线上两点
  49.     il db angle() const {return v.angle();}
  50.     void input() {p.input(); v.input(); v = v - p;}
  51. };
  52. typedef lin ray;
  54. il db dot(const vec &a, const vec &b) {return a.x * b.x + a.y * b.y;} // 点积
  55. il db crs(const vec &a, const vec &b) {return a.x * b.y - a.y * b.x;} // 叉积
  56. il vec rot90(const vec &t) {return vec(-t.y, t.x);} // +90
  57. il vec rotn90(const vec &t) {return vec(t.y, -t.x);} // -90
  58. il vec rot180(const vec &t) {return vec(-t.x, -t.y);} // +180
  59. il poi cross(const lin &a, const lin &b) {return a.p + a.v * crs((b.p - a.p), b.v) / crs(a.v, b.v);} // 求两直线交点
  60. il poi foot(const lin &l, const poi &p) {return cross(lin(p, rot90(l.v)), l);} // p 到 l 的垂足
  61. il db dist(const lin &l, const poi &p) {return (p - foot(l, p)).len();} // 点到直线距离
  62. il db Helen(const db &a, const db &b, const db &c) { db p = (a + b + c) / 2; return sqrt(p * (p - a) * (p - b) * (p - c));} // 海伦公式，求三角形面积
  63. il int rela(const cir &c, const poi &p) {return cmp((c.O - p).len(), c.r) + 1;} // 点与圆关系，0:点在圆内；1:点在圆上；2:点在圆外
  64. il int rela(const cir &c, const lin &l); // 圆与直线关系
  65. il int rela(const cir &c, const lin &l); // 圆与圆关系
  66. il void cross(const cir &c, const lin &l, poi &p1, poi &p2); // 圆与直线交点
  68. void ptv(const vec &v) {printf(">>> [%.6lf,%.6lf]\n", v.x, v.y);}
  69. void ptp(const poi &p) {printf(">>> (%.6lf,%.6lf)\n", p.x, p.y);}
  70. void ptl(const lin &l) {printf(">>> (%.6lf,%.6lf) [%.6lf,%.6lf]\n", l.p.x, l.p.y, l.v.x, l.v.y);}
  71. void ptc(const cir &c) {printf(">>> (%.6lf,%.6lf) r=%0.6lf\n", c.O.x, c.O.y, c.r);}
  72. void ptt(const db  &t) {printf(">>> %.6lf\n", t);}
  74. cir OutsideCircle(const poi &A, const poi &B, const poi &C) { // 外接圆
  75.     poi O = cross(lin((A + B) / 2, rot90(B - A)), lin((A + C) / 2, rot90(A - C)));
  76.     return cir(O, (O - A).len());
  77. }
  79. cir InsideCircle(const poi &A, const poi &B, const poi &C) { // 内切圆
  80.     vec a = C - B, c = A - B, b = C - A;
  81.     db p = a.len() + b.len() + c.len();
  82.     db r = abs(crs(a, c) / p);
  83.     poi O = (A * a.len() + B * b.len() + C * c.len()) / p;
  84.     return cir(O, r);
  85. }
  87. void TangentLine(const cir &C, const poi &P, vector<lin> &res) { // 过点 P 到圆的切线
  88.     res.clear();
  89.     int op = cmp((C.O - P).len(), C.r);
  90.     if (op < 0) return ; // P 在圆内无切线
  91.     if (op == 0) {
  92.         res.push_back(lin(P, rot90(C.O - P))); // P 在圆上切线与半径垂直
  93.         return ;
  94.     }
  95.     // P 在圆外两切线
  96.     vec d = P - C.O;
  97.     db t = sqrt(d.len2() - C.r * C.r);
  98.     db h = t * C.r / d.len(), x = C.r * h / t;
  99.     poi F = C.O + d.turnc(x);
  100.     res.push_back(lin(P, (F + rot90(d).turnc(h) - P)));
  101.     res.push_back(lin(P, (F + rotn90(d).turnc(h) - P)));
  102. }
  104. void GetCircle(const poi &P, const lin &l, const db &r,
  105.                vector<poi> &res) { // 给圆上一点,一切线,半径：求圆心
  106.     res.clear();
  107.     if (sign(crs(l.v, l.p - P)) == 0) { // P 在 l 上，P 为切点
  108.         res.push_back(P + rot90(l.v).turnc(r));
  109.         res.push_back(P + rotn90(l.v).turnc(r));
  110.         return ;
  111.     }
  112.     poi F = foot(l, P); // F 为 P 到 l 垂足
  113.     int op = cmp((P - F).len(), 2 * r);
  114.     if (op > 0) return ; // P 到 l 距离大于 2r
  115.     if (op == 0) { // P 到 l 距离等于 2r，PF为直径
  116.         res.push_back((P + F) / 2);
  117.         return ;
  118.     }
  119.     db t = (P - F).len() - r, d = sqrt(r * r - t * t);
  120.     res.push_back(F + l.v.turnc(d) + (P - F).turnc(r));
  121.     res.push_back(F - l.v.turnc(d) + (P - F).turnc(r));
  122. }
  124. void GetCircle(const lin &l1, const lin &l2, const db &r, vector<poi> &res) { // 两切线+半径：求圆心
  125.     res.clear();
  126.     lin l1u = lin(l1.p + rot90(l1.v).turnc(r), l1.v), l1d = lin(l1.p + rotn90(l1.v).turnc(r), l1.v);
  127.     lin l2u = lin(l2.p + rot90(l2.v).turnc(r), l2.v), l2d = lin(l2.p + rotn90(l2.v).turnc(r), l2.v);
  128.     res.push_back(cross(l1u, l2u)); res.push_back(cross(l1u, l2d));
  129.     res.push_back(cross(l1d, l2u)); res.push_back(cross(l1d, l2d));
  130. }
  132. void CircleCross(const cir &c1, const cir &c2, vector<poi> &res) { // 求两圆交点
  133.     res.clear();
  134.     vec d = c2.O - c1.O;
  135.     int op = cmp(c1.r + c2.r, d.len());
  136.     if (op < 0) return ;
  137.     if (op == 0) {
  138.         res.push_back(c1.O + d.turnc(c1.r));
  139.         return ;
  140.     }
  141.     db t = c1.r * (c1.r * c1.r + d.len2() - c2.r * c2.r) / (2.0 * c1.r * d.len());
  142.     db h = sqrt(c1.r * c1.r - t * t);
  143.     res.push_back(c1.O + rot90(d).turnc(h) + d.turnc(t));
  144.     res.push_back(c1.O + rotn90(d).turnc(h) + d.turnc(t));
  145. }
  147. void TangentCircle(const cir &c1, const cir &c2, const db &r,
  148.                    vector<poi> &res) { // 给两无交圆 ，求半径为r的切圆
  149.     CircleCross(cir(c1.O, c1.r + r), cir(c2.O, c2.r + r), res);
  150. }
  152. void output(vector<poi> &pois) {
  153.     sort(pois.begin(), pois.end());
  154.     printf("[");
  155.     for (int i = 0; i < (int)pois.size(); ++i) {
  156.         printf("(%.6lf,%.6lf)", pois[i].x, pois[i].y);
  157.         if (i < (int)pois.size() - 1) putchar(',');
  158.     }
  159.     printf("]\n");
  160. }
  162. void output(vector<db> &nums) {
  163.     sort(nums.begin(), nums.end());
  164.     printf("[");
  165.     for (int i = 0; i < (int)nums.size(); ++i) {
  166.         printf("%.6lf", nums[i]);
  167.         if (i < (int)nums.size() - 1) putchar(',');
  168.     }
  169.     printf("]\n");
  170. }
  172. string opt;
  174. int main() {
  175.     while (cin >> opt) {
  176.         if (opt == "CircumscribedCircle") {
  177.             poi A, B, C; A.input(); B.input(); C.input();
  178.             cir c = OutsideCircle(A, B, C);
  179.             printf("(%.6lf,%.6lf,%.6lf)\n", c.O.x, c.O.y, c.r);
  180.         } else if (opt == "InscribedCircle") {
  181.             poi A, B, C; A.input(); B.input(); C.input();
  182.             cir c = InsideCircle(A, B, C);
  183.             printf("(%.6lf,%.6lf,%.6lf)\n", c.O.x, c.O.y, c.r);
  184.         } else if (opt == "TangentLineThroughPoint") {
  185.             vector<lin> lins; vector<db> degs; poi P; cir c;
  186.             c.input(); P.input();
  187.             TangentLine(c, P, lins);
  188.             for (int i = 0; i < (int)lins.size(); ++i)
  189.                 degs.push_back(R_to_D(lins[i].angle()));
  190.             output(degs);
  191.         } else if (opt == "CircleThroughAPointAndTangentToALineWithRadius") {
  192.             vector<poi> pois; poi P; lin l0; db r;
  193.             P.input(); l0.input(); scanf("%lf", &r);
  194.             GetCircle(P, l0, r, pois);
  195.             output(pois);
  196.         } else if (opt == "CircleTangentToTwoLinesWithRadius") {
  197.             vector<poi> pois; lin l1, l2; db r;
  198.             l1.input(); l2.input(); scanf("%lf", &r);
  199.             GetCircle(l1, l2, r, pois);
  200.             output(pois);
  201.         } else if (opt == "CircleTangentToTwoDisjointCirclesWithRadius") {
  202.             vector<poi> pois; cir c1, c2; db r;
  203.             c1.input(); c2.input(); scanf("%lf", &r);
  204.             TangentCircle(c1, c2, r, pois);
  205.             output(pois);
  206.         }
  207.     }
  208. }

最小圆覆盖.cpp - GEOMETRY

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <algorithm>
  4. #include <ctime>
  5. using namespace std;
  6. typedef long double db;
  7. const int N = 100010;
  8. struct vec {
  9.     db x, y;
  10.     vec(const db &_x = 0, const db &_y = 0): x(_x), y(_y) {}
  11.     vec operator+(const vec &t) const {return vec(x + t.x, y + t.y);}
  12.     vec operator-(const vec &t) const {return vec(x - t.x, y - t.y);}
  13.     vec operator*(const db &t) const {return vec(x * t, y * t);}
  14.     vec operator/(const db &t) const {return vec(x / t, y / t);}
  15.     const db len2() const {return x * x + y * y;}
  16.     const db len() const {return sqrt(len2());}
  17. };
  18. db dot(const vec &a, const vec &b) {return a.x * b.x + a.y * b.y;}
  19. db crs(const vec &a, const vec &b) {return a.x * b.y - a.y * b.x;}
  20. vec pt[N]; int n;
  21. vec rot90(vec a) {return vec(a.y, -a.x);}
  22. vec cross(vec p1, vec v1, vec p2, vec v2) {return p1 + v1 * crs(p2 - p1, v2) / crs(v1, v2);}
  23. vec get_circle(vec a, vec b, vec c) {   return cross((a + b) / 2, rot90(b - a), (b + c) / 2, rot90(c - b));}
  24. void min_circle_cover(vec p[], int t) {
  25.     random_shuffle(p + 1, p + n + 1);
  26.     db r_2 = 0; vec O;
  27.     for (int i = 1; i <= n; ++i) {
  28.         if ((p[i] - O).len2() > r_2) {
  29.             O = p[i], r_2 = 0;
  30.             for (int j = 1; j < i; ++j) {
  31.                 if ((p[j] - O).len2() > r_2) {
  32.                     O = (p[i] + p[j]) / 2, r_2 = (p[i] - O).len2();
  33.                     for (int k = 1; k < j; ++k) {
  34.                         if ((p[k] - O).len2() > r_2) {
  35.                             O = get_circle(p[i], p[j], p[k]); r_2 = (p[k] - O).len2();
  36.                         }
  37.                     }
  38.                 }
  39.             }
  40.         }
  41.     }
  42.     printf("%.10Lf\n%.10Lf %.10Lf\n", sqrt(r_2), O.x, O.y);
  43. }
  44. int main() {
  45.     srand(time(0));
  46.     scanf("%d", &n);
  47.     for (int i = 1; i <= n; ++i)
  48.         scanf("%Lf%Lf", &pt[i].x, &pt[i].y);
  49.     min_circle_cover(pt, n);
  50. }

GRAPH

2-SAT.cpp - GRAPH

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int N = 2000100;
  4. int n, m;
  5. struct twosat {
  6.     int head[N], pnt[N], nxt[N], E;
  7.     int dfn[N], low[N], tis, st[N], top, col[N], co, ans[N];
  8.     void add(int u, int v) {
  9.         E++; pnt[E] = v; nxt[E] = head[u]; head[u] = E;
  10.     }
  11.     void tarjan(int u) {
  12.         st[++top] = u; dfn[u] = low[u] = ++tis;
  13.         for (int i = head[u]; i; i = nxt[i]) {
  14.             int v = pnt[i];
  15.             if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
  16.             else if (!col[v]) low[u] = min(low[u], dfn[v]);
  17.         }
  18.         if (low[u] == dfn[u]) {
  19.             col[u] = ++co;
  20.             while (st[top] != u) {col[st[top]] = co; top--;}
  21.             top--;
  22.         }
  23.     }
  24.     bool solve() {
  25.         for (int i = 1; i <= 2 * n; i++) if (!dfn[i]) tarjan(i);
  26.         for (int i = 1; i <= n; i++) {
  27.             if (col[i] == col[i + n]) return 0;
  28.             ans[i] = (col[i] > col[i + n]);
  29.         }
  30.         return 1;
  31.     }
  32.     void insert(int i, bool a, int j, bool b) {
  33.         // here  xi=a or xj=b
  34.         add(i + n * (a ^ 1), j + b * n);
  35.         add(j + n * (b ^ 1), i + a * n);
  36.         // other forms
  37.         // if xi=a then xj=b
  38.         // add(i+a*n,j+b*n);
  39.         // add(j+(b^1)*n,i+(a^1)*n);
  40.     }
  41. } S;
  42. int main() {
  43.     scanf("%d%d", &n, &m);
  44.     for (int i = 1; i <= m; i++) {
  45.         int u, a, v, b;
  46.         scanf("%d%d%d%d", &u, &a, &v, &b);
  47.         S.insert(u, a, v, b);
  48.     }
  49.     bool fg = S.solve();
  50.     if (!fg) printf("IMPOSSIBLE\n");
  51.     else {
  52.         printf("POSSIBLE\n");
  53.         for (int i = 1; i <= n; i++) printf("%d ", S.ans[i]);
  54.         printf("\n");
  55.     }
  56. }

Dinic.cpp - GRAPH

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. template<typename T>
  4. inline void red(T &x) {
  5.     x = 0; bool fg = 0; char ch = getchar();
  6.     while (ch < '0' || ch > '9') {if (ch == '-') fg ^= 1; ch = getchar();}
  7.     while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (T)(ch ^ 48), ch = getchar();
  8.     if (fg) x = -x;
  9. }
  10. template<size_t N, size_t M>
  11. struct Dinic {
  12.     const int inf = 0x3f3f3f3f;
  13.     int fl[M << 1], pnt[M << 1], nxt[M << 1], cur[N], head[N], dep[N], E, S, T;
  14.     long long maxf;
  15.     Dinic() {memset(head, -1, sizeof(head)); E = -1;}
  16.     void adde(int u, int v, int c) {
  17.         E++; pnt[E] = v; fl[E] = c; nxt[E] = head[u]; head[u] = E;
  18.         E++; pnt[E] = u; fl[E] = 0; nxt[E] = head[v]; head[v] = E;
  19.     }
  20.     bool BFS(int u) {
  21.         memset(dep, 0x3f, sizeof(dep)); dep[S] = 0;
  22.         queue<int> q; q.push(S);
  23.         while (!q.empty()) {
  24.             int u = q.front(); q.pop();
  25.             if (u == T) break;
  26.             for (int i = head[u]; i != -1; i = nxt[i]) {
  27.                 if (fl[i] > 0 && dep[pnt[i]] == inf)
  28.                     dep[pnt[i]] = dep[u] + 1, q.push(pnt[i]);
  29.             }
  30.         }
  31.         return dep[T] != inf;
  32.     }
  33.     int DFS(int u, int nf) {
  34.         if (u == T || nf == 0) return nf;
  35.         int flow = 0, tf;
  36.         for (int &i = cur[u]; i != -1; i = nxt[i]) {
  37.             int v = pnt[i];
  38.             if (dep[v] != dep[u] + 1) continue;
  39.             tf = DFS(v, min(nf, fl[i]));
  40.             if (tf == 0) continue;
  41.             flow += tf; nf -= tf;
  42.             fl[i] -= tf; fl[i ^ 1] += tf;
  43.             if (nf == 0) break;
  44.         }
  45.         return flow;
  46.     }
  47.     long long maxflow() {
  48.         maxf = 0;
  49.         while (BFS(S)) {
  50.             memcpy(cur, head, sizeof(cur));
  51.             maxf += DFS(S, inf);
  52.         }
  53.         return maxf;
  54.     }
  55. };
  56. Dinic<205, 5005> G;
  57. int n, m, s, t;
  58. int main() {
  59.     // scanf("%d%d%d%d",&n,&m,&s,&t);
  60.     red(n); red(m); red(s); red(t);
  61.     G.S = s, G.T = t;
  62.     for (int i = 1; i <= m; ++i) {
  63.         int u, v, c; red(u); red(v); red(c);
  64.         // scanf("%d%d%d",&u,&v,&c);
  65.         G.adde(u, v, c);
  66.     }
  67.     printf("%lld\n", G.maxflow());
  68. }

e-cut.cpp - GRAPH

  1. // 割边（桥）
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. const int N = 20010;
  5. const int M = 200010;
  6. int head[N], pnt[M], nxt[M], E, n, m;
  7. int dfn[N], low[N], tim;
  8. bool ecut[M];
  9. void adde(int u, int v) {
  10.     E++; pnt[E] = v; nxt[E] = head[u]; head[u] = E;
  11. }
  12. void tarjan(int u, int in_edge) { // 考虑重边
  13.     dfn[u] = low[u] = ++tim;
  14.     for (int i = head[u]; i; i = nxt[i]) {
  15.         int v = pnt[i];
  16.         if (!dfn[v]) {
  17.             tarjan(v, i); 
  18.             low[u] = min(low[u], low[v]);
  19.             if (dfn[u] < low[v]) ecut[i] = ecut[i ^ 1] = true;
  20.         } else if (in_edge != (i ^ 1)) low[u] = min(low[u], dfn[v]);
  21.     }
  22. }
  23. int main() {
  24.     scanf("%d%d", &n, &m);
  25.     E = 1;
  26.     for (int i = 1; i <= m; ++i) {
  27.         int u, v; scanf("%d%d", &u, &v);
  28.         adde(u, v); adde(v, u);
  29.     }
  30.     for (int i = 1; i <= n; ++i) if (!dfn[i]) tarjan(i, 0);
  31.     return 0;
  32. }

e-DCC.cpp - GRAPH

  1. // 边双连通分量 & 缩点
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. const int N = 20010;
  5. const int M = 200010;
  6. int head[N], pnt[M], nxt[M], E, n, m;
  7. int headc[N], pntc[M], nxtc[M], Ec;
  8. int dfn[N], low[N], tim;
  9. bool ecut[M];
  10. void adde(int u, int v) {
  11.     E++; pnt[E] = v; nxt[E] = head[u]; head[u] = E;
  12. }
  13. void addec(int u, int v) {
  14.     Ec++; pntc[Ec] = v; nxtc[Ec] = headc[u]; headc[u] = Ec;
  15. }
  16. void tarjan(int u, int in_edge) { // 考虑重边
  17.     dfn[u] = low[u] = ++tim;
  18.     for (int i = head[u]; i; i = nxt[i]) {
  19.         int v = pnt[i];
  20.         if (!dfn[v]) {
  21.             tarjan(v, i); 
  22.             low[u] = min(low[u], low[v]);
  23.             if (dfn[u] < low[v]) ecut[i] = ecut[i ^ 1] = true;
  24.         } else if (in_edge != (i ^ 1)) low[u] = min(low[u], dfn[v]);
  25.     }
  26. }
  27. int col[N], dcc;
  28. void dfs(int u) {
  29.     col[u] = dcc;
  30.     for (int i = head[u]; i; i = nxt[i]) {
  31.         int v = pnt[i];
  32.         if (col[v] || ecut[i]) continue;
  33.         dfs(v);        
  34.     }
  35. }
  36. int main() {
  37.     scanf("%d%d", &n, &m);
  38.     E = 1; // !!
  39.     for (int i = 1; i <= m; ++i) {
  40.         int u, v; scanf("%d%d", &u, &v);
  41.         adde(u, v); adde(v, u);
  42.     }
  43.     // e-cut
  44.     for (int i = 1; i <= n; ++i) if (!dfn[i]) tarjan(i, 0);
  45.     // e-DCC 断开割边，每个联通块即 e-DCC
  46.     for (int i = 1; i <= n; ++i) if (!col[i]) {
  47.         ++dcc, dfs(i);
  48.     }
  49.     // e-DCC 缩点
  50.     for (int i = 2; i <= E; ++i) {
  51.         int u = pnt[i], v = pnt[i ^ 1];
  52.         if (col[u] == col[v]) continue;
  53.         addec(col[u], col[v]);
  54.     }
  55.     return 0;
  56. }

GomoryHu-Tree.cpp - GRAPH

  1. // 最小割树
  2. #include <bits/stdc++.h>
  3. template<typename _Tp>
  4. inline void red(_Tp &x) {
  5.     x = 0; bool fg = 0; char ch = getchar();
  6.     while (ch < '0' || ch > '9') {if (ch == '-') fg ^= 1; ch = getchar();}
  7.     while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (_Tp)(ch ^ 48), ch = getchar();
  8.     if (fg) x = -x;
  9. }
  10. using namespace std;
  11. const int N = 505;
  12. const int M = 3005;
  13. const int inf = 0x3f3f3f3f;
  14. int n, m, q;
  15. struct networkflow {
  16.     int head[N], pnt[M << 1], nxt[M << 1], fl[M << 1], E;
  17.     int dep[N], cur[N], maxf;
  18.     void adde(int u, int v, int f) {
  19.         E++; pnt[E] = v; fl[E] = f; nxt[E] = head[u]; head[u] = E;
  20.         E++; pnt[E] = u; fl[E] = 0; nxt[E] = head[v]; head[v] = E;
  21.     }
  22.     void init() {
  23.         memset(head, -1, sizeof(head));
  24.         E = -1;
  25.     }
  26.     void reset() { for (int i = 0; i < E; i += 2) fl[i] += fl[i + 1], fl[i + 1] = 0;}
  27.     bool BFS(int S, int T) {
  28.         memset(dep, 0x3f, sizeof(dep));
  29.         dep[S] = 0; queue<int> q; q.push(S);
  30.         while (!q.empty()) {
  31.             int u = q.front(); q.pop();
  32.             for (int i = head[u]; i != -1; i = nxt[i]) {
  33.                 int v = pnt[i];
  34.                 if (fl[i] > 0 && dep[v] == inf) {dep[v] = dep[u] + 1; q.push(v);}
  35.             }
  36.         }
  37.         return dep[T] < inf;
  38.     }
  39.     int DFS(int u, int T, int nf) {
  40.         if (u == T || nf == 0) return nf;
  41.         int flow = 0, tf;
  42.         for (int &i = cur[u]; i != -1; i = nxt[i]) {
  43.             int v = pnt[i];
  44.             if (dep[v] == dep[u] + 1) {
  45.                 tf = DFS(v, T, min(nf, fl[i]));
  46.                 flow += tf; nf -= tf;
  47.                 fl[i] -= tf; fl[i ^ 1] += tf;
  48.                 if (nf == 0) break;
  49.             }
  50.         }
  51.         return flow;
  52.     }
  53.     void Dinic(int S, int T) {
  54.         maxf = 0;
  55.         while (BFS(S, T)) {
  56.             memcpy(cur, head, sizeof(head));
  57.             maxf += DFS(S, T, inf);
  58.         }
  59.     }
  60. } G;
  61. int t[N], head[N], pnt[N << 1], nxt[N << 1], wth[N << 1], E;
  62. int tl[N], tr[N];
  64. void adde(int u, int v, int w) {
  65.     // fprintf(stderr,"e : %d %d %d\n",u,v,w);
  66.     E++; pnt[E] = v; wth[E] = w; nxt[E] = head[u]; head[u] = E;
  67. }
  68. void Build(int l, int r) {
  69.     if (l == r) return ;
  70.     G.reset(); G.Dinic(t[l], t[r]);
  71.     adde(t[l], t[r], G.maxf); adde(t[r], t[l], G.maxf);
  72.     int cl = 0, cr = 0;
  73.     for (int i = l; i <= r; ++i) {
  74.         if (G.dep[t[i]] == inf) tr[cr++] = t[i];
  75.         else tl[cl++] = t[i];
  76.     }
  77.     for (int i = 0; i < cl; ++i) t[l + i] = tl[i];
  78.     for (int i = 0; i < cr; ++i) t[l + cl + i] = tr[i];
  79.     Build(l, l + cl - 1); Build(l + cl, l + cl + cr - 1);
  80. }
  82. int fa[10][N], mn[10][N], dep[N];
  83. bool vis[N];
  84. void Prework(int u) {
  85.     vis[u] = 1;
  86.     for (int i = 1; i < 10; ++i) {
  87.         fa[i][u] = fa[i - 1][fa[i - 1][u]];
  88.         if (fa[i][u] == 0) break;
  89.         mn[i][u] = min(mn[i - 1][u], mn[i - 1][fa[i - 1][u]]);
  90.     }
  91.     for (int i = head[u]; i; i = nxt[i]) {
  92.         int v = pnt[i];
  93.         if (v == fa[0][u]) continue;
  94.         fa[0][v] = u; mn[0][v] = wth[i]; dep[v] = dep[u] + 1;
  95.         Prework(v);
  96.     }
  97. }
  98. int Query(int u, int v) {
  99.     if (dep[u] < dep[v]) swap(u, v);
  100.     int d = dep[u] - dep[v], ret = inf;
  101.     for (int i = 0; i < 10; ++i) if ((d >> i) & 1)
  102.             ret = min(ret, mn[i][u]), u = fa[i][u];
  103.     if (u == v) return ret;
  104.     for (int i = 9; i >= 0; --i) if (fa[i][u] != fa[i][v])
  105.             ret = min(ret, min(mn[i][u], mn[i][v])),
  106.             u = fa[i][u], v = fa[i][v];
  107.     return min(ret, min(mn[0][u], mn[0][v]));
  108. }
  110. int main() {
  111.     red(n); red(m);
  112.     G.init();
  113.     for (int i = 1; i <= m; ++i) {
  114.         int u, v, w; red(u); red(v); red(w);
  115.         G.adde(u, v, w); G.adde(v, u, w);
  116.     }
  117.     for (int i = 1; i <= n; ++i) t[i] = i;
  118.     Build(1, n);
  119.     Prework(1);
  120.     red(q);
  121.     while (q--) {
  122.         int u, v; red(u); red(v);
  123.         printf("%d\n", Query(u, v));
  124.     }
  125. }

Hungarian.cpp - GRAPH

  1. // 二分图最大匹配 匈牙利算法
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. const int N = 505;
  5. vector<int> e[N];
  6. int mx[N], my[N], n, m, E;
  7. bool vis[N];
  8. bool find(int x) {
  9.     for (auto y : e[x]) if (!vis[y]) {
  10.         vis[y] = 1;
  11.         if (my[y] == 0 || find(my[y])) {
  12.             my[y] = x, mx[x] = y;
  13.             return true;
  14.         }
  15.     }
  16.     return false;
  17. }
  18. int march(){
  19.     int cnt = 0;
  20.     memset(my, 0, sizeof(my));
  21.     memset(mx, 0, sizeof(mx));
  22.     for (int i = 1; i <= n; ++i) {
  23.         memset(vis, 0, sizeof(vis));
  24.         cnt += find(i);
  25.     }
  26.     return cnt;
  27. }
  28. int main() {
  29.     scanf("%d%d%d", &n, &m, &E);
  30.     for (int i = 1; i <= E; ++i) {
  31.         int u, v; scanf("%d%d", &u, &v);
  32.         e[u].push_back(v);
  33.     }
  34.     printf("%d\n", march());
  35. }

MFMC(Dijkstra).cpp - GRAPH

  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. template<typename _Tp>
  5. inline void red(_Tp &x) {
  6.     x = 0; bool fg = 0; char ch = getchar();
  7.     while (ch < '0' || ch > '9') {if (ch == '-') fg ^= 1; ch = getchar();}
  8.     while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (_Tp)(ch ^ 48), ch = getchar();
  9.     if (fg) x = -x;
  10. }
  11. template<typename _Tp> bool umax(_Tp &x, _Tp y) {return (x < y) ? (x = y, true) : (false);}
  12. template<typename _Tp> bool umin(_Tp &x, _Tp y) {return (x > y) ? (x = y, true) : (false);}
  13. using namespace std;
  14. typedef long long ll;
  15. typedef pair<int, int> P;
  16. const int inf = 0x3f3f3f3f;
  17. int n, m, s, t;
  18. struct networkflow {
  19.     static const int N = 5010, M = 100010;
  20.     int head[N], pnt[M], fl[M], nxt[M], cst[M], pre[N], lst[N], E = -1;
  21.     int dis[N], h[N]; bool vis[N];
  22.     int minc, maxf, n;
  23.     void init(int _n) {
  24.         memset(head, -1, sizeof(head)); E = -1; n = _n;
  25.     }
  26.     void adde(int u, int v, int f, int c) {
  27.         ++E; pnt[E] = v; nxt[E] = head[u]; head[u] = E; fl[E] = f; cst[E] = c;
  28.         ++E; pnt[E] = u; nxt[E] = head[v]; head[v] = E; fl[E] = 0; cst[E] = -c;
  29.     }
  30.     bool SPFA(int S, int T) {
  31.         memset(dis, 0x3f, sizeof(dis));
  32.         memset(vis, 0, sizeof(vis));
  33.         dis[S] = 0; vis[S] = 1; queue<int> q; q.push(S);
  34.         while (!q.empty()) {
  35.             int u = q.front(); q.pop();
  36.             vis[u] = 0;
  37.             for (int i = head[u]; i != -1; i = nxt[i]) {
  38.                 int v = pnt[i];
  39.                 if (fl[i] > 0 && dis[u] + cst[i] < dis[v]) {
  40.                     dis[v] = dis[u] + cst[i]; pre[v] = u; lst[v] = i;
  41.                     if (!vis[v]) q.push(v), vis[v] = 1;
  42.                 }
  43.             }
  44.         }
  45.         return dis[T] < inf;
  46.     }
  47.     void work(int S, int T) {
  48.         for (int i = 0; i <= n; ++i) h[i] += dis[i];
  49.         int flow = inf;
  50.         for (int u = T; u != S; u = pre[u]) flow = min(flow, fl[lst[u]]);
  51.         maxf += flow; minc += flow * h[T];
  52.         for (int u = T; u != S; u = pre[u]) {
  53.             fl[lst[u]] -= flow;
  54.             fl[lst[u] ^ 1] += flow;
  55.         }
  56.     }
  57.     bool Dij(int S, int T) {
  58.         priority_queue<P, vector<P>, greater<P> > q;
  59.         memset(dis, 0x3f, sizeof(dis));
  60.         memset(vis, 0, sizeof(vis));
  61.         dis[S] = 0; q.push({0, S});
  62.         while (!q.empty()) {
  63.             int u = q.top().se; q.pop();
  64.             if (vis[u]) continue; vis[u] = 1;
  65.             for (int i = head[u]; i != -1; i = nxt[i]) {
  66.                 int v = pnt[i];
  67.                 if (fl[i] > 0 && dis[v] > dis[u] + cst[i] + h[u] - h[v]) {
  68.                     dis[v] = dis[u] + cst[i] + h[u] - h[v];
  69.                     pre[v] = u; lst[v] = i;
  70.                     q.push({dis[v], v});
  71.                 }
  72.             }
  73.         }
  74.         return dis[T] < inf;
  75.     }
  76.     void MFMC(int S, int T) {
  77.         minc = maxf = 0;
  78.         memset(h, 0, sizeof(h));
  79.         if (SPFA(S, T)) work(S, T);
  80.         else return ;
  81.         while (Dij(S, T)) work(S, T);
  82.     }
  83. } G;
  84. int main() {
  85.     red(n); red(m); red(s); red(t);
  86.     G.init(n);
  87.     for (int i = 1; i <= m; ++i) {
  88.         int a, b, c, d; red(a); red(b); red(c); red(d);
  89.         G.adde(a, b, c, d);
  90.     }
  91.     G.MFMC(s, t);
  92.     printf("%d %d\n", G.maxf, G.minc);
  93.     return 0;
  94. }

MFMC(Dinic).cpp - GRAPH

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. template<size_t N, size_t M>
  4. struct SPFA_Dinic {
  5.     const int inf = 0x3f3f3f3f;
  6.     int fl[M << 1], cst[M << 1], pnt[M << 1], nxt[M << 1], cur[N], head[N], dis[N], E, S, T;
  7.     bool vis[N];
  8.     int maxf, minc;
  9.     SPFA_Dinic() {memset(head, -1, sizeof(head)); E = -1;}
  10.     void adde(int u, int v, int c, int w) { // (u,v) c容量限制，w单位费用
  11.         E++; pnt[E] = v; fl[E] = c; cst[E] = w; nxt[E] = head[u]; head[u] = E;
  12.         E++; pnt[E] = u; fl[E] = 0; cst[E] = -w; nxt[E] = head[v]; head[v] = E;
  13.     }
  14.     bool SPFA() {
  15.         memset(dis, 0x3f, sizeof(dis));
  16.         queue<int> q; q.push(S);
  17.         dis[S] = 0; vis[S] = 1;
  18.         while (!q.empty()) {
  19.             int u = q.front(); q.pop(); vis[u] = 0;
  20.             for (int i = head[u]; i != -1; i = nxt[i]) {
  21.                 int v = pnt[i];
  22.                 if (fl[i] > 0 && dis[v] > dis[u] + cst[i]) {
  23.                     dis[v] = dis[u] + cst[i];
  24.                     if (!vis[v]) q.push(v), vis[v] = 1;
  25.                 }
  26.             }
  27.         }
  28.         return dis[T] != inf;
  29.     }
  30.     int DFS(int u, int nf) {
  31.         if (u == T || nf == 0) return nf;
  32.         int flow = 0, tf; vis[u] = 1;
  33.         for (int &i = cur[u]; i != -1; i = nxt[i]) {
  34.             int v = pnt[i];
  35.             if (!vis[v] && fl[i] && dis[v] == dis[u] + cst[i]) {
  36.                 tf = DFS(v, min(nf, fl[i]));
  37.                 if (tf) {flow += tf; nf -= tf; fl[i] -= tf; fl[i ^ 1] += tf; minc += tf * cst[i];}
  38.             }
  39.             if (nf == 0) break;
  40.         }
  41.         vis[u] = 0;
  42.         return flow;
  43.     }
  44.     void MFMC() {
  45.         maxf = minc = 0;
  46.         int cnt = 0;
  47.         while (SPFA()) {
  48.             memcpy(cur, head, sizeof(cur));
  49.             maxf += DFS(S, inf);
  50.         }
  51.     }
  52. };
  53. SPFA_Dinic<5005, 50005> G;
  54. int n, m, s, t;
  55. int main() {
  56.     scanf("%d%d%d%d", &n, &m, &s, &t);
  57.     G.S = s, G.T = t;
  58.     for (int i = 1; i <= m; ++i) {
  59.         int u, v, c, w;
  60.         scanf("%d%d%d%d", &u, &v, &c, &w);
  61.         G.adde(u, v, c, w);
  62.     }
  63.     G.MFMC();
  64.     printf("%d %d\n", G.maxf, G.minc);
  65.     return 0;
  66. }

MFMC(EK).cpp - GRAPH

  1. #include <bits/stdc++.h>
  2. template<typename _Tp>
  3. inline void red(_Tp &x) {
  4.     x = 0; bool fg = 0; char ch = getchar();
  5.     while (ch < '0' || ch > '9') {if (ch == '-') fg ^= 1; ch = getchar();}
  6.     while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (_Tp)(ch ^ 48), ch = getchar();
  7.     if (fg) x = -x;
  8. }
  9. using namespace std;
  10. const int inf = 0x3f3f3f3f;
  11. int n, m, s, t;
  12. struct networkflow {
  13.     static const int N = 5010, M = 100010;
  14.     int head[N], pnt[M], fl[M], nxt[M], cst[M], pre[N], lst[N], E = -1;
  15.     int dis[N]; bool vis[N];
  16.     int minc, maxf;
  17.     void init() {
  18.         memset(head, -1, sizeof(head)); E = -1;
  19.     }
  20.     void adde(int u, int v, int f, int c) {
  21.         ++E; pnt[E] = v; nxt[E] = head[u]; head[u] = E; fl[E] = f; cst[E] = c;
  22.         ++E; pnt[E] = u; nxt[E] = head[v]; head[v] = E; fl[E] = 0; cst[E] = -c;
  23.     }
  24.     bool SPFA(int S, int T) {
  25.         memset(dis, 0x3f, sizeof(dis));
  26.         memset(vis, 0, sizeof(vis));
  27.         dis[S] = 0; vis[S] = 1; queue<int> q; q.push(S);
  28.         while (!q.empty()) {
  29.             int u = q.front(); q.pop();
  30.             vis[u] = 0;
  31.             for (int i = head[u]; i != -1; i = nxt[i]) {
  32.                 int v = pnt[i];
  33.                 if (fl[i] > 0 && dis[u] + cst[i] < dis[v]) {
  34.                     dis[v] = dis[u] + cst[i]; pre[v] = u; lst[v] = i;
  35.                     if (!vis[v]) q.push(v), vis[v] = 1;
  36.                 }
  37.             }
  38.         }
  39.         return dis[T] < inf;
  40.     }
  41.     void work(int S, int T) {
  42.         int flow = inf;
  43.         for (int u = T; u != S; u = pre[u]) flow = min(flow, fl[lst[u]]);
  44.         maxf += flow; minc += flow * dis[T];
  45.         for (int u = T; u != S; u = pre[u]) {
  46.             fl[lst[u]] -= flow;
  47.             fl[lst[u] ^ 1] += flow;
  48.         }
  49.     }
  50.     void MFMC(int S, int T) {
  51.         minc = maxf = 0;
  52.         while (SPFA(S, T)) work(S, T);
  53.     }
  54. } G;
  55. int main() {
  56.     red(n); red(m); red(s); red(t);
  57.     G.init();
  58.     for (int i = 1; i <= m; ++i) {
  59.         int a, b, c, d; red(a); red(b); red(c); red(d);
  60.         G.adde(a, b, c, d);
  61.     }
  62.     G.MFMC(s, t);
  63.     printf("%d %d\n", G.maxf, G.minc);
  64. }

prufer.cpp - GRAPH

  1. // Prufer 序列
  2. #include <bits/stdc++.h>
  3. template <typename Tp>
  4. inline void read(Tp &x) {
  5.     x = 0; bool fg = 0; char ch = getchar();
  6.     while (ch < '0' || ch > '9') {if (ch == '-') fg ^= 1; ch = getchar();}
  7.     while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (Tp)(ch ^ 48), ch = getchar();
  8.     if (fg) x = -x;
  9. }
  10. using namespace std;
  11. const int N = 5000010;
  12. int n, type, a[N];
  13. long long ans = 0;
  15. namespace prufer {
  16.     int p[N], f[N], deg[N];
  17.     void encode(int *f, int n) { // father -> prufer
  18.         for (int i = 1; i <= n; ++i) deg[i] = 0;
  19.         for (int i = 1; i < n; ++i) ++deg[f[i]];
  20.         for (int i = 1, j = 1; i <= n - 2; ++i, ++j) {
  21.             while (deg[j]) ++j; p[i] = f[j];
  22.             while (i <= n - 2 && --deg[p[i]] == 0 && p[i] < j) p[i + 1] = f[p[i]], ++i;
  23.         }
  24.         for (int i = 1; i <= n - 2; ++i) ans ^= 1ll * i * p[i];
  25.     }
  27.     void decode(int *p, int n) { // prufer -> father
  28.         for (int i = 1; i <= n; ++i) deg[i] = 0;
  29.         for (int i = 1; i <= n - 2; ++i) ++deg[p[i]]; p[n - 1] = n;
  30.         for (int i = 1, j = 1; i < n; ++i, ++j) {
  31.             while (deg[j]) ++j; f[j] = p[i];
  32.             while (i < n && --deg[p[i]] == 0 && p[i] < j) f[p[i]] = p[i + 1], ++i;
  33.         }
  34.         for (int i = 1; i <= n - 1; ++i) ans ^= 1ll * i * f[i];
  35.     }
  36. }
  38. int main() {
  39.     read(n); read(type);
  40.     for (int i = 1; i <= n - type; ++i) read(a[i]);
  41.     if (type == 1) prufer::encode(a, n);
  42.     else prufer::decode(a, n);
  43.     printf("%lld\n", ans);
  44.     return 0;
  45. }

SCC.cpp - GRAPH

  1. // 强连通分量
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. const int N = 10010;
  5. const int M = 200010;
  6. int head[N], pnt[M], nxt[M], E, n, m;
  7. int dfn[N], low[N], tim, sta[N], top, scc[N], cnt;
  8. void adde(int u, int v) {
  9.     E++; pnt[E] = v; nxt[E] = head[u]; head[u] = E;
  10. }
  11. void tarjan(int u) {
  12.     dfn[u] = low[u] = ++tim;
  13.     sta[++top] = u;
  14.     for (int i = head[u]; i; i = nxt[i]) {
  15.         int v = pnt[i];
  16.         if (!dfn[v]) {
  17.             tarjan(v);
  18.             low[u] = min(low[u], low[v]);
  19.         } else if (!scc[v]) low[u] = min(low[u], dfn[v]);
  20.     }
  21.     if (dfn[u] == low[u]) {
  22.         ++cnt;
  23.         do {
  24.             scc[sta[top]] = cnt;
  25.         } while (sta[top--] != u);
  26.     }
  27. }
  28. int main() {
  29.     scanf("%d%d", &n, &m);
  30.     for (int i = 1; i <= m; ++i) {
  31.         int u, v; scanf("%d%d", &u, &v);
  32.         adde(u, v); adde(v, u);
  33.     }
  34.     for (int i = 1; i <= n; ++i) if (!dfn[i]) top = 0, tarjan(i);
  35.     return 0;
  36. }

steiner-tree.cpp - GRAPH

  1. // 最小斯坦纳树
  2. // https://www.luogu.com.cn/problem/P6192
  3. #include <bits/stdc++.h>
  4. template <typename Tp>
  5. inline void read(Tp &x) {
  6.     x = 0; bool fg = 0; char ch = getchar();
  7.     while (ch < '0' || ch > '9') { if (ch == '-') fg ^= 1; ch = getchar();}
  8.     while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (Tp)(ch ^ 48), ch = getchar();
  9.     if (fg) x = -x;
  10. }
  11. template <typename Tp, typename... Args>
  12. void read(Tp &t, Args &...args) { read(t); read(args...); }
  13. using namespace std;
  14. typedef long long ll;
  15. const int N = 105;
  16. const int M = 1010;
  17. const int inf = 0x3f3f3f3f;
  18. int head[N], pnt[M], nxt[M], wth[M], E;
  19. int n, m, k, id[N], _id, ful;
  20. int dp[1 << 10][N];
  21. void adde(int u, int v, int w) {
  22.     E++; pnt[E] = v; wth[E] = w; nxt[E] = head[u]; head[u] = E;
  23. }
  24. struct dat {
  25.     int u, d;
  26.     bool operator<(const dat a) const {
  27.         return d > a.d;
  28.     }
  29. };
  30. bool vis[N];
  31. priority_queue<dat> Q;
  32. void dijk(int S) {
  33.     memset(vis, 0, sizeof(vis));
  34.     while (!Q.empty()) {
  35.         int u = Q.top().u; Q.pop();
  36.         if (vis[u]) continue;
  37.         vis[u] = 1;
  38.         for (int i = head[u]; i; i = nxt[i]) {
  39.             int v = pnt[i];
  40.             if (!vis[v] && dp[S][v] > dp[S][u] + wth[i]) {
  41.                 dp[S][v] = dp[S][u] + wth[i];
  42.                 Q.push(dat{v, dp[S][v]});
  43.             }
  44.         }
  45.     }
  46. }
  48. int main() {
  49.     read(n, m, k);
  50.     for (int i = 1; i <= m; ++i) {
  51.         int u, v, w; read(u, v, w);
  52.         adde(u, v, w); adde(v, u, w);
  53.     }
  54.     memset(id, -1, sizeof(id));
  55.     for (int i = 1; i <= k; ++i) {
  56.         int x; read(x); id[x] = _id++;
  57.     }
  58.     ful = (1 << k) - 1;
  59.     memset(dp, 0x3f, sizeof(dp));
  60.     for (int i = 1; i <= n; ++i) if (id[i] != -1)
  61.             dp[1 << id[i]][i] = 0;
  62.     for (int S = 1; S <= ful; ++S) {
  63.         for (int i = 1; i <= n; ++i) {
  64.             for (int sub = (S - 1) & S; sub; sub = (sub - 1) & S)
  65.                 dp[S][i] = min(dp[S][i], dp[sub][i] + dp[S ^ sub][i]);
  66.             if (dp[S][i] < inf) {
  67.                 Q.push(dat{i, dp[S][i]});
  68.             }
  69.         }
  70.         dijk(S);
  71.     }
  72.     int ans = inf;
  73.     for (int i = 1; i <= n; ++i)
  74.         ans = min(ans, dp[ful][i]);
  75.     printf("%d\n", ans);
  76.     return 0;
  77. }

v-cut.cpp - GRAPH

  1. // 割点（割顶）
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. const int N = 20010;
  5. const int M = 200010;
  6. int head[N], pnt[M], nxt[M], E, n, m;
  7. int dfn[N], low[N], tim, root;
  8. bool vcut[N];
  9. void adde(int u, int v) {
  10.     E++; pnt[E] = v; nxt[E] = head[u]; head[u] = E;
  11. }
  12. void tarjan(int u) {
  13.     dfn[u] = low[u] = ++tim;
  14.     int child = 0;
  15.     for (int i = head[u]; i; i = nxt[i]) {
  16.         int v = pnt[i];
  17.         if (!dfn[v]) {
  18.             tarjan(v); low[u] = min(low[u], low[v]);
  19.             if (dfn[u] <= low[v]) {
  20.                 ++child;
  21.                 if (u != root || child >= 2) vcut[u] = true;
  22.             }
  23.         } else low[u] = min(low[u], dfn[v]);
  24.     }
  25. }
  26. int main() {
  27.     scanf("%d%d", &n, &m);
  28.     for (int i = 1; i <= m; ++i) {
  29.         int u, v; scanf("%d%d", &u, &v);
  30.         adde(u, v); adde(v, u);
  31.     }
  32.     for (int i = 1; i <= n; ++i) if (!dfn[i]) root = i, tarjan(i);
  33.     return 0;
  34. }

v-DCC.cpp - GRAPH

  1. // 点双连通分量 & 缩点
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. const int N = 20010;
  5. const int M = 200010;
  6. int head[N], pnt[M], nxt[M], E, n, m;
  7. int headc[N], pntc[M], nxtc[M], Ec;
  8. int dfn[N], low[N], tim, root, sta[N], top;
  9. bool vcut[N];
  10. vector<int> dcc[N]; int col[N], cnt;
  11. int tot, new_id[N];
  12. void adde(int u, int v) {
  13.     E++; pnt[E] = v; nxt[E] = head[u]; head[u] = E;
  14. }
  15. void addec(int u, int v) {
  16.     Ec++; pntc[Ec] = v; nxtc[Ec] = headc[u]; headc[u] = Ec;
  17. }
  18. void tarjan(int u) {
  19.     dfn[u] = low[u] = ++tim;
  20.     sta[++top] = u;
  21.     if (u == root && head[u] == 0) { // 孤立点
  22.         dcc[++cnt].push_back(u); return;
  23.     }
  24.     int child = 0;
  25.     for (int i = head[u]; i; i = nxt[i]) {
  26.         int v = pnt[i];
  27.         if (!dfn[v]) {
  28.             tarjan(v); low[u] = min(low[u], low[v]);
  29.             if (dfn[u] <= low[v]) {
  30.                 ++child;
  31.                 if (u != root || child >= 2) vcut[u] = true;
  32.                 ++cnt;
  33.                 while (1) {
  34.                     dcc[cnt].push_back(sta[top]);
  35.                     if (sta[top--] == v) break;
  36.                 }
  37.                 dcc[cnt].push_back(u);
  38.             }
  39.         } else low[u] = min(low[u], dfn[v]);
  40.     }
  41. }
  42. int main() {
  43.     scanf("%d%d", &n, &m);
  44.     for (int i = 1; i <= m; ++i) {
  45.         int u, v; scanf("%d%d", &u, &v);
  46.         adde(u, v); adde(v, u);
  47.     }
  48.     for (int i = 1; i <= n; ++i) if (!dfn[i]) root = i, top = 0, tarjan(i);
  49.     // 割点可以属于多个 v-DCC，其它点只属于一个 v-DCC
  50.     // 缩点: 割点重新编号，每个 v-DCC 向它包含的割点连边
  51.     tot = cnt;
  52.     for (int i = 1; i <= n; ++i) if (vcut[i]) new_id[i] = ++tot;
  53.     for (int i = 1; i <= cnt; ++i) {
  54.         for (auto &u : dcc[i]) {
  55.             if (vcut[u]) {
  56.                 addec(i, new_id[u]);
  57.                 addec(new_id[u], i);
  58.             } else col[u] = i;
  59.         }
  60.     }
  61.     return 0;
  62. }

verdiv_tree.cpp - GRAPH

  1. // 点分树 luogu-P6329
  2. #include <bits/stdc++.h>
  3. #define see(x) cerr<<#x<<"="<<x<<endl;
  4. #define _max(x,y) ((x>y)?x:y)
  5. #define _min(x,y) ((x<y)?x:y)
  6. using namespace std;
  7. typedef long long ll;
  8. template<typename _Tp>
  9. inline void red(_Tp &x) {
  10.     x = 0; bool fg = 0; char ch = getchar();
  11.     while (ch < '0' || ch > '9') {if (ch == '-') fg ^= 1; ch = getchar();}
  12.     while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (_Tp)(ch ^ 48), ch = getchar();
  13.     if (fg) x = -x;
  14. }
  15. const int N = 100010;
  16. const int M = 20;
  17. int head[N], pnt[N << 1], nxt[N << 1], E;
  18. int val[N], son[N], siz[N], dep[N], mxdep, size, root, n, m;
  19. int far[N], Dep[N], dist[M][N];
  20. struct trearr {
  21.     vector<int> t; int n;
  22.     void init(int sz) {t.resize(sz + 1, 0); n = sz;}
  23.     void add(int x, int v) {for (; x <= n; x += x & -x) t[x] += v;}
  24.     int sum(int x) {int r = 0; for (x = _min(x, n); x > 0; x -= x & -x) r += t[x]; return r;}
  25. } Dt[N], dt[N];
  26. trearr *ps[N];
  27. bool vis[N];
  28. void adde(int u, int v) { E++; pnt[E] = v; nxt[E] = head[u]; head[u] = E; }
  29. void getroot(int u, int f) {
  30.     siz[u] = 1; son[u] = 0;
  31.     for (int i = head[u]; i; i = nxt[i]) {
  32.         int v = pnt[i];
  33.         if (v == f || vis[v]) continue;
  34.         getroot(v, u);
  35.         siz[u] += siz[v];
  36.         son[u] = _max(son[u], siz[v]);
  37.     }
  38.     son[u] = _max(son[u], size - siz[u]);
  39.     if (son[u] < son[root]) root = u;
  40. }
  41. void dfs(int u, int f, int S, int fr) {
  42.     Dt[S].add(dep[u], val[u]); dt[fr].add(dep[u], val[u]);
  43.     dist[Dep[S]][u] = dep[u];
  44.     for (int i = head[u]; i; i = nxt[i]) {
  45.         int v = pnt[i];
  46.         if (v == f || vis[v]) continue;
  47.         dfs(v, u, S, fr);
  48.     }
  49. }
  50. void DFS(int u, int f, int d) {
  51.     dep[u] = d; siz[u] = 1; mxdep = _max(mxdep, d);
  52.     for (int i = head[u]; i; i = nxt[i]) {
  53.         int v = pnt[i];
  54.         if (v == f || vis[v]) continue;
  55.         DFS(v, u, d + 1); siz[u] += siz[v];
  56.     }
  57. }
  58. void vdiv(int u) {
  59.     int mx = 0;
  60.     vector<pair<int, int> > sons;
  61.     for (int i = head[u]; i; i = nxt[i]) {
  62.         int v = pnt[i];
  63.         if (vis[v]) continue;
  64.         mxdep = 0; DFS(v, u, 1); mx = _max(mx, mxdep);
  65.         size = siz[v]; root = 0; getroot(v, u);
  66.         sons.push_back(make_pair(v, root)); far[root] = u;
  67.         dt[root].init(mxdep);
  68.     }
  69.     Dt[u].init(mx);
  70.     for (int i = 0; i < sons.size(); ++i)
  71.         dfs(sons[i].first, u, u, sons[i].second);
  72.     vis[u] = 1;
  73.     for (int i = 0; i < sons.size(); ++i) {
  74.         Dep[sons[i].second] = Dep[u] + 1;
  75.         vdiv(sons[i].second);
  76.     }
  77. }
  78. int ask(int x, int K) {
  79.     int ret = 0, fr = -1;
  80.     for (int u = x; u; u = far[u]) {
  81.         int d = K - dist[Dep[u]][x];
  82.         if (d > 0) {
  83.             ret += Dt[u].sum(d);
  84.             if (fr != -1)
  85.                 ret -= dt[fr].sum(d);
  86.         }
  87.         if (d >= 0) ret += val[u];
  88.         fr = u;
  89.     }
  90.     return ret;
  91. }
  92. void modify(int x, int vl) {
  93.     int fr = x;
  94.     for (int u = far[x]; u; u = far[u]) {
  95.         int d = dist[Dep[u]][x];
  96.         Dt[u].add(d, -val[x]); dt[fr].add(d, -val[x]);
  97.         Dt[u].add(d, vl); dt[fr].add(d, vl);
  98.         fr = u;
  99.     }
  100.     val[x] = vl;
  101. }
  102. int main() {
  103.     red(n); red(m);
  104.     for (int i = 1; i <= n; ++i) red(val[i]);
  105.     for (int i = 1; i < n; ++i) {
  106.         int u, v; red(u); red(v);
  107.         adde(u, v); adde(v, u);
  108.     }
  109.     size = n; son[root = 0] = n;
  110.     getroot(1, 0);
  111.     vdiv(root);
  112.     int lst = 0;
  113.     while (m--) {
  114.         int op, x, y; red(op); red(x); red(y);
  115.         x ^= lst; y ^= lst;
  116.         if (op == 0) {
  117.             lst = ask(x, y);
  118.             printf("%d\n", lst);
  119.         } else
  120.             modify(x, y);
  121.     }
  122.     return 0;
  123. }

Virtual_Tree.cpp - GRAPH

  1. /*
  2.     luogu - P2495 [SDOI2011]消耗战
  3.     虚树板子，建树看 build()
  4.     Oi-wiki(虚树) --> https://oi-wiki.org/graph/virtual-tree/
  5. */
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8. template <typename T>
  9. inline void red(T &x) {
  10.     x = 0; bool f = 0; char ch = getchar();
  11.     while (ch < '0' || ch > '9') {if (ch == '-') f ^= 1; ch = getchar();}
  12.     while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (T)(ch ^ 48), ch = getchar();
  13.     if (f) x = -x;
  14. }
  15. const int N = 300000;
  16. const int inf = 0x3f3f3f3f;
  17. typedef long long ll;
  18. int head[N], pnt[N << 1], nxt[N << 1], wth[N << 1], E;
  19. int dfn[N], tim, h[N], K;
  20. int n, Q, fa[N], deg[N], W[N], ty[N];
  21. ll Dp[N];
  22. namespace LCA {
  23.     int siz[N], son[N], top[N], fa[N], dep[N];
  24.     void dfs1(int u, int f, int d) {
  25.         fa[u] = f; dep[u] = d; siz[u] = 1;
  26.         for (int i = head[u]; i; i = nxt[i]) {
  27.             int v = pnt[i];
  28.             if (v == f) continue;
  29.             dfs1(v, u, d + 1); siz[u] += siz[v];
  30.             if (siz[son[u]] < siz[v]) son[u] = v;
  31.         }
  32.     }
  33.     void dfs2(int u, int topf) {
  34.         top[u] = topf;
  35.         if (son[u]) dfs2(son[u], topf);
  36.         for (int i = head[u]; i; i = nxt[i]) {
  37.             int v = pnt[i];
  38.             if (v == son[u] || v == fa[u]) continue;
  39.             dfs2(v, v);
  40.         }
  41.     }
  42.     int lca(int u, int v) {
  43.         int fu = top[u], fv = top[v];
  44.         while (fu != fv) {
  45.             if (dep[fu] < dep[fv]) swap(fu, fv), swap(u, v);
  46.             u = fa[fu]; fu = top[u];
  47.         }
  48.         return (dep[u] < dep[v]) ? u : v;
  49.     }
  50. }
  51. using LCA::lca;
  52. void adde(int u, int v, int w) {
  53.     E++; pnt[E] = v; nxt[E] = head[u]; wth[E] = w; head[u] = E;
  54. }
  55. bool cmp(int x, int y) {    return dfn[x] < dfn[y];}
  56. void dfs(int u, int f) {
  57.     dfn[u] = ++tim;
  58.     for (int i = head[u]; i; i = nxt[i]) {
  59.         int v = pnt[i];
  60.         if (v == f) continue;
  61.         W[v] = min(W[u], wth[i]);
  62.         dfs(v, u);
  63.     }
  64. }
  65. // begin : build virtual tree
  66. int st[N], top, b[N], tot; // b[1:tot] are the nodes in virtual tree
  67. void build() {
  68.     sort(h + 1, h + K + 1, cmp);
  69.     st[top = 1] = 1; deg[1] = fa[1] = 0; b[tot = 1] = 1;
  70.     for (int i = 1; i <= K; ++i) {
  71.         if (h[i] == 1) continue;
  72.         int lc = lca(h[i], st[top]);
  73.         if (lc != st[top]) {
  74.             while (dfn[lc] < dfn[st[top - 1]]) {
  75.                 fa[st[top]] = st[top - 1];
  76.                 ++deg[st[top - 1]];
  77.                 top--;
  78.             }
  79.             if (dfn[lc] > dfn[st[top - 1]]) {
  80.                 fa[st[top]] = lc; deg[lc] = 1;
  81.                 fa[lc] = 0, st[top] = lc; b[++tot] = lc;
  82.             } else {
  83.                 fa[st[top--]] = lc; ++deg[lc];
  84.             }
  85.         }
  86.         st[++top] = h[i]; b[++tot] = h[i];
  87.         deg[h[i]] = fa[h[i]] = 0;
  88.     }
  89.     for (int i = 2; i <= top; ++i) fa[st[i]] = st[i - 1], ++deg[st[i - 1]];
  90. }
  91. // end build
  92. ll solve() {
  93.     queue<int> q;
  94.     for (int i = 1; i <= tot; ++i) {
  95.         Dp[b[i]] = 0;
  96.         if (deg[b[i]] == 0) q.push(b[i]);
  97.     }
  98.     while (!q.empty()) {
  99.         int u = q.front(); q.pop();
  100.         if (u == 1) break;
  101.         if (ty[u]) Dp[fa[u]] += W[u];
  102.         else Dp[fa[u]] += min((ll)W[u], Dp[u]);
  103.         --deg[fa[u]];
  104.         if (deg[fa[u]] == 0) q.push(fa[u]);
  105.     }
  106.     return Dp[1];
  107. }
  108. int main() {
  109.     red(n);
  110.     for (int i = 1; i < n; ++i) {
  111.         int u, v, w; red(u); red(v); red(w);
  112.         adde(u, v, w); adde(v, u, w);
  113.     }
  114.     W[1] = inf;
  115.     dfs(1, 0);
  116.     LCA::dfs1(1, 0, 0); LCA::dfs2(1, 1);
  117.     red(Q);
  118.     while (Q--) {
  119.         red(K);
  120.         for (int i = 1; i <= K; ++i) red(h[i]), ty[h[i]] = 1;
  121.         build();
  122.         ll ans = solve();
  123.         printf("%lld\n", ans);
  124.         for (int i = 1; i <= K; ++i) ty[h[i]] = 0;
  125.     }
  126. }

MATH

basis.cpp - MATH

  1. // P3812 【模板】线性基
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. typedef long long ll;
  5. const int B = 52;
  6. ll d[B], x;
  7. int tot, n;
  8. void insert(ll x) {
  9.     for (int i = B - 1; i >= 0; --i) if ((x >> i) & 1) {
  10.             if (d[i] == 0) {
  11.                 d[i] = x, ++tot; return ;
  12.             }
  13.             x ^= d[i];
  14.         }
  15. }
  16. ll getmax() {
  17.     ll ret = 0;
  18.     for (int i = B - 1; i >= 0; --i) if ((ret ^ d[i]) > ret) ret ^= d[i];
  19.     return ret;
  20. }
  21. ll getmin() {
  22.     if (tot < n) return 0;
  23.     for (int i = 0; i < B; ++i) if (d[i] != 0) return d[i];
  24.     return -1;
  25. }
  26. void work() {
  27.     for (int i = 1; i < B; ++i)
  28.         for (int j = 0; j < i; ++j)
  29.             if ((d[i] >> j) & 1) d[i] ^= d[j];
  30. }
  31. ll getkth(ll k) {
  32.     if (k == 1 && tot < n) return 0;
  33.     if (tot < n) --k;
  34.     work(); ll ret = 0;
  35.     for (int i = 0; i < B; ++i, k >>= 1) if (d[i] && (k & 1)) ret ^= d[i];
  36.     return ret;
  37. }
  38. int main() {
  39.     cin >> n;
  40.     for (int i = 1; i <= n; ++i) {
  41.         cin >> x;
  42.         insert(x);
  43.     }
  44.     printf("%lld\n", getmax());
  45. }

CRT.cpp - MATH

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int N = 20;
  5. ll a[N], b[N]; int n;
  6. ll exgcd(ll a, ll b, ll &x, ll &y) {
  7.     if (!b) {x = 1, y = 0; return a;}
  8.     ll d = exgcd(b, a % b, x, y);
  9.     swap(x, y); y -= a / b * x;
  10.     return d;
  11. }
  12. ll inv(ll a, ll b) {
  13.     ll x, y; exgcd(a, b, x, y);
  14.     return (x % b + b) % b;
  15. }
  16. // x=ai (mod mi)   gcd(m1,m2....mn)=1
  17. ll CRT(int n, ll a[], ll m[]) {
  18.     ll M = 1, x = 0;
  19.     for (int i = 1; i <= n; i++) M *= m[i];
  20.     for (int i = 1; i <= n; i++)
  21.         x = (x + (M / m[i]) * inv(M / m[i], m[i]) % M * a[i] % M) % M;
  22.     return x;
  23. }
  24. int main() {
  25.     scanf("%d", &n);
  26.     for (int i = 1; i <= n; i++) scanf("%lld%lld", &a[i], &b[i]);
  27.     ll ans = CRT(n, b, a);
  28.     printf("%lld\n", ans);
  29. }

EXBSGS.cpp - MATH

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. ll gcd(ll a, ll b) {return !b ? a : gcd(b, a % b);}
  5. ll exgcd(ll a, ll b, ll &x, ll &y) {
  6.     if (!b) {x = 1, y = 0; return a;}
  7.     ll d = exgcd(b, a % b, x, y);
  8.     swap(x, y); y -= a / b * x;
  9.     return d;
  10. }
  11. ll inv(ll a, ll b) {
  12.     ll x, y; exgcd(a, b, x, y);
  13.     return (x % b + b) % b;
  14. }
  15. ll BSGS(ll a, ll n, ll p) {
  16.     ll ans = p, t = ceil(sqrt(p)), dt = 1;
  17.     map<ll, ll> hash;
  18.     for (ll B = 1; B <= t; B++) dt = (dt * a) % p, hash[(dt * n) % p] = B;
  19.     for (ll A = 1, num = dt; A <= t;
  20.          A++, num = (num * dt) % p) if (hash.find(num) != hash.end()) ans = min(ans, A * t - hash[num]);
  21.     return ans;
  22. }
  23. //a^x=n (mod p)
  24. ll EXBSGS(ll a, ll n, ll p) {
  25.     int k = 0; ll d, ad = 1;
  26.     while ((d = gcd(a, p)) != 1) {
  27.         if (n % d) return -1;
  28.         n /= d, p /= d; ad *= a / d; ad %= p; k++;
  29.     }
  30.     n = (n * inv(ad, p)) % p;
  31.     ll res = BSGS(a, n, p);
  32.     if (res == p) return -1;
  33.     return res + k;
  34. }
  35. ll a, p, n;
  36. int main() {
  37.     while (cin >> a >> p >> n) {
  38.         if (a == 0 && p == 0 && n == 0) break;
  39.         ll ans = EXBSGS(a, n, p);
  40.         if (ans == -1) printf("No Solution\n");
  41.         else printf("%lld\n", ans);
  42.     }
  43. }

EXCRT.cpp - MATH

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int N = 100010;
  5. ll a[N], b[N]; int n;
  6. ll mul(ll a, ll b, ll mod) {
  7.     ll r = 0;
  8.     a = (a % mod + mod) % mod;
  9.     b = (b % mod + mod) % mod;
  10.     while (b) {
  11.         if (b & 1) r = (r + a) % mod;
  12.         a = (a << 1) % mod; b >>= 1;
  13.     } return r;
  14. }
  15. ll gcd(ll a, ll b) {
  16.     return !b ? a : gcd(b, a % b);
  17. }
  18. ll exgcd(ll a, ll b, ll &x, ll &y) {
  19.     if (!b) {x = 1, y = 0; return a;}
  20.     ll d = exgcd(b, a % b, x, y);
  21.     swap(x, y); y -= a / b * x;
  22.     return d;
  23. }
  24. // x=ai (mod mi)
  25. ll EXCRT(int n, ll a[], ll m[]) {
  26.     for (int i = 2; i <= n; i++) {
  27.         ll d = gcd(m[i - 1], m[i]), x, y;
  28.         if ((a[i] - a[i - 1]) % d != 0) return -1; // 无解
  29.         exgcd(m[i - 1] / d, m[i] / d, x, y);
  30.         m[i] = m[i] / gcd(m[i], m[i - 1]) * m[i - 1];
  31.         a[i] = (a[i - 1] + mul(mul((a[i] - a[i - 1]) / d, x, m[i]), m[i - 1], m[i])) % m[i];
  32.         a[i] = (a[i] + m[i]) % m[i];
  33.     }
  34.     return a[n];
  35. }
  36. int main() {
  37.     scanf("%d", &n);
  38.     for (int i = 1; i <= n; i++)
  39.         scanf("%lld%lld", &a[i], &b[i]);
  40.     ll ans = EXCRT(n, b, a);
  41.     printf("%lld\n", ans);
  42. }

exlucas.cpp - MATH

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. ll mul(ll a, ll b, ll p) {
  5.     ll l = ((b >> 30) % p * (1ll << 30) % p) % p;
  6.     ll r = (b & ((1ll << 30) - 1ll)) % p;
  7.     return ((l * a) % p + (r * a) % p) % p;
  8. }
  9. ll fpow(ll a, ll b, ll p) {
  10.     ll r = 1ll;
  11.     while (b) {
  12.         if (b & 1) r = mul(r, a, p);
  13.         a = mul(a, a, p);
  14.         b >>= 1;
  15.     }
  16.     return r;
  17. }
  18. ll exgcd(ll a, ll b, ll &x, ll &y) {
  19.     if (!b) {x = 1ll, y = 0; return a;}
  20.     ll d = exgcd(b, a % b, x, y); swap(x, y);
  21.     y -= (a / b) * x; return d;
  22. }
  23. ll inv(ll a, ll p) {
  24.     ll iv, k;
  25.     exgcd(a, p, iv, k);
  26.     return (iv % p + p) % p;
  27. }
  28. // calc (n!/p^c) mod p^k which gcd(n!/p^c,p^k)=1
  29. ll fact(ll n, ll p, ll pk) {
  30.     if (!n) return 1ll;
  31.     ll ret = 1ll;
  32.     for (ll i = 1ll; i <= pk; i++) {
  33.         if (i % p) ret = ret * i % pk;
  34.     }
  35.     ret = fpow(ret, n / pk, pk);
  36.     for (ll i = 1ll; i <= n % pk; i++) {
  37.         if (i % p) ret = ret * i % pk;
  38.     }
  39.     return ret * fact(n / p, p, pk) % pk;
  40. }
  41. ll C(ll n, ll m, ll p, ll pk) {
  42.     if (n < m) return 0;
  43.     ll f1 = fact(n, p, pk), f2 = inv(fact(m, p, pk), pk), f3 = inv(fact(n - m, p, pk), pk);
  44.     ll cnt = 0;
  45.     for (ll i = n; i; i /= p) cnt += i / p;
  46.     for (ll i = m; i; i /= p) cnt -= i / p;
  47.     for (ll i = n - m; i; i /= p) cnt -= i / p;
  48.     return f1 * f2 % pk * f3 % pk * fpow(p, cnt, pk) % pk;
  49. }
  50. ll CRT(int n, ll a[], ll m[]) {
  51.     ll M = 1, ret = 0;
  52.     for (int i = 1; i <= n; i++) M *= m[i];
  53.     for (int i = 1; i <= n; i++)
  54.         ret = (ret + a[i] * (M / m[i]) % M * inv(M / m[i], m[i])) % M;
  55.     return (ret % M + M) % M;
  56. }
  57. ll exlucas(ll n, ll m, ll p) {
  58.     ll pk[24], c[24]; int tot = 0;
  59.     for (ll i = 2ll; i <= p / i; i++) {
  60.         if (p % i == 0) {
  61.             pk[++tot] = 1ll;
  62.             while (p % i == 0) p /= i, pk[tot] *= i;
  63.             c[tot] = C(n, m, i, pk[tot]);
  64.         }
  65.     }
  66.     if (p > 1) pk[++tot] = p, c[tot] = C(n, m, p, p);
  67.     return CRT(tot, c, pk);
  68. }
  69. int main() {
  70.     ll n, m, p;
  71.     cin >> n >> m >> p;
  72.     cout << exlucas(n, m, p) << endl;
  73. }

guess.cpp - MATH

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int N = 105;
  4. double a[N][N];
  5. int n;
  6. void init() {
  7.     scanf("%d", &n);
  8.     for (int i = 1; i <= n; i++)
  9.         for (int j = 1; j <= n + 1; j++)
  10.             scanf("%lf", &a[i][j]);
  11. }
  12. void solve() {
  13.     for (int j = 1; j <= n; j++) {
  14.         int mxp = j;
  15.         for (int i = j + 1; i <= n; i++)
  16.             if (fabs(a[i][j]) > fabs(a[mxp][j])) mxp = i;
  17.         for (int i = 1; i <= n + 1; i++)
  18.             swap(a[j][i], a[mxp][i]);
  19.         if (a[j][j] == 0) {
  20.             printf("No Solution\n");
  21.             return ;
  22.         }
  23.         for (int i = 1; i <= n; i++) {
  24.             if (i == j) continue;
  25.             double tmp = a[i][j] / a[j][j];
  26.             for (int k = 1; k <= n + 1; k++)
  27.                 a[i][k] -= a[j][k] * tmp;
  28.         }
  29.     }
  30.     for (int i = 1; i <= n; i++)
  31.         printf("%.2lf\n", a[i][n + 1] / a[i][i]);
  32. }
  33. int main() {
  34.     init();
  35.     solve();
  36.     return 0;
  37. }

primitive_root.cpp - MATH

  1. // 原根
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. const int N = 1000010;
  5. int p[N], tot, phi[N]; // p[] 素数，phi[] 欧拉函数
  6. bool v[N], has[N]; // v[] 是否是素数, is[] 是否有原根
  7. int Ts;
  8. typedef long long ll;
  9. ll fpow(ll a, ll b, ll p) {ll r = 1; for (; b; b >>= 1, a = (a * a) % p) if (b & 1) r = (r * a) % p; return r;}
  10. int gcd(int a, int b) {return !b ? a : gcd(b, a % b);}
  11. void init(int n) { // 预处理欧拉函数，素数，及那些数有原根
  12.     phi[1] = 1;
  13.     for (int i = 2; i <= n; ++i) {
  14.         if (!v[i]) p[++tot] = i, phi[i] = i - 1;
  15.         for (int j = 1; j <= tot && p[j]*i <= n; ++j) {
  16.             v[p[j]*i] = 1;
  17.             if (i % p[j] == 0) {
  18.                 phi[i * p[j]] = phi[i] * p[j];
  19.                 break;
  20.             }
  21.             phi[i * p[j]] = phi[i] * (p[j] - 1);
  22.         }
  23.     }
  24.     has[2] = has[4] = 1;
  25.     for (int i = 2; i <= tot; ++i) for (ll j = p[i]; j <= n; j *= p[i]) has[j] = 1, (j * 2 <= n)
  26.                     && (has[j * 2] = 1);
  27. }
  28. void devide(int x, vector<int> &ret) { // 分解质因数
  29.     ret.clear();
  30.     for (int i = 1; 1ll * p[i]*p[i] <= x; ++i) if (x % p[i] == 0) {
  31.             ret.push_back(p[i]);
  32.             while (x % p[i] == 0) x /= p[i];
  33.         }
  34.     if (x > 1) ret.push_back(x);
  35. }
  36. bool hasroot(int n) { // 判断一个数是否有原根
  37.     if (n == 2 || n == 4) return 1;
  38.     if (n % 2 == 0) n /= 2;
  39.     if (n % 2 == 0) return 0;
  40.     for (int i = 2; 1ll * p[i]*p[i] <= n; ++i) if (n % p[i] == 0) {
  41.             while (n % p[i] == 0) n /= p[i];
  42.             return (n == 1);
  43.         }
  44.     return 1;
  45. }
  46. void Getroot(int m, vector<int> &res) {
  47.     res.clear();
  48.     if (!has[m]) return ;
  49.     vector<int> factor;
  50.     devide(phi[m], factor);
  51.     int g = 1, mphi = phi[m];
  52.     while (true) {
  53.         bool fg = 1;
  54.         if (gcd(g, m) != 1) fg = 0; //i不存在模n的阶
  55.         else for (int i = 0; i < (int)factor.size(); ++i) {
  56.                 if (fpow(g, mphi / factor[i], m) == 1ll) {fg = 0; break;}
  57.             }
  58.         if (fg) break;
  59.         ++g;
  60.     }
  61.     ll pw = 1;
  62.     for (int s = 1; (int)res.size() < phi[mphi]; ++s) {
  63.         pw = (pw * g) % m;
  64.         if (gcd(s, mphi) == 1) res.push_back(pw);
  65.     }
  66.     sort(res.begin(), res.end());
  67. }
  68. int main() {
  69.     init(1e6);
  70.     scanf("%d", &Ts);
  71.     while (Ts--) {
  72.         int n, d; // 找 n 的所有原根
  73.         scanf("%d%d", &n, &d);
  74.         vector<int> ans;
  75.         Getroot(n, ans);
  76.         printf("%d\n", (int)ans.size());
  77.         for (int i = d - 1; i < (int)ans.size(); i += d) printf("%d ", ans[i]);
  78.         printf("\n");
  79.     }
  80. }

simpson.cpp - MATH

  1. // 数值积分，自适应辛普森法
  2. #include <cmath>
  3. #include <cstdio>
  4. using namespace std;
  6. typedef double db;
  8. // 要计算的函数
  9. db f(db x) {
  10.     return x * x * x;
  11. }
  13. // 辛普森公式  = (r - l) / 6 * (f(l) + f(r) + 4f((l + r) / 2))
  14. db simpon(db l, db r) {
  15.     db mid = (l + r) / 2.0;
  16.     return (r - l) * (f(l) + f(r) + f(mid) * 4.0) / 6.0;
  17. }
  19. db simpon(db l, db r, db eps, db ans, int step) {
  20.     db mid = (l + r) / 2.0;
  21.     db fl = simpon(l, mid), fr = simpon(mid, r);
  22.     if (fabs(fl + fr - ans) <= 15.0 * eps && step < 0) return fl + fr + (fl + fr - ans) / 15.0;
  23.     return simpon(l, mid, eps / 2.0, fl, step - 1) + simpon(mid, r, eps / 2.0, fr, step - 1);
  24. }
  26. db calc(db l, db r, db eps) {
  27.     return simpon(l, r, eps, simpon(l, r), 12);
  28. }

stirling1row.cpp - MATH

  1. // 第一类斯特林数·行
  2. #include <algorithm>
  3. #include <cstdio>
  4. #include <iostream>
  5. #include <cstring>
  6. #define clr(f,n) memset(f,0,sizeof(long long)*(n))
  7. #define cpy(f,g,n) memcpy(f,g,sizeof(long long)*(n))
  8. #define _max(x,y) ((x>y)?x:y)
  9. #define _min(x,y) ((x<y)?x:y)
  10. #define MOD(x) ((x)<mod?(x):((x)%mod))
  11. using namespace std;
  12. typedef long long ll;
  13. template<typename _Tp>
  14. inline void red(_Tp &x) {
  15.     x = 0; bool fg = 0; char ch = getchar();
  16.     while (ch < '0' || ch > '9') {if (ch == '-') fg ^= 1; ch = getchar();}
  17.     while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (_Tp)(ch ^ 48), ch = getchar();
  18.     if (fg) x = -x;
  19. }
  20. template<typename _Tp> bool umax(_Tp &x, _Tp y) {return (x < y) ? (x = y, true) : (false);}
  21. template<typename _Tp> bool umin(_Tp &x, _Tp y) {return (x > y) ? (x = y, true) : (false);}
  22. const int N = (1 << 19);
  23. const int mod = 167772161;
  24. const int _G = 3;
  25. const int _iG = 55924054;
  26. int rev[N], rev_n;
  27. ll inv[N], ifac[N], fac[N];
  28. ll fpow(ll a, ll b = mod - 2) {
  29.     ll r = 1;
  30.     for (; b; b >>= 1, a = MOD(a * a)) if (b & 1) r = MOD(r * a);
  31.     return r;
  32. }
  33. void prerev(int n) {
  34.     if (rev_n == n) return ;
  35.     for (int i = 0; i < n; ++i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? (n >> 1) : 0);
  36.     rev_n = n;
  37. }
  38. void NTT(ll f[], int n, int fg) {
  39.     prerev(n);
  40.     for (int i = 0; i < n; ++i) if (i < rev[i]) swap(f[i], f[rev[i]]);
  41.     for (int h = 2; h <= n; h <<= 1) {
  42.         int len = h >> 1;
  43.         ll Dt = fpow((fg == 1) ? _G : _iG, (mod - 1) / h), w;
  44.         for (int j = 0; j < n; j += h) { // j<n !! not j<=n
  45.             w = 1;
  46.             for (int k = j; k < j + len; ++k) {
  47.                 ll tt = MOD(w * f[k + len]);
  48.                 f[k + len] = f[k] - tt; (f[k + len] < 0) &&(f[k + len] += mod);
  49.                 f[k] = f[k] + tt; (f[k] >= mod) &&(f[k] -= mod);
  50.                 w = MOD(w * Dt);
  51.             }
  52.         }
  53.     }
  54.     if (fg == -1) {
  55.         ll invn = fpow(n, mod - 2);
  56.         for (int i = 0; i < n; ++i) f[i] = MOD(f[i] * invn);
  57.     }
  58. }
  60. ll S1[N];
  61. int n;
  62. // change f(x) to f(x+n)
  63. void change(ll f[], int n) {
  64.     static ll g[N];
  65.     int nn;
  66.     for (nn = 1; nn < (2 * n + 2); nn <<= 1) ;
  67.     clr(g, nn); clr(f + n + 1, nn - n - 1);
  68.     for (int i = 0; i <= n; ++i) f[i] = MOD(f[i] * fac[i]);
  69.     for (int i = 0, pw = 1; i <= n; ++i, pw = MOD((ll)pw * n)) g[n - i] = MOD((ll)pw * ifac[i]);
  70.     NTT(f, nn, 1); NTT(g, nn, 1);
  71.     for (int i = 0; i < nn; ++i) f[i] = MOD(f[i] * g[i]);
  72.     NTT(f, nn, -1);
  73.     for (int i = 0; i <= n; ++i)
  74.         f[i] = MOD(f[i + n] * ifac[i]);
  75.     clr(f + n + 1, nn - n - 1);
  76. }
  78. void GetS1(ll f[], int n) {
  79.     static int stk[50], top;
  80.     static ll g[N];
  81.     top = 0;
  82.     while (n) stk[++top] = n, n >>= 1;
  83.     clr(f, n << 1); f[1] = 1;
  84.     for (int tt = top - 1; tt >= 1; --tt) {
  85.         int now = stk[tt], len = stk[tt + 1], nn;
  86.         cpy(g, f, len + 1);
  87.         change(g, len);
  88.         for (nn = 1; nn < (len * 2 + 2); nn <<= 1) ;
  89.         NTT(f, nn, 1); NTT(g, nn, 1);
  90.         for (int i = 0; i < nn; ++i) f[i] = MOD(f[i] * g[i]);
  91.         NTT(f, nn, -1);
  92.         if ((len << 1) + 1 == now) {
  93.             // * (x+now-1)
  94.             for (int i = now; i >= 0; --i) {
  95.                 f[i + 1] = MOD(f[i + 1] + f[i]);
  96.                 f[i] = MOD(f[i] * (now - 1));
  97.             }
  98.         }
  99.     }
  100. }
  102. int main() {
  103.     red(n);
  104.     fac[0] = fac[1] = inv[0] = inv[1] = ifac[0] = ifac[1] = 1;
  105.     for (int i = 2; i <= n + 1; ++i) fac[i] = MOD(fac[i - 1] * i);
  106.     for (int i = 2; i <= n + 1; ++i) inv[i] = MOD((mod - mod / i) * inv[mod % i]);
  107.     for (int i = 2; i <= n + 1; ++i) ifac[i] = MOD(ifac[i - 1] * inv[i]);
  108.     GetS1(S1, n);
  109.     for (int i = 0; i <= n; ++i)
  110.         printf("%lld ", S1[i]);
  111.     printf("\n");
  112.     return 0;
  113. }
  114. /*
  115. 生活不止眼前的 OI
  116. 还有 逻辑 与 并行
  117. */

stirling2row.cpp - MATH

  1. // 第二类斯特林数·行
  2. #include <algorithm>
  3. #include <cstdio>
  4. #include <iostream>
  5. #define _max(x,y) ((x>y)?x:y)
  6. #define _min(x,y) ((x<y)?x:y)
  7. #define MOD(x) ((x)<mod?(x):((x)%mod))
  8. using namespace std;
  9. typedef long long ll;
  10. template<typename _Tp>
  11. inline void red(_Tp &x) {
  12.     x = 0; bool fg = 0; char ch = getchar();
  13.     while (ch < '0' || ch > '9') {if (ch == '-') fg ^= 1; ch = getchar();}
  14.     while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (_Tp)(ch ^ 48), ch = getchar();
  15.     if (fg) x = -x;
  16. }
  17. template<typename _Tp> bool umax(_Tp &x, _Tp y) {return (x < y) ? (x = y, true) : (false);}
  18. template<typename _Tp> bool umin(_Tp &x, _Tp y) {return (x > y) ? (x = y, true) : (false);}
  19. const int N = (1 << 19);
  20. const int mod = 167772161;
  21. const int _G = 3;
  22. const int _iG = 55924054;
  23. int rev[N], rev_n;
  24. ll inv[N], ifac[N], fac[N];
  25. ll S2[N], f[N], g[N];
  27. ll fpow(ll a, ll b = mod - 2) {
  28.     ll r = 1;
  29.     for (; b; b >>= 1, a = MOD(a * a)) if (b & 1) r = MOD(r * a);
  30.     return r;
  31. }
  32. void prerev(int n) {
  33.     if (rev_n == n) return ;
  34.     for (int i = 0; i < n; ++i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? (n >> 1) : 0);
  35.     rev_n = n;
  36. }
  37. void NTT(ll f[], int n, int fg) {
  38.     prerev(n);
  39.     for (int i = 0; i < n; ++i) if (i < rev[i]) swap(f[i], f[rev[i]]);
  40.     for (int h = 2; h <= n; h <<= 1) {
  41.         int len = h >> 1;
  42.         ll Dt = fpow((fg == 1) ? _G : _iG, (mod - 1) / h), w;
  43.         for (int j = 0; j < n; j += h) { // j<n !! not j<=n
  44.             w = 1;
  45.             for (int k = j; k < j + len; ++k) {
  46.                 ll tt = MOD(w * f[k + len]);
  47.                 f[k + len] = f[k] - tt; (f[k + len] < 0) &&(f[k + len] += mod);
  48.                 f[k] = f[k] + tt; (f[k] >= mod) &&(f[k] -= mod);
  49.                 w = MOD(w * Dt);
  50.             }
  51.         }
  52.     }
  53.     if (fg == -1) {
  54.         ll invn = fpow(n, mod - 2);
  55.         for (int i = 0; i < n; ++i) f[i] = MOD(f[i] * invn);
  56.     }
  57. }
  60. int n, k, nn;
  61. int main() {
  62.     red(n);
  63.     fac[0] = fac[1] = inv[0] = inv[1] = ifac[0] = ifac[1] = 1;
  64.     for (int i = 2; i <= n; ++i) fac[i] = MOD(fac[i - 1] * i);
  65.     for (int i = 2; i <= n; ++i) inv[i] = MOD((mod - mod / i) * inv[mod % i]);
  66.     for (int i = 2; i <= n; ++i) ifac[i] = MOD(ifac[i - 1] * inv[i]);
  67.     for (int k = 0; k <= n; ++k) {
  68.         f[k] = ifac[k];
  69.         if (k & 1) f[k] = MOD(mod - f[k]);
  70.         g[k] = MOD(ifac[k] * fpow(k, n));
  71.     }
  72.     for (nn = 1; nn < (n * 2 + 2); nn <<= 1) ;
  73.     NTT(f, nn, 1); NTT(g, nn, 1);
  74.     for (int i = 0; i < nn; ++i) S2[i] = MOD(f[i] * g[i]);
  75.     NTT(S2, nn, -1);
  76.     for (int i = 0; i <= n; ++i) printf("%lld ", S2[i]);
  77.     printf("\n");
  78.     return 0;
  79. }

MISC

chk.cpp - MISC

  1. #include <windows.h>
  2. #include <cstdio>
  3. #include <string>
  4. #include <cstring>
  5. #include <ctime>
  6. using namespace std;
  7. string tmp;
  9. int st;
  10. void setclock() {st = clock();}
  11. int getclock() {return clock() - st;}
  13. int ifcpl = 1, test_times = 1e9;
  14. string comd = "-std=c++11 -Wall -O2";
  16. void PrintHelp() {
  17.     printf("Uesge:\n");
  18.     printf("\tchk <std.cpp> <test.cpp> <mker.cpp> [-t (test-times)] [-q | -c <commond>]\n");
  19.     printf("-t (test-times) : run test for (test-times) times\n");
  20.     printf("-q              : without compile\n");
  21.     printf("-c <commond>    : commonds for compile\n");
  22.     exit(1);
  23. }
  24. void Genarg(int argc, char const *argv[]) {
  25.     if (argc < 4) PrintHelp();
  26.     for (int i = 4; i < argc; ++i) {
  27.         if (strcmp(argv[i], "-q") == 0) ifcpl = 0;
  28.         else if (strcmp(argv[i], "-t") == 0) {
  29.             ++i;
  30.             if (i >= argc) PrintHelp();
  31.             test_times = atoi(argv[i]);
  32.         } else if (strcmp(argv[i], "-c") == 0) {
  33.             ++i;
  34.             if (i >= argc) PrintHelp();
  35.             comd = argv[i];
  36.         } else PrintHelp();
  37.     }
  38. }
  40. int main(int argc, char const *argv[]) {
  41.     Genarg(argc, argv);
  42.     printf("total: %d test\n", test_times);
  43.     if (ifcpl) {
  44.         int fg = 0;
  45.         printf("building...\n");
  46.         tmp = "g++ " + string(argv[1]) + " -o .std " + comd; fg |= system(tmp.c_str());
  47.         tmp = "g++ " + string(argv[2]) + " -o .tst " + comd; fg |= system(tmp.c_str());
  48.         tmp = "g++ " + string(argv[3]) + " -o .mk " + comd; fg |= system(tmp.c_str());
  49.         if (fg) {
  50.             printf("complie error!\n");
  51.             return 2;
  52.         } else
  53.             printf("completed!\n");
  54.     }
  55.     for (int t = 1; t <= test_times; ++t) {
  56.         printf("test #%d\n", t);
  57.         system(".mk > .in.txt");
  58.         int Tstd, Ttst;
  59.         setclock(); system(".std < .in.txt > .ans.txt"); Tstd = getclock(); printf("std: %dms ", Tstd);
  60.         setclock(); system(".tst < .in.txt > .out.txt"); Ttst = getclock(); printf("tst: %dms\n", Ttst);
  61.         if (system("fc .ans.txt .out.txt")) {
  62.             printf("Wrong Answer !\n");
  63.             getchar();
  64.         }
  65.     }
  66.     return 0;
  67. }

debuger.h - MISC

  1. #include <bits/stdc++.h>
  3. #ifndef DEBUGER
  4. #define DEBUGER
  6. #ifdef DEBUG
  7. #define see(a) cerr<<#a<<" = "<<a<<" "
  8. #define seeln(a) cerr<<#a<<" = "<<a<<endl
  9. #define put(a) cerr<<a
  10. #define outarr(_a,_l,_r) for(int _i=(_l);_i<=(_r);_i++) cerr<<#_a"["<<_i<<"]="<<_a[_i]<<" ";cerr<<endl;
  11. #define Outarr(_a,_l,_r) cerr<<#_a<<" ["<<_l<<", "<<_r<<"] : "; for(int i=(_l);i<=(_r);++i) cerr<<_a[i]<<" ";cerr<<endl;
  12. #define out(a) cerr<<a<<" "
  13. #define outln(a) cerr<<a<<endl
  14. #else
  15. #define see(a) ;
  16. #define seeln(a) ;
  17. #define put(a);
  18. #define outarr(_a,_l,_r) ;
  19. #define Outarr(_a,_l,_r) ;
  20. #define out(a) ;
  21. #define outln(a) ;
  22. #endif
  24. using namespace std;
  26. template<typename Tp>
  27. ostream &operator<<(ostream &out, vector<Tp> vt) {
  28.     out << "vector of size = " << vt.size() << " : { " ;
  29.     for (size_t i = 0; i < vt.size(); ++i) out << vt[i] << ", ";
  30.     return out << "} ";
  31. }
  32. template<typename Tp>
  33. istream &operator>>(istream &in, vector<Tp> &vt) {
  34.     for (size_t i = 0; i < vt.size(); ++i) in >> vt[i];
  35.     return in;
  36. }
  37. template<typename Tp>
  38. ostream &operator<<(ostream &out, set<Tp> st) {
  39.     out << "set of size = " << st.size() << " : { " ;
  40.     for (auto it = st.begin(); it != st.end(); ++it) out << *it << ", ";
  41.     return out << "} ";
  42. }
  43. template<typename Tp>
  44. ostream &operator<<(ostream &out, multiset<Tp> st) {
  45.     out << "multiset of size = " << st.size() << " : { " ;
  46.     for (auto it = st.begin(); it != st.end(); ++it) out << *it << ", ";
  47.     return out << "} ";
  48. }
  49. template<typename Tp1, typename Tp2>
  50. ostream &operator<<(ostream &out, map<Tp1, Tp2> mp) {
  51.     out << "map of size = " << mp.size() << " : { " ;
  52.     for (auto it = mp.begin(); it != mp.end(); ++it)
  53.         out << "\"" << it->first << "\": " << it->second << ", ";
  54.     return out << "} ";
  55. }
  56. template<typename Tp1, typename Tp2>
  57. ostream &operator<<(ostream &out, pair<Tp1, Tp2> P) {
  58.     return out << "(" << P.first << ", " << P.second << ")";
  59. }
  61. #endif

fastIO.h - MISC

  1. #include <iostream>
  2. #include <cstdio>
  4. #ifndef FASTIO
  5. #define FASTIO
  7. class myin {
  8.   private:
  9.     static const int MAX = 1 << 20;
  10.     char buf[MAX], *p1 = buf, *p2 = buf;
  11.     inline char gc() {
  12. #ifdef DEBUG
  13.         return getchar();
  14. #endif
  15.         if (p1 != p2) return *p1++;
  16.         p1 = buf; p2 = p1 + fread(buf, 1, MAX, stdin); return (p1 == p2) ? (EOF) : (*p1++);
  17.     }
  18.   public:
  19.     myin &operator>>(char *s) {
  20.         char ch = gc();
  21.         while (ch == '\n' || ch == '\r' || ch == ' ') ch = gc();
  22.         while (ch != '\n' && ch != '\r' && ch != ' ') *s++ = ch, ch = gc();
  23.         *s = '\0';
  24.         return *this;
  25.     }
  26.     template <typename Tp>
  27.     myin &operator>>(Tp &x) {
  28.         x = 0; char ch = gc(); bool f = 0;
  29.         while (ch < '0' || ch > '9') {(ch == '-') &&(f ^= 1); ch = gc();}
  30.         while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (Tp)(ch ^ 48), ch = gc();
  31.         if (f)(x = -x);
  32.         return *this;
  33.     }
  34.     myin &operator>>(double &x) {
  35.         x = 0; bool f = 0; char ch = gc();
  36.         while (ch < '0' || ch > '9') {(ch == '-') &&(f ^= 1); ch = gc();}
  37.         while (ch >= '0' && ch <= '9') x = x * 10 + (double)(ch ^ 48), ch = gc();
  38.         if (ch == '.') {
  39.             ch = gc(); double e = 0.1;
  40.             while (ch >= '0' && ch <= '9') x = x + e * (double)(ch ^ 48), e *= 0.1, ch = gc();
  41.         }
  42.         if (f) x = -x;
  43.         return *this;
  44.     }
  45. } fin;
  47. class myout {
  48.   private:
  49.     static const int MAX = 1 << 20;
  50.     char buf[MAX], *p1 = buf, *p2 = buf + MAX;
  51.     char dbform[10] = "%.6lf";
  52.     inline void pc(const char c) {
  53. #ifdef DEBUG
  54.         putchar(c); return ;
  55. #endif
  56.         if (p1 != p2) *p1++ = c;
  57.         else {fwrite(buf, p1 - buf, 1, stdout); p1 = buf; *p1++ = c;}
  58.     }
  59.     template <typename _Tp> void write(_Tp x) {
  60.         if (x < 0) x = -x, pc('-');
  61.         if (x >= (_Tp)10) write(x / 10);
  62.         pc(x % 10 + '0');
  63.     }
  64.   public:
  65.     void flush() {fwrite(buf, p1 - buf, 1, stdout); p1 = buf;}
  66.     myout &operator<<(const char *s) { for (const char *p = s; *p; ++p) pc(*p); return *this;}
  67.     myout &operator<<(char *s) { for (char *p = s; *p; ++p) pc(*p); return *this;}
  68.     myout &operator<<(const char s) {pc(s); return *this;}
  69.     template <typename Tp> myout &operator<<(Tp x) {write(x); return *this;}
  70.     myout &operator<<(myout & (*__pf)(myout &)) {return __pf(*this);}
  71.     void setpoint(int n) {
  72.         sprintf(dbform + 1, ".%dlf", n);
  73.     }
  74.     myout &operator<<(double x) {
  75.         static char num[100];
  76.         sprintf(num, dbform, x);
  77.         return *this << num;
  78.     }
  79. } fout;
  81. inline myout &edl(myout &out) {out << "\n"; out.flush(); return out;}
  83. #endif

fast_io.cpp - MISC

  1. #include <cstdio>
  3. namespace IO {
  4.     const int MAX = 1 << 20;
  5.     char buf[MAX], Buf[MAX], * p1 = buf, * p2 = buf, * P1 = Buf, * P2 = Buf + MAX;
  6.     inline char gc() {
  7. #ifdef DEBUG
  8.         return getchar();
  9. #endif
  10.         if (p1 != p2) return *p1++;
  11.         p1 = buf; p2 = p1 + fread(buf, 1, MAX, stdin); return (p1 == p2) ? (EOF) : (*p1++);
  12.     }
  13.     inline void pc(const char c) {
  14. #ifdef DEBUG
  15.         return putchar(c), void();
  16. #endif
  17.         if (P1 != P2) *P1++ = c;
  18.         else { fwrite(Buf, P1 - Buf, 1, stdout); P1 = Buf; *P1++ = c; }
  19.     }
  20.     void readstr(char *s, bool fg = 0) { // fg=1 for getline
  21.         char ch = gc();
  22.         while (ch == '\n' || ch == '\r' || (!fg && ch == ' ')) ch = gc();
  23.         while (ch != '\n' && ch != '\r' && (fg || ch != ' ')) *s++ = ch, ch = gc();
  24.         *s = '\0';
  25.     }
  26.     void writestr(const char *s, char ch = '\0') { for (const char *p = s; *p; ++p) pc(*p); (ch != '\0') &&(pc(ch), 1); }
  27.     template <typename _Tp> void read(_Tp &x) {
  28.         x = 0; char ch = gc(); int f = 0;
  29.         while (ch < '0' || ch > '9') { (ch == '-') &&(f ^= 1); ch = gc(); }
  30.         while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (_Tp)(ch ^ 48), ch = gc();
  31.         f &&(x = -x);
  32.     }
  33.     template<typename Tp, typename... Args>void read(Tp &t, Args &... args) { read(t); read(args...); }
  34.     template<typename Tp> void write(Tp x, char ch = '\n') {
  35.         static int buf[100], d;
  36.         if (x == 0)  pc('0');
  37.         else {
  38.             if (x < 0)  pc('-'), x = -x;
  39.             for (d = 0; x; x /= 10)  buf[++d] = x % 10 + 48;
  40.             while (d) pc((char)buf[d--]);
  41.         }
  42.         if (ch != '\0') pc(ch);
  43.     }
  44.     template <typename Tp, typename... Args> void write(Tp x, Args ...args) { write(x, ' '); write(args...); }
  45.     void flush() { fwrite(Buf, P1 - Buf, 1, stdout); P1 = Buf; }
  46.     struct _flusher {
  47.         ~_flusher() { flush(); }
  48.     } flusher;
  49. }
  50. using IO::read; using IO::write; using IO::readstr; using IO::writestr;
  52. int main() {
  53.     return 0;
  54. }

OFFLINE

twiceoffline.cpp - OFFLINE

  1. // 莫队二次离线
  2. #include <bits/stdc++.h>
  3. template <typename Tp>
  4. inline void read(Tp &x) {
  5.     x = 0; bool fg = 0; char ch = getchar();
  6.     while (ch < '0' || ch > '9') {
  7.         if (ch == '-') fg ^= 1;
  8.         ch = getchar();
  9.     }
  10.     while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (Tp)(ch ^ 48), ch = getchar();
  11.     if (fg) x = -x;
  12. }
  13. using namespace std;
  14. typedef long long ll;
  15. const int N = 100010;
  16. struct mds {
  17.     int l, r, id, fg;
  18. };
  19. vector<mds> mdl[N], mdr[N];
  20. vector<mds>::iterator mt;
  21. vector<int>::iterator it;
  22. int a[N], n, m, K;
  23. int L[N], R[N], t[N], bl[N], B;
  24. ll Fl[N], Fr[N], ans[N];
  25. bool cmp(int x, int y) {
  26.     if (bl[L[x]] == bl[L[y]]) return R[x] < R[y];
  27.     return L[x] < L[y];
  28. }
  29. void init() {
  30.     // init Fr,Fl
  31.     for (int i = 1; i < n; ++i) {
  32.         // Fr(i) = f([1,i],i+1)
  33.     }
  34.     for (int i = n - 1; i >= 1; --i) {
  35.         // Fl(i) = f([i+1,n],i)
  36.     }
  37.     for (int i = 2; i <= n; ++i) Fl[i] += Fl[i - 1], Fr[i] += Fr[i - 1];
  38. }
  39. void solve() {
  40.     for (int x = 1; x <= n; ++x) {
  41.         // updata(a[x])
  42.         for (mt = mdr[x].begin(); mt != mdr[x].end(); ++mt)
  43.             for (int i = mt->l; i <= mt->r; ++i) ans[mt->id] += mt->fg * (1/*query(a[i])*/);
  44.     }
  45.     for (int x = n; x >= 1; --x) {
  46.         // updata(a[x])
  47.         for (mt = mdl[x].begin(); mt != mdl[x].end(); ++mt)
  48.             for (int i = mt->l; i <= mt->r; ++i) ans[mt->id] += mt->fg * (1/*query(a[i])*/);
  49.     }
  50. }
  51. int main() {
  52.     read(n); read(m); read(K);
  53.     for (int i = 1; i <= n; ++i) read(a[i]);
  54.     B = sqrt(n);
  55.     for (int i = 1; i <= n; ++i) bl[i] = (i - 1) / B + 1;
  56.     for (int i = 1; i <= m; ++i) read(L[i]), read(R[i]), t[i] = i;
  57.     sort(t + 1, t + m + 1, cmp);
  58.     init();
  59.     int l = 1, r = 1;
  60.     for (int i = 1; i <= m; ++i) {
  61.         int id = t[i];
  62.         if (r < R[id]) {
  63.             ans[id] += Fr[R[id] - 1] - Fr[r - 1];
  64.             mdr[l - 1].push_back(mds{ r + 1, R[id], id, -1 }); r = R[id];
  65.         }
  66.         if (l > L[id]) {
  67.             ans[id] += Fl[l - 1] - Fl[L[id] - 1];
  68.             mdl[r + 1].push_back(mds{ L[id], l - 1, id, -1 }); l = L[id];
  69.         }
  70.         if (r > R[id]) {
  71.             ans[id] -= Fr[r - 1] - Fr[R[id] - 1];
  72.             mdr[l - 1].push_back(mds{ R[id] + 1, r, id, 1 }); r = R[id];
  73.         }
  74.         if (l < L[id]) {
  75.             ans[id] -= Fl[L[id] - 1] - Fl[l - 1];
  76.             mdl[r + 1].push_back(mds{ l, L[id] - 1, id, 1 }); l = L[id];
  77.         }
  78.     }
  79.     solve();
  80.     for (int i = 1; i <= m; ++i) ans[t[i]] += ans[t[i - 1]];
  81.     for (int i = 1; i <= m; ++i)
  82.         printf("%lld\n", ans[i]);
  83.     return 0;
  84. }

POLY

FFT.cpp - POLY

  1. /*
  2.     FFT 快速傅立叶变换
  3.     加法卷积
  4. */
  5. #include <bits/stdc++.h>
  6. #define _max(x,y) ((x>y)?x:y)
  7. #define _min(x,y) ((x<y)?x:y)
  8. using namespace std;
  9. typedef long long ll;
  10. template<typename _Tp>
  11. inline void red(_Tp &x) {
  12.     x = 0; bool fg = 0; char ch = getchar();
  13.     while (ch < '0' || ch > '9') {if (ch == '-') fg ^= 1; ch = getchar();}
  14.     while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (_Tp)(ch ^ 48), ch = getchar();
  15.     if (fg) x = -x;
  16. }
  17. template<typename _Tp> bool umax(_Tp &x, _Tp y) {return (x < y) ? (x = y, true) : (false);}
  18. template<typename _Tp> bool umin(_Tp &x, _Tp y) {return (x > y) ? (x = y, true) : (false);}
  19. typedef double db;
  20. const int N = 2097152;
  21. const db Pi = acos(-1);
  22. struct com {
  23.     db r, i;
  24.     com(): r(0), i(0) {}
  25.     com(db _r, db _i): r(_r), i(_i) {}
  26.     com(int n): r(cos(Pi * 2 / n)), i(sin(Pi * 2 / n)) {} // w_n^1
  27.     com operator+(const com &b)const {return com(r + b.r, i + b.i);}
  28.     com operator-(const com &b)const {return com(r - b.r, i - b.i);}
  29.     com operator*(const com &b)const {return com(r * b.r - i * b.i, i * b.r + r * b.i);}
  30. } A[N], B[N];
  31. int n, m, tot;
  32. namespace sol1 { // 分治版FFT
  33.     com sav[N];
  34.     // flag = 1 DFT  flag = -1 IDFT
  35.     void FFT(com *f, int n, int flag) {
  36.         if (n == 1) return ;
  37.         com *fl = f, *fr = f + n / 2, Dt(n), w(1, 0);
  38.         Dt.i *= flag;
  39.         for (int i = 0; i < n; ++i) sav[i] = f[i];
  40.         for (int i = 0; i < n / 2; ++i) fl[i] = sav[i << 1], fr[i] = sav[i << 1 | 1];
  41.         FFT(fl, n / 2, flag); FFT(fr, n / 2, flag);
  42.         for (int i = 0; i < n / 2; ++i) {
  43.             com tmp = w * fr[i];
  44.             sav[i] = fl[i] + tmp;
  45.             sav[i + n / 2] = fl[i] - tmp;
  46.             w = w * Dt;
  47.         }
  48.         for (int i = 0; i < n; ++i) f[i] = sav[i];
  49.     }
  50. }
  51. namespace sol2 { // 迭代版FFT （小常数）
  52.     int rev[N];
  53.     void FFT(com f[], int n, int fg) {
  54.         for (int i = 0; i < n; ++i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? (n >> 1) : 0);
  55.         for (int i = 0; i < n; ++i)(i < rev[i]) && (swap(f[i], f[rev[i]]), 1);
  56.         for (int h = 2; h <= n; h <<= 1) {
  57.             com Dt(h), w, tt; Dt.i *= fg;
  58.             int len = (h >> 1);
  59.             for (int j = 0; j < n; j += h) {
  60.                 w = com(1, 0);
  61.                 for (int k = j; k < j + len; ++k) {
  62.                     tt = f[k + len] * w;
  63.                     f[k + len] = f[k] - tt;
  64.                     f[k] = f[k] + tt;
  65.                     w = w * Dt;
  66.                 }
  67.             }
  68.         }
  69.     }
  70. }
  71. int main() {
  72.     red(n); red(m);
  73.     for (int i = 0; i <= n; ++i) scanf("%lf", &A[i].r);
  74.     for (int i = 0; i <= m; ++i) scanf("%lf", &B[i].r);
  75.     tot = n + m; n = ceil(log2(n + m + 2));  n = 1 << n;
  76.     using namespace sol2;
  77.     FFT(A, n, 1); FFT(B, n, 1);
  78.     for (int i = 0; i < n; ++i) A[i] = A[i] * B[i];
  79.     FFT(A, n, -1);
  80.     for (int i = 0; i <= tot; ++i) printf("%d ", (int)(A[i].r / n + 0.49));
  81.     puts("");
  82.     return 0;
  83. }

FMT_FWT.cpp - POLY

  1. /*
  2.     FMT/FWT 快速莫比乌斯/沃尔什变换
  3.     位运算卷积
  4. */
  5. #include <bits/stdc++.h>
  6. #define re register
  7. #define cpy(f,g,n) memcpy(f,g,sizeof(long long)*(n))
  8. #define clr(f,n) memset(f,0,sizeof(long long)*(n))
  9. #define out(f,n) for(int i=0;i<(n);++i) printf("%lld ",f[i]);puts("")
  10. #define MOD(x) ((x<mod)?(x):((x)%mod))
  11. template <typename T>
  12. inline void red(T &x) {
  13.     x = 0; bool f = 0; char ch = getchar();
  14.     while (ch < '0' || ch > '9') {if (ch == '-') f ^= 1; ch = getchar();}
  15.     while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (T)(ch ^ 48), ch = getchar();
  16.     if (f) x = -x;
  17. }
  18. using namespace std;
  19. typedef long long ll;
  20. const int N = 1 << 18;
  21. const int mod = 998244353;
  22. const int inv2 = 499122177;
  23. ll A[N], B[N], C[N], ta[N], tb[N]; int n;
  24. inline void FMT_OR(ll f[], int n, int fg) { // fg=1 for FMT ; fg=0 for IFMT
  25.     for (re int h = 2, k = 1; h <= n; h <<= 1, k <<= 1)
  26.         for (re int i = 0; i < n; i += h)
  27.             for (re int j = 0; j < k; ++j)
  28.                 f[i + j + k] = MOD(f[i + j + k] + f[i + j] * fg + mod);
  29. }
  30. inline void FMT_AND(ll f[], int n, int fg) { // fg=1 for FMT ; fg=0 for IFMT
  31.     for (re int h = 2, k = 1; h <= n; h <<= 1, k <<= 1)
  32.         for (re int i = 0; i < n; i += h)
  33.             for (re int j = 0; j < k; ++j)
  34.                 f[i + j] = MOD(f[i + j] + f[i + j + k] * fg + mod);
  35. }
  36. inline void FWT_XOR(ll f[], int n, int fg) { // fg=1 for FWT; fg=1/2(inv 2) for IFWT
  37.     ll t;
  38.     for (re int h = 2, k = 1; h <= n; h <<= 1, k <<= 1)
  39.         for (re int i = 0; i < n; i += h)
  40.             for (re int j = 0; j < k; ++j)
  41.                 t = f[i + j + k], f[i + j + k] = MOD(f[i + j] - t + mod), f[i + j] = MOD(f[i + j] + t),
  42.                                                  f[i + j] = MOD(f[i + j] * fg), f[i + j + k] = MOD(f[i + j + k] * fg);
  43. }
  44. void times(ll f[], ll g[], int n) {for (int i = 0; i < n; ++i) f[i] = MOD(f[i] * g[i]);}
  45. int main() {
  46.     red(n); n = 1 << n;
  47.     for (re int i = 0; i < n; ++i) red(A[i]);
  48.     for (re int i = 0; i < n; ++i) red(B[i]);
  49.     cpy(ta, A, n); cpy(tb, B, n); FMT_OR(ta, n, 1); FMT_OR(tb, n, 1); times(ta, tb, n); FMT_OR(ta, n, -1);
  50.     out(ta, n);
  51.     cpy(ta, A, n); cpy(tb, B, n); FMT_AND(ta, n, 1); FMT_AND(tb, n, 1); times(ta, tb, n); FMT_AND(ta, n, -1);
  52.     out(ta, n);
  53.     cpy(ta, A, n); cpy(tb, B, n); FWT_XOR(ta, n, 1); FWT_XOR(tb, n, 1); times(ta, tb, n); FWT_XOR(ta, n, inv2);
  54.     out(ta, n);
  55. }

lagrange.cpp - POLY

  1. // 拉格朗日插值法
  2. // L(x)=\sum_{j=0}^n y_j\prod_{i\ne j}\frac{x-x_i}{x_j-x_i}
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. typedef long long ll;
  6. const int N = 1000010;
  7. const int mod = 1e9 + 7;
  8. int n, k;
  10. ll fpow(ll a, ll b, ll p = mod) {
  11.     ll r = 1;
  12.     for (; b; b >>= 1, a = (a * a) % p) if (b & 1) r = (r * a) % p;
  13.     return r;
  14. }
  15. ll s[N], p[N], fac[N], inv[N], ifac[N];
  17. void init(int n) {
  18.     fac[0] = fac[1] = inv[0] = inv[1] = ifac[0] = ifac[1] = 1;
  19.     for (int i = 2; i <= n; ++i) fac[i] = fac[i - 1] * i % mod;
  20.     for (int i = 2; i <= n; ++i) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
  21.     for (int i = 2; i <= n; ++i) ifac[i] = ifac[i - 1] * inv[i] % mod;
  22. }
  24. ll lagrange(int n, ll k, ll x[], ll y[]) { // O(n^2)
  25.     ll r = 0;
  26.     for (int j = 0; j < n; ++j) {
  27.         ll P1 = 1, P2 = 1;
  28.         for (int i = 0; i < n; ++i) if (i != j) {
  29.                 P1 = (P1 * (k - x[i] + mod)) % mod;
  30.                 P2 = (P2 * (x[j] - x[i] + mod)) % mod;
  31.             }
  32.         r = (r + y[j] * P1 % mod * fpow(P2, mod - 2, mod) % mod) % mod;
  33.     }
  34.     return r;
  35. }
  37. ll lagrange_y(int n, ll k, ll y[]) { // 当 x_i = i (i in [0, n]) O(n)
  38.     init(n);
  39.     p[0] = 1;
  40.     for (int i = 0; i < n; ++i) p[i + 1] = p[i] * (k - i + mod) % mod;
  41.     s[n] = 1;
  42.     for (int i = n; i >= 1; --i) s[i - 1] = s[i] * (k - i + mod) % mod;
  43.     ll r = 0;
  44.     for (int j = 0; j <= n; ++j) {
  45.         ll tmp = p[j] * s[j] % mod * ifac[j] % mod * ifac[n - j] % mod;
  46.         r = (r + (ll)(((n - j) & 1) ? (mod - 1) : 1) * y[j] % mod * tmp % mod) % mod;
  47.     }
  48.     return r;
  49. }

NTT.cpp - POLY

  1. /*
  2.     NTT 快速数论变换
  3.     FFT的取模形式
  4. */
  5. #include <bits/stdc++.h>
  6. #define MOD(x) ((x<p)?(x):((x)%p))
  7. template <typename T>
  8. inline void red(T &x) {
  9.     x = 0; bool f = 0; char ch = getchar();
  10.     while (ch < '0' || ch > '9') {if (ch == '-') f ^= 1; ch = getchar();}
  11.     while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (T)(ch ^ 48), ch = getchar();
  12.     if (f) x = -x;
  13. }
  14. using namespace std;
  15. typedef long long ll;
  16. const int p = 998244353; // = 119*2^23+1 g=3 是其原根
  17. const int G = 3;
  18. const int invG = 332748118;
  19. const int N = 2097152;
  20. int n, m, rev[N], tot;
  21. ll A[N], B[N];
  22. // NTT 对模数有要求，如果 p = r*2^k+1 是素数，在 mod p 意义下可处理 2^k 以内数据
  23. // 与 FFT 的区别，单位根 w1 = g^((p-1)/n)
  24. ll fpow(ll a, ll b, ll p =::p) {ll r = 1; for (; b; b >>= 1, a = MOD(a * a)) if (b & 1) r = MOD(r * a); return r;}
  25. // fg=1 DFT fg=0 IDFT
  26. void NTT(ll f[], int n, bool fg) {
  27.     for (int i = 0; i < n;
  28.          ++i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? (n >> 1) : 0); // 可以放到外面预处理
  29.     for (int i = 0; i < n; ++i)(rev[i] < i) && (swap(f[i], f[rev[i]]), 1);
  30.     for (int h = 2; h <= n; h <<= 1) {
  31.         int len = h >> 1;
  32.         ll Dt = fpow(fg ? G : invG, (p - 1) / h), w;
  33.         for (int j = 0; j < n; j += h) {
  34.             w = 1;
  35.             for (int k = j; k < j + len; ++k) {
  36.                 ll tt = MOD(w * f[k + len]);
  37.                 f[k + len] = f[k] - tt; (f[k + len] < 0) &&(f[k + len] += p);
  38.                 f[k] = f[k] + tt; (f[k] > p) &&(f[k] -= p);
  39.                 w = MOD(w * Dt);
  40.             }
  41.         }
  42.     }
  43.     if (fg == 0) {
  44.         ll invn = fpow(n, p - 2);
  45.         for (int i = 0; i < n; ++i) f[i] = MOD(f[i] * invn);
  46.     }
  47. }
  48. int main() {
  49.     red(n); red(m);
  50.     for (int i = 0; i <= n; ++i) red(A[i]);
  51.     for (int i = 0; i <= m; ++i) red(B[i]);
  52.     tot = n + m + 1;
  53.     n = ceil(log2(n + m + 2)); n = 1 << n;
  54.     NTT(A, n, 1); NTT(B, n, 1);
  55.     for (int i = 0; i < n; ++i) A[i] = MOD(A[i] * B[i]);
  56.     NTT(A, n, 0);
  57.     for (int i = 0; i < tot; ++i) printf("%lld ", A[i]);
  58.     printf("\n");
  59. }

poly.cpp - POLY

  1. /*
  2.     NTT 多项式全家桶
  3.     p_mul 乘法; p_inv 求逆; p_div 带余数除法; p_sqrt 开方;
  4.     p_ln Ln； p_exp EXP; p_int 积分; p_der 求导; p_pow 快速幂;
  5.     DCFFT 分治 FFT 板子;
  7.     to be continue ...
  8.     多项式三角函数，多项式反三角函数，多项式多点求值，多项式快速差值.....
  9. */
  11. #include <algorithm>
  12. #include <iostream>
  13. #include <cstring>
  14. #include <cstdio>
  15. #include <cmath>
  16. #define clr(f,n) memset(f,0,sizeof(long long)*(n))
  17. #define cpy(f,g,n) memcpy(f,g,sizeof(long long)*(n))
  18. #define Outarr(x,n) cerr<<#x<<" : "; for(int i=0;i<n;++i) cerr<<x[i]<<" ";cout<<endl;
  19. #define outarr(x,n) for(int i=0;i<n;++i) printf("%lld%c",x[i],(i==n-1)?'\n':' ');
  20. #define MOD(x) ((x)<mod?(x):((x)%mod))
  21. using namespace std;
  22. template<typename _Tp>
  23. inline void red(_Tp &x) {
  24.     x = 0; bool fg = 0; char ch = getchar();
  25.     while (ch < '0' || ch > '9') {if (ch == '-') fg ^= 1; ch = getchar();}
  26.     while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (_Tp)(ch ^ 48), ch = getchar();
  27.     if (fg) x = -x;
  28. }
  29. typedef long long ll;
  31. namespace poly {
  32.     const int mod = 998244353;
  33.     const int N = (1 << 19);
  34.     const int _G = 3;
  35.     const int _iG = 332748118;
  36.     const int inv2 = 499122177;
  38.     ll fpow(ll a, ll b, ll p) {
  39.         ll r = 1;
  40.         for (; b; a = a * a % p, b >>= 1) if (b & 1) r = r * a % p;
  41.         return r;
  42.     }
  44.     int rev[N], rev_n;
  45.     void prerev(int n) {
  46.         if (n == rev_n) return;
  47.         rev_n = n;
  48.         for (int i = 0; i < n; ++i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? (n >> 1) : 0);
  49.     }
  50.     // NTT : fg=1 DFT fg=-1 IDFT
  51.     void NTT(ll f[], int n, int fg) {
  52.         prerev(n);
  53.         for (int i = 0; i < n; ++i) if (i < rev[i]) swap(f[i], f[rev[i]]);
  54.         for (int h = 2; h <= n; h <<= 1) {
  55.             ll Dt = fpow((fg == 1) ? _G : _iG, (mod - 1) / h, mod), w;
  56.             int len = h >> 1;
  57.             for (int j = 0; j < n; j += h) {
  58.                 w = 1;
  59.                 for (int k = j; k < j + len; ++k) {
  60.                     ll tmp = MOD(f[k + len] * w);
  61.                     f[k + len] = f[k] - tmp; (f[k + len] < 0) &&(f[k + len] += mod);
  62.                     f[k] = f[k] + tmp; (f[k] >= mod) &&(f[k] -= mod);
  63.                     w = MOD(w * Dt);
  64.                 }
  65.             }
  66.         }
  67.         if (fg == -1) {
  68.             ll invn = fpow(n, mod - 2, mod);
  69.             for (int i = 0; i < n; ++i) f[i] = MOD(f[i] * invn);
  70.         }
  71.     }
  72.     // f(x) = f*g(x) n = def f ; m = def g ; len = 最终长度(保留几位)
  73.     void p_mul(ll f[], ll g[], int n, int m, int len) {
  74.         static ll a[N], b[N];
  75.         int nn = 1 << (int)ceil(log2(n + m - 1));
  76.         clr(a, nn); clr(b, nn); cpy(a, f, n); cpy(b, g, m);
  77.         NTT(a, nn, 1); NTT(b, nn, 1);
  78.         for (int i = 0; i < nn; ++i) a[i] = MOD(a[i] * b[i]);
  79.         NTT(a, nn, -1);
  80.         for (int i = 0; i < len; ++i) f[i] = a[i];
  81.     }
  82.     // f(x) = g^-1(x)  f(x) 为 g(x) 模 x^n 意义下的逆
  83.     void p_inv(ll g[], int n, ll f[]) {
  84.         static ll sav[N];
  85.         int nn = 1 << (int)ceil(log2(n));
  86.         clr(f, n * 2);
  87.         f[0] = fpow(g[0], mod - 2, mod);
  88.         for (int h = 2; h <= nn; h <<= 1) {
  89.             cpy(sav, g, h); clr(sav + h, h);
  90.             NTT(sav, h << 1, 1); NTT(f, h << 1, 1);
  91.             for (int i = 0; i < (h << 1); ++i)
  92.                 f[i] = f[i] * (2ll - f[i] * sav[i] % mod + mod) % mod;
  93.             NTT(f, h << 1, -1); clr(f + h, h);
  94.         }
  95.         clr(f + n, nn * 2 - n);
  96.     }
  97.     // f^2(x) = g(x)  f(x) 为 g(x) 模 x^n 意义下的开方
  98.     void p_sqrt(ll g[], int n, ll f[]) {
  99.         static ll sav[N], r[N];
  100.         int nn = 1 << (int)ceil(log2(n));
  101.         clr(f, n * 2); f[0] = 1; // g[0] should be 1 otherwise
  102.         for (int h = 2; h <= nn; h <<= 1) {
  103.             cpy(sav, g, h); clr(sav + h, h); p_inv(f, h, r);
  104.             NTT(sav, h << 1, 1); NTT(r, h << 1, 1);
  105.             for (int i = 0; i < (h << 1); ++i) sav[i] = MOD(sav[i] * r[i]);
  106.             NTT(sav, h << 1, -1);
  107.             for (int i = 0; i < h; ++i) f[i] = MOD((f[i] + sav[i]) * inv2);
  108.             clr(f + h, h);
  109.         }
  110.         clr(f + n, nn * 2 - n);
  111.     }
  112.     // f(x) = g(x) * q(x) + r(x) : q(x) 为商 r(x) 为余数
  113.     void p_div(ll f[], ll g[], int n, int m, ll q[], ll r[]) {
  114.         static ll sav1[N], sav2[N];
  115.         int nn;
  116.         for (nn = 1; nn < n - m + 1; nn <<= 1);
  117.         clr(sav1, nn); clr(sav2, nn); cpy(sav1, f, n); cpy(sav2, g, m);
  118.         reverse(sav1, sav1 + n); reverse(sav2, sav2 + m);
  119.         p_inv(sav2, n - m + 1, q); p_mul(q, sav1, n - m + 1, n, n - m + 1);
  120.         reverse(q, q + n - m + 1);  cpy(r, g, m);
  121.         p_mul(r, q, m, n - m + 1, m - 1);
  122.         for (int i = 0; i < m - 1; ++i) r[i] = MOD(f[i] - r[i] + mod);
  123.     }
  124.     // 预处理乘法逆元
  125.     ll inv[N];
  126.     void Initinv(int n) {
  127.         inv[0] = inv[1] = 1;
  128.         for (int i = 2; i <= n; ++i) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
  129.     }
  130.     // 对 f(x) 进行积分  Initinv() first
  131.     void p_int(ll f[], int n) {
  132.         for (int i = n - 1; i; --i) f[i] = MOD(f[i - 1] * inv[i]);
  133.         f[0] = 0;
  134.     }
  135.     // 对 f(x) 进行求导
  136.     void p_der(ll f[], int n) {
  137.         for (int i = 1; i < n; ++i) f[i - 1] = MOD(f[i] * i);
  138.         f[n - 1] = 0;
  139.     }
  140.     //  f(x) <- ln f(x)  f[0] should be 1
  141.     void p_ln(ll f[], int n) {
  142.         static ll g[N];
  143.         p_inv(f, n, g); p_der(f, n);
  144.         p_mul(f, g, n, n, n + n);
  145.         p_int(f, n);
  146.     }
  148.     // f(x) <- exp f(x) (倍增版) f[0] should be 0
  149.     void p_exp(ll f[], int n) {
  150.         static ll g[N], sav[N];
  151.         clr(g, n * 2); clr(sav, n * 2); g[0] = 1;
  152.         for (int h = 2; h <= n; h <<= 1) {
  153.             cpy(sav, g, h); p_ln(sav, h);
  154.             for (int i = 0; i < h; ++i) sav[i] = MOD(f[i] - sav[i] + mod);
  155.             sav[0] = MOD(sav[0] + 1);
  156.             p_mul(g, sav, h, h, h);
  157.         }
  158.         cpy(f, g, n);
  159.     }
  161.     /*
  162.     void _p_exp(ll f[],ll g[],int l,int r) {
  163.         static ll A[N],B[N];
  164.         if(r-l==1) {if(l>0) f[l]=MOD(f[l]*fpow(l,mod-2,mod));return ;}
  165.         int mid=(l+r)>>1,len=mid-l;
  166.         _p_exp(f,g,l,mid);
  167.         cpy(A,f+l,len); clr(A+len,len); cpy(B,g,len<<1);
  168.         p_mul(A,B,len<<1,len<<1,len<<1);
  169.         for(int i=mid;i<r;++i) f[i]=MOD(f[i]+A[i-l]);
  170.         _p_exp(f,g,mid,r);
  171.     }
  172.     // f(x) <- exp f(x) (分治 FFT 版) f[0] should be 0
  173.     void p_exp(ll f[],int n) {
  174.         static ll g[N];
  175.         cpy(g,f,n); clr(f,n); f[0]=1;
  176.         for(int i=0;i<n;++i) g[i]=MOD(g[i]*i);
  177.         _p_exp(f,g,0,n);
  178.     }
  179.     */
  181.     // f(x) <- f^k(x)  f(x) 模 x^n 意义下的 k 次
  182.     void p_pow(ll f[], int n, ll k) {
  183.         p_ln(f, n);
  184.         for (int i = 0; i < n; ++i) f[i] = MOD(f[i] * k);
  185.         p_exp(f, n);
  186.     }
  188.     // 分治FFT [l,r)   F[n] = sum(0<i<=n) F[n-i]G[i]
  189.     void DCFFT(ll f[], ll g[], int l, int r) {
  190.         static ll A[N], B[N];
  191.         if (r - l == 1) return ;
  192.         int mid = (l + r) >> 1, len = mid - l;
  193.         DCFFT(f, g, l, mid);
  194.         cpy(A, f + l, len); clr(A + len, len); cpy(B, g, len << 1);
  195.         p_mul(A, B, len << 1, len << 1, len << 1);
  196.         for (int i = mid; i < r; ++i) f[i] = MOD(f[i] + A[i - l]);
  197.         DCFFT(f, g, mid, r);
  198.     }
  199. }
  200. using namespace poly;
  202. int main() {
  203.     return 0;
  204. }

STRING

ACAM.cpp - STRING

  1. // AC 自动机，字符串多模式串匹配
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. namespace ACAM {
  5.     const int MAX = 200010;
  6.     int tr[MAX][26], fail[MAX], sz;
  7.     int tag[MAX];
  8.     void init() {
  9.         memset(tr[0], 0, sizeof(tr[0]));
  10.         fail[0] = 0; sz = 0;
  11.     }
  12.     int newnode() {
  13.         ++sz; fail[sz] = 0; memset(tr[sz], 0, sizeof(tr[sz]));
  14.         return sz;
  15.     }
  16.     int insert(string &s) {
  17.         int p = 0, c;
  18.         for (int i = 0; i < s.size(); ++i) {
  19.             c = s[i] - 'a';
  20.             if (tr[p][c] == 0) tr[p][c] = newnode();
  21.             p = tr[p][c];
  22.         }
  23.         return p;
  24.     }
  25.     void build() {
  26.         queue<int> q;
  27.         for (int i = 0; i < 26; ++i) {
  28.             if (tr[0][i]) q.push(tr[0][i]);
  29.         }
  30.         while (!q.empty()) {
  31.             int u = q.front(); q.pop();
  32.             for (int i = 0; i < 26; ++i) {
  33.                 if (tr[u][i]) fail[tr[u][i]] = tr[fail[u]][i], q.push(tr[u][i]);
  34.                 else tr[u][i] = tr[fail[u]][i];
  35.             }
  36.         }
  37.     }
  38.     void query(string &s) {
  39.         int cur = 0, c;
  40.         for (int i = 0; i <= sz; ++i) tag[i] = 0;
  41.         for (int i = 0; i < s.size(); ++i) {
  42.             c = s[i] - 'a';
  43.             cur = tr[cur][c];
  44.             tag[cur]++;
  45.         }
  46.     }
  47.     void work() {
  48.         static int idg[MAX];
  49.         for (int i = 0; i <= sz; ++i) idg[i] = 0;
  50.         for (int i = 1; i <= sz; ++i) ++idg[fail[i]];
  51.         queue<int> q;
  52.         for (int i = 1; i <= sz; ++i) if (idg[i] == 0) q.push(i);
  53.         while (!q.empty()) {
  54.             int u = q.front(); q.pop();
  55.             if (!u) break;
  56.             tag[fail[u]] += tag[u];
  57.             if (--idg[fail[u]] == 0) q.push(fail[u]);
  58.         }
  59.     }
  60. }
  61. int n, ed[200005];
  62. string P[200005], T;
  63. int main() {
  64.     cin >> n;
  65.     ACAM::init();
  66.     for (int i = 0; i < n; ++i)
  67.         cin >> P[i], ed[i] = ACAM::insert(P[i]);
  68.     ACAM::build();
  69.     cin >> T;
  70.     ACAM::query(T);
  71.     ACAM::work();
  72.     for (int i = 0; i < n; ++i)
  73.         cout << ACAM::tag[ed[i]] << "\n";
  74.     return 0;
  75. }

EXSAM.cpp - STRING

  1. // EXSAM 广义后缀自动机
  2. #include <bits/stdc++.h>
  3. template<typename _Tp>
  4. inline void read(_Tp &x) {
  5.     x = 0; bool fg = 0; char ch = getchar();
  6.     while (ch < '0' || ch > '9') {if (ch == '-') fg ^= 1; ch = getchar();}
  7.     while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (_Tp)(ch ^ 48), ch = getchar();
  8.     if (fg) x = -x;
  9. }
  10. template<typename _Tp, typename... Args>void read(_Tp &t, Args &... args) {read(t); read(args...);}
  11. using namespace std;
  12. typedef long long ll;
  13. typedef pair<int, int> P;
  14. const int N = 1000010;
  15. namespace EXSAM {
  16.     const int MAX = 2000010;
  17.     struct sta {
  18.         int len, link;
  19.         int nxt[26];
  20.         int &operator[](const int k) {return nxt[k];}
  21.     } st[MAX];
  22.     int sz;
  23.     void init() {
  24.         sz = 1; st[0].link = -1;
  25.     }
  26.     void _extend(int last, int c) {
  27.         int cur = st[last][c], p = st[last].link; st[cur].len = st[last].len + 1;
  28.         while (p != -1 && st[p][c] == 0) {
  29.             st[p][c] = cur; p = st[p].link;
  30.         }
  31.         if (p == -1) st[cur].link = 0;
  32.         else {
  33.             int q = st[p][c];
  34.             if (st[q].len == st[p].len + 1) st[cur].link = q;
  35.             else {
  36.                 int cp = sz++; st[cp].len = st[p].len + 1; st[cp].link = st[q].link;
  37.                 for (int i = 0; i < 26; ++i) st[cp][i] = (st[st[q][i]].len == 0) ? 0 : st[q][i];
  38.                 st[cur].link = st[q].link = cp;
  39.                 while (p != -1 && st[p][c] == q) {
  40.                     st[p][c] = cp;
  41.                     p = st[p].link;
  42.                 }
  43.             }
  44.         }
  45.     }
  46.     void build() {
  47.         queue<P> q;
  48.         for (int i = 0; i < 26; ++i) if (st[0][i] != 0) q.push(P(0, i));
  49.         while (!q.empty()) {
  50.             P u = q.front(); q.pop();
  51.             _extend(u.first, u.second);
  52.             int o = st[u.first][u.second];
  53.             for (int i = 0; i < 26; ++i) if (st[o][i] != 0) q.push(P(o, i));
  54.         }
  55.     }
  56.     void insert(char *s, int len) {
  57.         int cur = 0;
  58.         for (int i = 0; i < len; ++i) {
  59.             if (st[cur][s[i] - 'a'] == 0) st[cur][s[i] - 'a'] = sz++;
  60.             cur = st[cur][s[i] - 'a'];
  61.         }
  62.     }
  63.     ll solve() {
  64.         ll r = 0;
  65.         for (int i = 1; i < sz; ++i) r += st[i].len - st[st[i].link].len;
  66.         return r;
  67.     }
  68. }
  69. int n; char s[N];
  71. int main() {
  72.     read(n);
  73.     EXSAM::init();
  74.     for (int i = 1; i <= n; ++i) {
  75.         scanf("%s", s);
  76.         EXSAM::insert(s, strlen(s));
  77.     }
  78.     EXSAM::build();
  79.     printf("%lld\n", EXSAM::solve());
  80.     return 0;
  81. }

KMP.cpp - STRING

  1. // KMP
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. const int N = 1000010;
  5. char P[N], T[N];
  6. int nxt[N], f[N], n, m;
  7. void getnxt() {
  8.     nxt[1] = 0;
  9.     for (int i = 2, j = 0; i <= m; ++i) {
  10.         while (j > 0 && P[i] != P[j + 1]) j = nxt[j];
  11.         if (P[i] == P[j + 1]) ++j;
  12.         nxt[i] = j;
  13.     }
  14. }
  15. void KMP() {
  16.     for (int i = 1, j = 0; i <= n; ++i) {
  17.         while (j > 0 && (j == m || T[i] != P[j + 1])) j = nxt[j];
  18.         if (T[i] == P[j + 1]) ++j;
  19.         f[i] = j;
  20.     }
  21. }
  22. int main() {
  23.     scanf("%s%s", T + 1, P + 1);
  24.     n = strlen(T + 1), m = strlen(P + 1);
  25.     getnxt();
  26.     KMP();
  27.     for (int i = 1; i <= n; ++i) if (f[i] == m) printf("%d\n", i - m + 1);
  28.     for (int i = 1; i <= m; ++i) printf("%d%c", nxt[i], " \n"[i == m]);
  29.     return 0;
  30. }

manacher.cpp - STRING

  1. /*
  2.     manachar 马拉车算法
  3.     --> 线性求最长回文串
  4.     Oi-wiki(Manacher) --> https://oi-wiki.org/string/manacher/
  5. */
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8. const int N = 1.2e7;
  9. char s[N], str[N << 1];
  10. int p[N << 1];
  11. int manacher() {
  12.     int len = strlen(s), n = 0;
  13.     str[n++] = '$'; str[n++] = '#';
  14.     for (int i = 0; i < len; i++) str[n++] = s[i], str[n++] = '#'; str[n] = '\0';
  15.     int mr = 0, ans = 0, mid = 0;
  16.     for (int i = 1; i < n; i++) {
  17.         p[i] = i < mr ? min(p[2 * mid - i], mr - i) : 1;
  18.         while (str[i - p[i]] == str[i + p[i]]) p[i]++;
  19.         if (p[i] + i > mr) mr = p[i] + i, mid = i;
  20.         ans = max(ans, p[i]);
  21.     }
  22.     return ans - 1;
  23. }
  24. int main() {
  25.     scanf("%s", s);
  26.     printf("%d\n", manacher());
  27. }

minstr.cpp - STRING

  1. // 最小表示法
  2. #include <bits/stdc++.h>
  3. template<typename _Tp>
  4. inline void read(_Tp &x) {
  5.     x = 0; bool fg = 0; char ch = getchar();
  6.     while (ch < '0' || ch > '9') {if (ch == '-') fg ^= 1; ch = getchar();}
  7.     while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (_Tp)(ch ^ 48), ch = getchar();
  8.     if (fg) x = -x;
  9. }
  10. template<typename _Tp, typename... Args>void read(_Tp &t, Args &... args) {read(t); read(args...);}
  11. using namespace std;
  12. typedef long long ll;
  13. const int N = 300010;
  14. int a[N], n;
  15. int minstr(int s[], int n) {
  16.     int i = 0, j = 1, k = 0; // i,j 比较的两个循环串开头，k为当前相等长度
  17.     while (i < n && j < n && k < n) {
  18.         if (s[(i + k) % n] == s[(j + k) % n]) ++k;
  19.         else {
  20.             if (s[(i + k) % n] < s[(j + k) % n]) j += k + 1;
  21.             else i += k + 1;
  22.             // 若 s[i..k-1] == s[j..k-1] ,s[i+k]<s[j+k] 说明 j~j+k 都不可能成为最小循环串，
  23.             // 因为都有对应的 i~i+k 比其更小
  24.             if (i == j) ++j;
  25.             k = 0;
  26.         }
  27.     }
  28.     return min(i, j);
  29. }
  30. int main() {
  31.     read(n);
  32.     for (int i = 0; i < n; ++i) read(a[i]);
  33.     int ps = minstr(a, n);
  34.     printf("%d", a[ps]);
  35.     for (int i = (ps + 1) % n; i != ps; i = (i + 1) % n) printf(" %d", a[i]);
  36.     puts("");
  37.     return 0;
  38. }

PAM.cpp - STRING

  1. /*
  2.     PAM 回文自动机 / 回文树
  3.     luogu P5496 【模板】回文自动机（PAM）
  4.     Oi-wiki --> https://oi-wiki.org/string/pam/
  5. */
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8. const int N = 500010;
  9. namespace PAM {
  10.     int sz, tot, lst; // sz:状态数量 tot:字符串长度 lst:上次状态
  11.     int cnt[N], sum[N], ch[N][26], len[N], fail[N]; // cnt:该状态对应原串中出现次数
  12.     // fail 指针跳到该串最长后缀回文，sum 记录跳几次跳完
  13.     char s[N];
  14.     int newnode(int l) {
  15.         ++sz; memset(ch[sz], 0, sizeof(ch[sz]));
  16.         len[sz] = l; fail[sz] = cnt[sz] = sum[sz] = 0;
  17.         return sz;
  18.     }
  19.     void init() {
  20.         sz = -1; lst = 0; s[tot = 0] = '$';
  21.         newnode(0); newnode(-1); fail[0] = 1;
  22.     }
  23.     int getfail(int x) {
  24.         while (s[tot - len[x] - 1] != s[tot]) x = fail[x];
  25.         return x;
  26.     }
  27.     void insert(char c) {
  28.         s[++tot] = c;
  29.         int cur = getfail(lst);
  30.         if (!ch[cur][c - 'a']) {
  31.             int now = newnode(len[cur] + 2);
  32.             fail[now] = ch[getfail(fail[cur])][c - 'a'];
  33.             ch[cur][c - 'a'] = now;
  34.             sum[now] = sum[fail[now]] + 1;
  35.         }
  36.         ++cnt[lst];
  37.         lst = ch[cur][c - 'a'];
  38.     }
  39.     void calc() {for (int i = sz; i >= 0; --i) cnt[fail[i]] += cnt[i];} // 计算每个状态出现次数
  40. }
  41. char str[N];
  42. int k;
  43. int main() {
  44.     scanf("%s", str);
  45.     PAM::init();
  46.     for (char *ps = str; *ps; ++ps) {
  47.         *ps = (*ps - 97 + k) % 26 + 97;
  48.         PAM::insert(*ps);
  49.         k = PAM::sum[PAM::lst]; // 以 ps 位为结尾的回文串数量
  50.         printf("%d ", k);
  51.     }
  52.     printf("\n");
  53.     return 0;
  54. }

SA.cpp - STRING

  1. /*
  2.     后缀数组 (SA)
  3.     O(nlogn) 倍增做法，外加求 height 数组
  4.     Oi-wiki(后缀数组 ) --> https://oi-wiki.org/string/sa/
  5. */
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8. const int N = 1000010;
  9. typedef long long ll;
  10. int x[N], y[N], sa[N], c[N], rk[N], height[N];
  11. char s[N];
  12. int n, m;
  13. void getSA() {
  14.     for (int i = 1; i <= n; ++i) ++c[x[i] = s[i]];
  15.     for (int i = 2; i <= m; ++i) c[i] += c[i - 1];
  16.     for (int i = n; i >= 1; --i) sa[c[x[i]]--] = i;
  17.     for (int k = 1; k <= n; k <<= 1) {
  18.         int num = 0;
  19.         for (int i = n - k + 1; i <= n; ++i) y[++num] = i;
  20.         for (int i = 1; i <= n; ++i) if (sa[i] > k) y[++num] = sa[i] - k;
  21.         for (int i = 1; i <= m; ++i) c[i] = 0;
  22.         for (int i = 1; i <= n; ++i) ++c[x[i]];
  23.         for (int i = 2; i <= m; ++i) c[i] += c[i - 1];
  24.         for (int i = n; i >= 1; --i) sa[c[x[y[i]]]--] = y[i], y[i] = 0;
  25.         swap(x, y);
  26.         x[sa[1]] = 1; num = 1;
  27.         for (int i = 2; i <= n; ++i)
  28.             x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++num;
  29.         if (num == n) break;
  30.         m = num;
  31.     }
  32. }
  33. void getheight() {
  34.     int k = 0;
  35.     for (int i = 1; i <= n; ++i) rk[sa[i]] = i;
  36.     for (int i = 1; i <= n; ++i)if (rk[i] != 1) {
  37.             if (k > 0) --k;
  38.             int j = sa[rk[i] - 1];
  39.             while (j + k <= n && i + k <= n && s[i + k] == s[j + k]) ++k;
  40.             height[rk[i]] = k;
  41.         }
  42. }
  43. int main() {
  44.     scanf("%s", s + 1);
  45.     n = strlen(s + 1); m = 'z';
  46.     getSA();
  47.     // getheight();
  48.     for (int i = 1; i <= n; ++i)
  49.         printf("%d ", sa[i]);
  50.     printf("\n");
  51. }

SAM.cpp - STRING

  1. // SAM 后缀自动机
  2. #include <bits/stdc++.h>
  3. template<typename _Tp>
  4. inline void read(_Tp &x) {
  5.     x = 0; bool fg = 0; char ch = getchar();
  6.     while (ch < '0' || ch > '9') {if (ch == '-') fg ^= 1; ch = getchar();}
  7.     while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (_Tp)(ch ^ 48), ch = getchar();
  8.     if (fg) x = -x;
  9. }
  10. template<typename _Tp, typename... Args>void read(_Tp &t, Args &... args) {read(t); read(args...);}
  11. using namespace std;
  12. typedef long long ll;
  13. const int N = 2000010;
  14. char s[N]; int n;
  15. namespace SAM {
  16.     struct sta {
  17.         int len, link;
  18.         int nxt[26];
  19.     };
  20.     const int MAX = 2000010;
  21.     sta st[MAX];
  22.     int ct[MAX], deg[MAX];
  23.     int sz, lst;
  24.     void init() {
  25.         sz = 1; st[0].len = 0; st[0].link = -1; lst = 0;
  26.     }
  27.     void extend(char c) {
  28.         int cur = sz++, p = lst; st[cur].len = st[lst].len + 1;
  29.         ct[cur]++;
  30.         while (p != -1 && !st[p].nxt[c - 'a']) {
  31.             st[p].nxt[c - 'a'] = cur;
  32.             p = st[p].link;
  33.         }
  34.         if (p == -1) st[cur].link = 0;
  35.         else {
  36.             int q = st[p].nxt[c - 'a'];
  37.             if (st[q].len == st[p].len + 1)
  38.                 st[cur].link = q;
  40.             else {
  41.                 int cp = sz++;
  42.                 st[cp] = st[q];
  43.                 st[cp].len = st[p].len + 1;
  44.                 while (p != -1 && st[p].nxt[c - 'a'] == q) {
  45.                     st[p].nxt[c - 'a'] = cp;
  46.                     p = st[p].link;
  47.                 }
  48.                 st[cur].link = st[q].link = cp;
  49.             }
  50.         }
  51.         lst = cur;
  52.     }
  53.     void solve() {
  54.         for (int i = 1; i < sz; ++i)
  55.             deg[st[i].link]++;
  56.         queue<int> q;
  57.         for (int i = 1; i < sz; ++i) {
  58.             if (deg[i] == 0) q.push(i);
  59.         }
  60.         while (!q.empty()) {
  61.             int u = q.front(), f = st[u].link; q.pop();
  62.             if (f != -1) {
  63.                 deg[f]--; ct[f] += ct[u];
  64.                 if (deg[f] == 0) q.push(f);
  65.             }
  66.         }
  67.         ll ans = 0;
  68.         for (int i = 1; i < sz; ++i) {
  69.             if (ct[i] > 1)
  70.                 ans = max(ans, (ll)ct[i] * st[i].len);
  71.         }
  72.         printf("%lld\n", ans);
  73.     }
  74. }
  76. int main() {
  77.     scanf("%s", s + 1);
  78.     n = strlen(s + 1);
  79.     SAM::init();
  80.     for (int i = 1; i <= n; ++i) SAM::extend(s[i]);
  81.     SAM::solve();
  82.     return 0;
  83. }

strhash.cpp - STRING

  1. #include <iostream>
  2. using namespace std;
  4. #define fi first
  5. #define se second
  6. typedef long long ll;
  7. typedef pair<ll, ll> pll;
  8. const int p1 = 1019260817; // 双模 hash
  9. const int p2 = 1019260819;
  10. const int bs = 125641; // 基数
  11. const int N  = 100000;
  12. pll operator*(const pll &a, const ll &b) {return pll(a.fi * b % p1, a.se * b % p2);}
  13. pll operator*(const pll &a, const pll &b) {return pll(a.fi * b.fi % p1, a.se * b.se % p2);}
  14. pll operator+(const pll &a, const ll &b) {return pll((a.fi + b) % p1, (a.se + b) % p2);}
  15. pll operator-(const pll &a, const pll &b) {return pll((a.fi - b.fi + p1) % p1, (a.se - b.se + p2) % p2);}
  16. pll operator+(const pll &a, const pll &b) {return pll((a.fi + b.fi) % p1, (a.se + b.se) % p2);}
  17. pll pw[N], pws[N]; // pw[i] = bs ^ i, pws[i] = \sum_{j=0}^i bs^j
  18. void init(int n) {
  19.     pw[0] = {1, 1};
  20.     for (int i = 1; i <= n; ++i) pw[i] = pw[i - 1] * bs;
  21.     // pws[0] = {1, 1};
  22.     // for (int i = 1; i <= n; ++i) pws[i] = pws[i - 1] + pw[i];
  23. }
  24. // ---------- 用于线段树维护 Hash ----------
  25. struct dat {
  26.     pll f; // 哈希值
  27.     int len; // 串长
  28.     dat() { f = {0, 0}; len = 0; }
  29.     dat(const pll &_f, const int &_len) { f = _f; len = _len; }
  30. };
  31. dat operator*(const dat &a, const dat &b) { // hash 值拼接
  32.     return dat(a.f * pw[b.len] + b.f, a.len + b.len);
  33. }
  34. // ---------- 字符串 Hash ----------
  35. void initstr(char *S, int n, pll *f) {
  36.     f[0] = pll(0, 0); init(n);
  37.     for (int i = 1; i <= n; ++i)
  38.         f[i] = f[i - 1] * bs + (S[i] - 'a');
  39. }
  40. pll gethash(pll *f, int l, int r) {
  41.     return f[r] - f[l - 1] * pw[r - l + 1];
  42. }

Z-func.cpp - STRING

  1. // Z 函数 (EXKMP)
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. const int N = 40000010;
  5. char s[N], t[N]; int z[N], n, m;
  6. void Z_algo(char *s, int n) {
  7.     for (int i = 1; i <= n; ++i) z[i] = 0;
  8.     for (int i = 2, l = 0, r = 0; i <= n; ++i) {
  9.         if (i <= r) z[i] = min(z[i - l + 1], r - i + 1);
  10.         while (i + z[i] <= n && s[z[i] + 1] == s[i + z[i]]) ++z[i];
  11.         if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
  12.     }
  13. }
  14. int main() {
  15.     scanf("%s%s", s + 1, t + 1);
  16.     n = strlen(s + 1), m = strlen(t + 1);
  17.     t[m + 1] = '@';
  18.     strcat(t + 1, s + 1);
  19.     Z_algo(t, n + m + 1);
  20.     return 0;
  21. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注