API tools faq
paste
Advertisement
pvcodes

PELTORATOR_CPP_TEMPLATE

pvcodes
Sep 21st, 2021
129
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 28.28 KB | None | 0 0
raw download clone embed print report diff
  1. snippet snips "all snippets"
  2. /*
  3. snips
  4. beg
  5. minimal
  6. for
  7. read
  8. vect
  9. all
  10. readvec
  11. sort
  12. pb
  13. graph
  14. tree
  15. rootedtree
  16. 0rootedtree
  17. gcd
  18. binpow
  19. inv
  20. fft
  21. sufarr
  22. aho
  23. cht
  24. segtree
  25. centroid
  26. sparse
  27. decart
  28. fenwick
  29. fenwick2d
  30. modular
  31. table
  32. {
  33. dsu
  34. deb
  35. */
  36. endsnippet
  37.  
  38. snippet beg "template"
  39. #ifdef ONPC
  40.     #define _GLIBCXX_DEBUG
  41. #endif
  42. #include <bits/stdc++.h>
  43. #define sz(a) ((int)((a).size()))
  44. #define char unsigned char
  45.  
  46. using namespace std;
  47. // mt19937 rnd(239);
  48. mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
  49.  
  50. typedef long long ll;
  51. typedef long double ld;
  52.  
  53. int solve() {
  54.     $0
  55.     return 0;
  56. }
  57.  
  58. int32_t main() {
  59.     ios::sync_with_stdio(0);
  60.     cin.tie(0);
  61.     int TET = 1e9;
  62.     //cin >> TET;
  63.     for (int i = 1; i <= TET; i++) {
  64.         if (solve()) {
  65.             break;
  66.         }
  67.         #ifdef ONPC
  68.             cout << "__________________________" << endl;
  69.         #endif
  70.     }
  71.     #ifdef ONPC
  72.         cerr << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
  73.     #endif
  74. }
  75. endsnippet
  76.  
  77. snippet minimal "minimalist begin"
  78. #include <bits/stdc++.h>
  79.  
  80. using namespace std;
  81. typedef long long ll;
  82.  
  83. int32_t main() {
  84.     $0
  85. }
  86. endsnippet
  87.  
  88. snippet for "for"
  89. for (int ${1:i} = 0; $1 < ${2:n}; $1++) {
  90.     $0
  91. }
  92. endsnippet
  93.  
  94. snippet read "read first variable"
  95. ${1:int} ${2:n};
  96. if (!(cin >> $2)) {
  97.     return 1;
  98. }
  99. $0
  100. endsnippet
  101.  
  102. snippet vect "vector"
  103. vector<${1:int}> ${2:arr};$0
  104. endsnippet
  105.  
  106. snippet all "all"
  107. ${1:arr}.begin(), $1.end()$0
  108. endsnippet
  109.  
  110. snippet readvec "read vector"
  111. vector<${1:int}> ${2:arr}(${3:n});
  112. for ($1 &val : $2) {
  113.     cin >> val;
  114. }
  115. $0
  116. endsnippet
  117.  
  118. snippet sort "read vector"
  119. sort(${1:arr}.begin(), $1.end());$0
  120. endsnippet
  121.  
  122. snippet pb "push_back"
  123. push_back($1);$0
  124. endsnippet
  125.  
  126. snippet graph "read graph"
  127. const int N = ;
  128.  
  129. vector<int> g[N];
  130. int used[N];
  131.  
  132. int solve() {
  133.     int n;
  134.     if (!(cin >> n)) {
  135.         return 1;
  136.     }
  137.     int m;
  138.     cin >> m;
  139.     for (int i = 0; i < n; i++) {
  140.         used[i] = 0;
  141.         g[i].clear();
  142.     }
  143.     for (int i = 0; i < m; i++) {
  144.         int x, y;
  145.         cin >> x >> y;
  146.         x--;
  147.         y--;
  148.         g[x].push_back(y);
  149.         g[y].push_back(x);
  150.     }
  151.     $0
  152.     return 1;
  153. }
  154. endsnippet
  155.  
  156. snippet tree "read tree"
  157. const int N = ;
  158.  
  159. vector<int> g[N];
  160. int used[N];
  161.  
  162. int solve() {
  163.     int n;
  164.     if (!(cin >> n)) {
  165.         return 1;
  166.     }
  167.     for (int i = 0; i < n; i++) {
  168.         used[i] = 0;
  169.         g[i].clear();
  170.     }
  171.     for (int i = 1; i < n; i++) {
  172.         int x, y;
  173.         cin >> x >> y;
  174.         x--;
  175.         y--;
  176.         g[x].push_back(y);
  177.         g[y].push_back(x);
  178.     }
  179.     $0
  180.     return 1;
  181. }
  182. endsnippet
  183.  
  184. snippet rootedtree "read rooted tree"
  185. const int N = ;
  186.  
  187. vector<int> g[N];
  188. int used[N], pr[N];
  189.  
  190. int solve() {
  191.     int n;
  192.     if (!(cin >> n)) {
  193.         return 1;
  194.     }
  195.     int root = -1;
  196.     for (int i = 0; i < n; i++) {
  197.         used[i] = 0;
  198.         g[i].clear();
  199.     }
  200.     for (int i = 0; i < n; i++) {
  201.         int p;
  202.         cin >> p;
  203.         if (p == -1) {
  204.             root = i;
  205.             continue;
  206.         }
  207.         p--;
  208.         g[p].push_back(i);
  209.         pr[i] = p;
  210.     }
  211.     $0
  212.     return 1;
  213. }
  214. endsnippet
  215.  
  216. snippet 0rootedtree "read rooted in first vertex tree"
  217. const int N = ;
  218.  
  219. vector<int> g[N];
  220. int used[N], pr[N];
  221.  
  222. int solve() {
  223.     int n;
  224.     if (!(cin >> n)) {
  225.         return 1;
  226.     }
  227.     for (int i = 0; i < n; i++) {
  228.         used[i] = 0;
  229.         g[i].clear();
  230.     }
  231.     for (int i = 1; i < n; i++) {
  232.         int p;
  233.         cin >> p;
  234.         p--;
  235.         g[p].push_back(i);
  236.         pr[i] = p;
  237.     }
  238.     $0
  239.     return 1;
  240. }
  241. endsnippet
  242.  
  243. snippet gcd "gcd"
  244. template<typename T>
  245. T gcd(T a, T b) {
  246.     while (a) {
  247.         b %= a;
  248.         swap(a, b);
  249.     }
  250.     return b;
  251. }
  252. endsnippet
  253.  
  254. snippet binpow "binpow"
  255. template<typename T>
  256. T binpow(T a, T b) {
  257.     T ans = 1;
  258.     while (b) {
  259.         if (b & 1) {
  260.             ans = 1LL * ans * a % MOD;
  261.         }
  262.         a = 1LL * a * a % MOD;
  263.         b >>= 1;
  264.     }
  265.     return ans;
  266. }
  267. endsnippet
  268.  
  269. snippet inv "any mod inverse"
  270. ll inv(ll a, ll m) {
  271.     if (a == 1) {
  272.         return 1;
  273.     }
  274.     return (1LL - inv(m % a, a) * m) / a + m;
  275. }
  276. endsnippet
  277.  
  278. snippet fft "FFT"
  279. namespace fft {
  280.     struct cmpl {
  281.         double x, y;
  282.         cmpl() {
  283.             x = y = 0;
  284.         }
  285.         cmpl(double x, double y) : x(x), y(y) {}
  286.         inline cmpl conjugated() const {
  287.             return cmpl(x, -y);
  288.         }
  289.     };
  290.     inline cmpl operator+(cmpl a, cmpl b) {
  291.         return cmpl(a.x + b.x, a.y + b.y);
  292.     }
  293.     inline cmpl operator-(cmpl a, cmpl b) {
  294.         return cmpl(a.x - b.x, a.y - b.y);
  295.     }
  296.     inline cmpl operator*(cmpl a, cmpl b) {
  297.         return cmpl(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
  298.     }
  299.  
  300.     int base = 1; // current power of two (2^base >= n)
  301.     vector<cmpl> roots = {{0, 0}, {1, 0}}; // complex roots of 1 (with bases from 1 to base), 1-based indexing
  302.     vector<int> rev = {0, 1}; // rev[i] = reversed bit representation of i
  303.     const double PI = static_cast<double>(acosl(-1.0));
  304.  
  305.     void ensure_base(int nbase) { // if base < nbase increase it
  306.         if (nbase <= base) {
  307.             return;
  308.         }
  309.         rev.resize(1 << nbase);
  310.         for (int i = 1; i < (1 << nbase); i++) {
  311.             rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (nbase - 1));
  312.         }
  313.         roots.resize(1 << nbase);
  314.         while (base < nbase) {
  315.             double angle = 2 * PI / (1 << (base + 1));
  316.             for (int i = 1 << (base - 1); i < (1 << base); i++) {
  317.                 roots[i << 1] = roots[i];
  318.                 double angle_i = angle * (2 * i + 1 - (1 << base));
  319.                 roots[(i << 1) + 1] = cmpl(cos(angle_i), sin(angle_i));
  320.             }
  321.             base++;
  322.         }
  323.     }
  324.  
  325.     void fft(vector<cmpl>& a, int n = -1) {
  326.         if (n == -1) {
  327.             n = (int) a.size();
  328.         }
  329.         assert((n & (n - 1)) == 0); // ensure that n is a power of two
  330.         int zeros = __builtin_ctz(n);
  331.         ensure_base(zeros);
  332.         int shift = base - zeros;
  333.         for (int i = 0; i < n; i++) {
  334.             if (i < (rev[i] >> shift)) {
  335.                 swap(a[i], a[rev[i] >> shift]);
  336.             }
  337.         }
  338.         for (int k = 1; k < n; k <<= 1) {
  339.             for (int i = 0; i < n; i += 2 * k) {
  340.                 for (int j = 0; j < k; j++) {
  341.                     cmpl z = a[i + j + k] * roots[j + k];
  342.                     a[i + j + k] = a[i + j] - z;
  343.                     a[i + j] = a[i + j] + z;
  344.                 }
  345.             }
  346.         }
  347.     }
  348.  
  349.     vector<cmpl> fa, fb;
  350.  
  351.     vector<long long> square(const vector<int>& a) {
  352.         if (a.empty()) {
  353.             return {};
  354.         }
  355.         int need = (int) a.size() + (int) a.size() - 1;
  356.         int nbase = 1;
  357.         while ((1 << nbase) < need) {
  358.             nbase++;
  359.         }
  360.         ensure_base(nbase);
  361.         int sz = 1 << nbase;
  362.         if ((sz >> 1) > (int) fa.size()) {
  363.             fa.resize(sz >> 1);
  364.         }
  365.         for (int i = 0; i < (sz >> 1); i++) {
  366.             int x = (2 * i < (int) a.size() ? a[2 * i] : 0);
  367.             int y = (2 * i + 1 < (int) a.size() ? a[2 * i + 1] : 0);
  368.             fa[i] = cmpl(x, y);
  369.         }
  370.         fft(fa, sz >> 1);
  371.         cmpl r(1.0 / (sz >> 1), 0.0);
  372.         for (int i = 0; i <= (sz >> 2); i++) {
  373.             int j = ((sz >> 1) - i) & ((sz >> 1) - 1);
  374.             cmpl fe = (fa[i] + fa[j].conjugated()) * cmpl(0.5, 0);
  375.             cmpl fo = (fa[i] - fa[j].conjugated()) * cmpl(0, -0.5);
  376.             cmpl aux = fe * fe + fo * fo * roots[(sz >> 1) + i] * roots[(sz >> 1) + i];
  377.             cmpl tmp = fe * fo;
  378.             fa[i] = r * (aux.conjugated() + cmpl(0, 2) * tmp.conjugated());
  379.             fa[j] = r * (aux + cmpl(0, 2) * tmp);
  380.         }
  381.         fft(fa, sz >> 1);
  382.         vector<long long> res(need);
  383.         for (int i = 0; i < need; i++) {
  384.             res[i] = llround(i % 2 == 0 ? fa[i >> 1].x : fa[i >> 1].y);
  385.         }
  386.         return res;
  387.     }
  388.    
  389.     // interface
  390.  
  391.     vector<long long> multiply(const vector<int>& a, const vector<int>& b) {
  392.         if (a.empty() || b.empty()) {
  393.             return {};
  394.         }
  395.         if (a == b) {
  396.             return square(a);
  397.         }
  398.         int need = (int) a.size() + (int) b.size() - 1;
  399.         int nbase = 1;
  400.         while ((1 << nbase) < need) nbase++;
  401.         ensure_base(nbase);
  402.         int sz = 1 << nbase;
  403.         if (sz > (int) fa.size()) {
  404.             fa.resize(sz);
  405.         }
  406.         for (int i = 0; i < sz; i++) {
  407.             int x = (i < (int) a.size() ? a[i] : 0);
  408.             int y = (i < (int) b.size() ? b[i] : 0);
  409.             fa[i] = cmpl(x, y);
  410.         }
  411.         fft(fa, sz);
  412.         cmpl r(0, -0.25 / (sz >> 1));
  413.         for (int i = 0; i <= (sz >> 1); i++) {
  414.             int j = (sz - i) & (sz - 1);
  415.             cmpl z = (fa[j] * fa[j] - (fa[i] * fa[i]).conjugated()) * r;
  416.             fa[j] = (fa[i] * fa[i] - (fa[j] * fa[j]).conjugated()) * r;
  417.             fa[i] = z;
  418.         }
  419.         for (int i = 0; i < (sz >> 1); i++) {
  420.             cmpl A0 = (fa[i] + fa[i + (sz >> 1)]) * cmpl(0.5, 0);
  421.             cmpl A1 = (fa[i] - fa[i + (sz >> 1)]) * cmpl(0.5, 0) * roots[(sz >> 1) + i];
  422.             fa[i] = A0 + A1 * cmpl(0, 1);
  423.         }
  424.         fft(fa, sz >> 1);
  425.         vector<long long> res(need);
  426.         for (int i = 0; i < need; i++) {
  427.         res[i] = llround(i % 2 == 0 ? fa[i >> 1].x : fa[i >> 1].y);
  428.         }
  429.         return res;
  430.     }
  431.  
  432.     vector<int> multiply_mod(const vector<int>& a, const vector<int>& b, int m) {
  433.         if (a.empty() || b.empty()) {
  434.             return {};
  435.         }
  436.         int need = (int) a.size() + (int) b.size() - 1;
  437.         int nbase = 0;
  438.         while ((1 << nbase) < need) {
  439.             nbase++;
  440.         }
  441.         ensure_base(nbase);
  442.         int sz = 1 << nbase;
  443.         if (sz > (int) fa.size()) {
  444.             fa.resize(sz);
  445.         }
  446.         for (int i = 0; i < (int) a.size(); i++) {
  447.             int x = (a[i] % m + m) % m;
  448.             fa[i] = cmpl(x & ((1 << 15) - 1), x >> 15);
  449.         }
  450.         fill(fa.begin() + a.size(), fa.begin() + sz, cmpl{0, 0});
  451.         fft(fa, sz);
  452.         if (sz > (int) fb.size()) {
  453.             fb.resize(sz);
  454.         }
  455.         if (a == b) {
  456.             copy(fa.begin(), fa.begin() + sz, fb.begin());
  457.         } else {
  458.             for (int i = 0; i < (int) b.size(); i++) {
  459.                 int x = (b[i] % m + m) % m;
  460.                 fb[i] = cmpl(x & ((1 << 15) - 1), x >> 15);
  461.             }
  462.             fill(fb.begin() + b.size(), fb.begin() + sz, cmpl{0, 0});
  463.             fft(fb, sz);
  464.         }
  465.         double ratio = 0.25 / sz;
  466.         cmpl r2(0, -1);
  467.         cmpl r3(ratio, 0);
  468.         cmpl r4(0, -ratio);
  469.         cmpl r5(0, 1);
  470.         for (int i = 0; i <= (sz >> 1); i++) {
  471.             int j = (sz - i) & (sz - 1);
  472.             cmpl a1 = (fa[i] + fa[j].conjugated());
  473.             cmpl a2 = (fa[i] - fa[j].conjugated()) * r2;
  474.             cmpl b1 = (fb[i] + fb[j].conjugated()) * r3;
  475.             cmpl b2 = (fb[i] - fb[j].conjugated()) * r4;
  476.             if (i != j) {
  477.                 cmpl c1 = (fa[j] + fa[i].conjugated());
  478.                 cmpl c2 = (fa[j] - fa[i].conjugated()) * r2;
  479.                 cmpl d1 = (fb[j] + fb[i].conjugated()) * r3;
  480.                 cmpl d2 = (fb[j] - fb[i].conjugated()) * r4;
  481.                 fa[i] = c1 * d1 + c2 * d2 * r5;
  482.                 fb[i] = c1 * d2 + c2 * d1;
  483.             }
  484.             fa[j] = a1 * b1 + a2 * b2 * r5;
  485.             fb[j] = a1 * b2 + a2 * b1;
  486.         }
  487.         fft(fa, sz);
  488.         fft(fb, sz);
  489.         vector<int> res(need);
  490.         for (int i = 0; i < need; i++) {
  491.             long long aa = llround(fa[i].x);
  492.             long long bb = llround(fb[i].x);
  493.             long long cc = llround(fa[i].y);
  494.             res[i] = static_cast<int>((aa + ((bb % m) << 15) + ((cc % m) << 30)) % m);
  495.         }
  496.         return res;
  497.     }
  498. }  // namespace fft
  499. /*
  500. use these:
  501. vector<int> multiply_mod(const vector<int>& a, const vector<int>& b, int m)
  502. vector<ll> square(const vector<int>& a)
  503. vector<ll> multiply(const vector<int>& a, const vector<int>& b) // (if a == b it uses square)
  504. */
  505. endsnippet
  506.  
  507.  
  508. snippet sufarr "suffix array"
  509. const char C = 'a' - 1; // before first letter // change
  510. const char maxchar = 'z'; // change
  511.  
  512. vector<int> suffarray(string s) { // without $ at the end
  513.     vector<int> p, c, pn, cn, cnt;
  514.     int n = (int)s.size();
  515.     c.assign(n, 0);
  516.     for (int i = 0; i < n; i++) {
  517.         c[i] = s[i] - C;
  518.     }
  519.     for (int j = 0; j <= (maxchar - C); j++) {
  520.         for (int i = 0; i < n; i++) {
  521.             if (c[i] == j) {
  522.                 p.push_back(i);
  523.             }
  524.         }
  525.     }
  526.     int maxc = c[p.back()];
  527.     pn.resize(n);
  528.     for (int k = 0; (1 << k) <= 2 * n; k++) {
  529.         for (int i = 0; i < n; i++) {
  530.             pn[i] = ((p[i] -  (1 << k)) % n + n) % n;
  531.         }
  532.         cnt.assign(maxc + 3, 0);
  533.         for (int i = 0; i < n; i++) {
  534.             cnt[c[i] + 1]++;
  535.         }
  536.         for (int i = 1; i <= maxc + 2; i++) {
  537.             cnt[i] += cnt[i - 1];
  538.         }
  539.         for (int i = 0; i < n; i++) {
  540.             p[cnt[c[pn[i]]]++] = pn[i];
  541.         }
  542.         cn.assign(n, 0);
  543.         cn[p[0]] = 1;
  544.         for (int i = 1; i < n; i++) {
  545.             if (c[p[i]] == c[p[i - 1]] && c[(p[i] + (1 << k)) % n] == c[(p[i - 1] + (1 << k)) % n]) {
  546.                 cn[p[i]] = cn[p[i - 1]];
  547.             } else {
  548.                 cn[p[i]] = cn[p[i - 1]] + 1;
  549.             }
  550.         }
  551.         maxc = cn[p.back()];
  552.         c = cn;
  553.     }
  554.     return p;
  555. }
  556.  
  557. vector<int> findlcp(string s, vector<int> p) {
  558.     vector<int> lcp, mem;
  559.     int n = (int)s.size();
  560.     mem.resize(n);
  561.     for (int i = 0; i < n; i++) {
  562.         mem[p[i]] = i;
  563.     }
  564.     lcp.assign(n, 0);
  565.     for (int i = 0; i < n; i++) {
  566.         if (i > 0) {
  567.             lcp[mem[i]] = max(lcp[mem[i - 1]] - 1, 0);
  568.         }
  569.         if (mem[i] == n - 1) {
  570.             continue;
  571.         }
  572.         while (max(i, p[mem[i] + 1]) + lcp[mem[i]] < n && s[i + lcp[mem[i]]] == s[p[mem[i] + 1] + lcp[mem[i]]]) {
  573.             lcp[mem[i]]++;
  574.         }
  575.     }
  576.     return lcp;
  577. }
  578. endsnippet
  579.  
  580.  
  581. snippet aho "aho-corasik"
  582. struct aho {
  583.     vector<vector<int> > g, gr;
  584.     vector<string> str;
  585.     int root;
  586.     int sz;
  587.     vector<ll> ending;
  588.     vector<int> link;
  589.     char firstlet;
  590.     int numlet = 0;
  591.  
  592.     aho():
  593.         g(),
  594.         gr(),
  595.         str(),
  596.         root(0),
  597.         sz(0),
  598.         ending(),
  599.         link() {}
  600.  
  601.     aho(vector<string> q, char firlet = 'a') { // change
  602.         firstlet = firlet;
  603.         sz = q.size();
  604.         str = q;
  605.         g.clear();
  606.         gr.clear();
  607.         ending.clear();
  608.         link.clear();
  609.         root = 0;
  610.         ending.assign(1, 0);
  611.         numlet = 0;
  612.         for (int i = 0; i < q.size(); i++) {
  613.             for (int j = 0; j < q[i].size(); j++) {
  614.                 numlet = q[i][j] - firstlet;
  615.             }
  616.         }
  617.         numlet++;
  618.         g.push_back(vector<int>(numlet, -1));
  619.         for (int i = 0; i < q.size(); i++) {
  620.             int v = root;
  621.             for (int j = 0; j < q[i].size(); j++) {
  622.                 if (g[v][q[i][j] - firstlet] == -1) {
  623.                     g[v][q[i][j] - firstlet] = g.size();
  624.                     g.push_back(vector<int>(numlet, -1));
  625.                     ending.push_back(0);
  626.                 }
  627.                 v = g[v][q[i][j] - firstlet];
  628.             }
  629.             ending[v]++;
  630.         }
  631.         link.assign(g.size(), -1);
  632.         link[root] = root;
  633.         queue<int> que;
  634.         que.push(root);
  635.         while (que.size()) {
  636.             int v = que.front();
  637.             que.pop();
  638.             for (int i = 0; i < numlet; i++) {
  639.                 if (g[v][i] == -1) {
  640.                     if (v == root) {
  641.                         g[v][i] = v;
  642.                     } else {
  643.                         g[v][i] = g[link[v]][i];
  644.                     }
  645.                 }
  646.                 else {
  647.                     que.push(g[v][i]);
  648.                     if (v == root) {
  649.                         link[g[v][i]] = v;
  650.                     } else {
  651.                         link[g[v][i]] = g[link[v]][i];
  652.                     }
  653.                 }
  654.         }
  655.         gr.resize(g.size());
  656.         for (int i = 0; i < g.size(); i++) {
  657.             if (i != root) {
  658.                 gr[link[i]].push_back(i);
  659.             }
  660.         }
  661.         dfslink(root);
  662.     }
  663.  
  664.     void dfslink(int v) {
  665.         for (int u : gr[v]) {
  666.             ending[u] += ending[v];
  667.             dfslink(u);
  668.         }
  669.     }
  670.  
  671.     ll find(string s) { // change
  672.         ll ans = 0;
  673.         int v = root;
  674.         for (int i = 0; i < s.size(); i++) {
  675.             v = g[v][s[i] - firstlet];
  676.             ans += ending[v];
  677.         }
  678.         return ans;
  679.     }
  680. };
  681. endsnippet
  682.    
  683.  
  684. snippet cht "convex hull trick"
  685. typedef long long integer;
  686.  
  687. struct Line {
  688.     integer k, b;
  689.     Line():
  690.         k(0),
  691.         b(0) {}
  692.     Line(integer k, integer b):
  693.         k(k),
  694.         b(b) {}
  695.  
  696.     ld operator()(ld x) {
  697.         return x * (ld)k + (ld)b;
  698.     }
  699. };
  700.  
  701. const integer INF = 2e18; // change
  702.  
  703. struct CHT {
  704.     vector<Line> lines;
  705.     bool mini; // cht on minimum
  706.  
  707.     ld f(Line l1, Line l2) {
  708.         return (ld)(l1.b - l2.b) / (ld)(l2.k - l1.k);
  709.     }
  710.  
  711.     void addLine(integer k, integer b) {
  712.         if (!mini) {
  713.             k = -k;
  714.             b = -b;
  715.         }
  716.         Line l(k, b);
  717.         while (lines.size() > 1) {
  718.             if (lines.back().k == k) {
  719.                 if (lines.back().b > b) {
  720.                     lines.pop_back();
  721.                 } else {
  722.                     break;
  723.                 }
  724.                 continue;
  725.             }
  726.             ld x1 = f(lines.back(), l);
  727.             ld x2 = f(lines.back(), lines[lines.size() - 2]);
  728.             if (x1 > x2) {
  729.                 break;
  730.             }
  731.             lines.pop_back();
  732.         }
  733.         if (!lines.size() || lines.back().k != k) {
  734.             lines.push_back(l);
  735.         }
  736.     }
  737.  
  738.     CHT(vector<pair<integer, integer> > v, bool ok = 1) { // change
  739.         mini = ok;
  740.         lines.clear();
  741.         for (int i = 0; i < v.size(); i++) {
  742.             addLine(v[i].first, v[i].second);
  743.         }
  744.     }
  745.  
  746.     integer getmin(integer x) { //find of integer!
  747.         if (!lines.size()) {
  748.             return (mini ? INF : -INF);
  749.         }
  750.         int l = 0, r = lines.size();
  751.         while (r - l > 1) {
  752.             int mid = (r + l) / 2;
  753.             if (f(lines[mid], lines[mid - 1]) <= (ld)x) {
  754.                 l = mid;
  755.             } else {
  756.                 r = mid;
  757.             }
  758.         }
  759.         integer ans = lines[l].k * x + lines[l].b;
  760.         return (mini ? ans : -ans);
  761.     }
  762. };
  763. endsnippet
  764.  
  765. snippet segtree "segment tree"
  766. struct SegmentTree {
  767.     // TO CHANGE
  768.  
  769.     struct Node { // set default values
  770.         ...
  771.  
  772.         template<typename T>
  773.         void apply(int l, int r, T val) { // update value and save push
  774.             ...
  775.         }
  776.     };
  777.  
  778.     Node merge(const Node& left, const Node& right) {
  779.         ...
  780.     }
  781.  
  782.     void push(int v, int l, int r) {
  783.         if (tree[v].??? != ...) {
  784.             int mid = (r + l) >> 1;
  785.             int vl = v + 1, vr = v + ((mid - l) << 1);
  786.             tree[vl].apply(l, mid, tree[v].???);
  787.             tree[vr].apply(mid, r, tree[v].???);
  788.             tree[v].??? = ...;
  789.         }
  790.     }
  791.  
  792.     // DEFAULT PART
  793.  
  794.     vector<Node> tree;
  795.     int n;
  796.  
  797.     template<typename T>
  798.     void build(int v, int l, int r, const vector<T>& arr) {
  799.         if (l + 1 == r) {
  800.             tree[v].apply(l, r, arr[l]);
  801.             return;
  802.         }
  803.         int mid = (r + l) >> 1;
  804.         int vl = v + 1, vr = v + ((mid - l) << 1);
  805.         build(vl, l, mid, arr);
  806.         build(vr, mid, r, arr);
  807.         tree[v] = merge(tree[vl], tree[vr]);
  808.     }
  809.  
  810.     void build(int v, int l, int r) {
  811.         if (l + 1 == r) {
  812.             return;
  813.         }
  814.         int mid = (r + l) >> 1;
  815.         int vl = v + 1, vr = v + ((mid - l) << 1);
  816.         build(vl, l, mid);
  817.         build(vr, mid, r);
  818.         tree[v] = merge(tree[vl], tree[vr]);
  819.     }
  820.  
  821.     Node find(int v, int l, int r, int ql, int qr) {
  822.         if (ql <= l && r <= qr) {
  823.             return tree[v];
  824.         }
  825.         push(v, l, r);
  826.         int mid = (r + l) >> 1;
  827.         int vl = v + 1, vr = v + ((mid - l) << 1);
  828.         if (qr <= mid) {
  829.             return find(vl, l, mid, ql, qr);
  830.         } else if (ql >= mid) {
  831.             return find(vr, mid, r, ql, qr);
  832.         } else {
  833.             return merge(find(vl, l, mid, ql, qr), find(vr, mid, r, ql, qr));
  834.         }
  835.     }
  836.  
  837.     template<typename T>
  838.     void update(int v, int l, int r, int ql, int qr, const T& newval) {
  839.         if (ql <= l && r <= qr) {
  840.             tree[v].apply(l, r, newval);
  841.             return;
  842.         }
  843.         push(v, l, r);
  844.         int mid = (r + l) >> 1;
  845.         int vl = v + 1, vr = v + ((mid - l) << 1);
  846.         if (ql < mid) {
  847.             update(vl, l, mid, ql, qr, newval);
  848.         }
  849.         if (qr > mid) {
  850.             update(vr, mid, r, ql, qr, newval);
  851.         }
  852.         tree[v] = merge(tree[vl], tree[vr]);
  853.     }
  854.  
  855.     int find_first(int v, int l, int r, int ql, int qr, const function<bool(const Node&)>& predicate) {
  856.         if (!predicate(tree[v])) {
  857.             return -1;
  858.         }
  859.         if (l + 1 == r) {
  860.             return l;
  861.         }
  862.         push(v, l, r);
  863.         int mid = (r + l) >> 1;
  864.         int vl = v + 1, vr = v + ((mid - l) << 1);
  865.         if (ql < mid) {
  866.             int lans = find_first(vl, l, mid, ql, qr, predicate);
  867.             if (lans != -1) {
  868.                 return lans;
  869.             }
  870.         }
  871.         if (qr > mid) {
  872.             int rans = find_first(vr, mid, r, ql, qr, predicate);
  873.             if (rans != -1) {
  874.                 return rans;
  875.             }
  876.         }
  877.         return -1;
  878.     }
  879.  
  880.     // INTERFACE
  881.  
  882.     SegmentTree(int n) : n(n) { // build from size with default values
  883.         tree.resize(2 * n - 1);
  884.         build(0, 0, n);
  885.     }
  886.  
  887.     template<typename T>
  888.     SegmentTree(const vector<T>& arr) { // build from vector
  889.         n = arr.size();
  890.         tree.resize(2 * n - 1);
  891.         build(0, 0, n, arr);
  892.     }
  893.  
  894.     Node find(int ql, int qr) { // find value on [ql, qr)
  895.         return find(0, 0, n, ql, qr);
  896.     }
  897.  
  898.     Node find(int qi) { // find value of position qi
  899.         return find(0, 0, n, qi);
  900.     }
  901.  
  902.     template<typename T>
  903.     void update(int ql, int qr, const T& newval) { // update [ql, qr) with newval
  904.         update(0, 0, n, ql, qr, newval);
  905.     }
  906.  
  907.     template<typename T>
  908.     void update(int qi, const T& newval) { // update position qi with newval
  909.         update(0, 0, n, qi, qi + 1, newval);
  910.     }
  911.  
  912.     int find_first(int ql, int qr, const function<bool(const Node&)>& predicate) { // find first index on [ql, qr) that satisfies predicate or -1 if none
  913.         return find_first(0, 0, n, ql, qr, predicate);
  914.     }
  915.  
  916.     int find_first(int ql, const function<bool(const Node&)>& predicate) { // find first index >= ql that satisfies predicate or -1 if none
  917.         return find_first(0, 0, n, ql, n, predicate);
  918.     }
  919.  
  920.     int find_first(const function<bool(const Node&)>& predicate) { // find first index that satisfies predicate or -1 if none
  921.         return find_first(0, 0, n, 0, n, predicate);
  922.     }
  923. };
  924. endsnippet
  925.    
  926. snippet centroid "centroid decomposition"
  927. const int MAXN = ;
  928.  
  929. vector<int> g[MAXN], used, p, d;
  930.  
  931. int cnt;
  932.  
  933. int dfs(int v, int pr) {
  934.     cnt++;
  935.     d[v] = 1;
  936.     for (int u : g[v]) {
  937.         if (!used[u] && u != pr) {
  938.             d[v] += dfs(u, v);
  939.         }
  940.     }
  941.     return d[v];
  942. }
  943.  
  944. int centroid(int v) {
  945.     cnt = 0;
  946.     dfs(v, -1);
  947.     int pr = -1;
  948.     while (true) {
  949.         int z = -1;
  950.         for (int u : g[v]) {
  951.             if (!used[u] && u != pr && d[u] * 2 >= cnt) {
  952.                 z = u;
  953.             }
  954.         }
  955.         if (z == -1) {
  956.             break;
  957.         }
  958.         pr = v;
  959.         v = z;
  960.     }
  961.     return v;
  962. }
  963.  
  964. void go(int v, int pr) {
  965.     v = centroid(v);
  966.     p[v] = pr;
  967.     used[v] = 1;
  968.  
  969.     for (int u : g[v]) {
  970.         if (!used[u]) {
  971.             go(u, v);
  972.         }
  973.     }
  974. }
  975. endsnippet
  976.    
  977.  
  978. snippet sparse "sparse table"
  979. template<typename T>
  980. struct SparseTable {
  981.     vector<vector<T>> sparse;
  982.     function<T(const T&, const T&)> accum_func;
  983.  
  984.     SparseTable(const vector<T>& arr, const function<T(const T&, const T&)>& func) : accum_func(func) {
  985.         int n = arr.size();
  986.         int logn = 32 - __builtin_clz(n);
  987.         sparse.resize(logn, vector<T>(n));
  988.         sparse[0] = arr;
  989.         for (int lg = 1; lg < logn; lg++) {
  990.             for (int i = 0; i + (1 << lg) <= n; i++) {
  991.                 sparse[lg][i] = accum_func(sparse[lg - 1][i], sparse[lg - 1][i + (1 << (lg - 1))]);
  992.             }
  993.         }
  994.     }
  995.  
  996.     T find(int l, int r) { // [l, r)
  997.         int cur_log = 31 - __builtin_clz(r - l);
  998.         return accum_func(sparse[cur_log][l], sparse[cur_log][r - (1 << cur_log)]);
  999.     }
  1000. };
  1001. endsnippet
  1002.    
  1003.  
  1004.  
  1005. snippet decart "treap"
  1006. struct Node {
  1007.     int x;
  1008.     ll y;
  1009.     int sz;
  1010.     Node *left;
  1011.     Node *right;
  1012.     Node(int x = 0):
  1013.         x(x),
  1014.         y((ll)rnd()),
  1015.         sz(1),
  1016.         left(NULL),
  1017.         right(NULL) {}
  1018. };
  1019.  
  1020. int sz(Node *v) {
  1021.     return (v == NULL ? 0 : v->sz);
  1022. }
  1023.  
  1024. Node* upd(Node *v) {
  1025.     if (v != NULL) {
  1026.         v->sz = 1 + sz(v->left) + sz(v->right);
  1027.     }
  1028.     return v;
  1029. }
  1030.  
  1031. Node* merge(Node *l, Node *r) {
  1032.     if (l == NULL) {
  1033.         return r;
  1034.     }
  1035.     if (r == NULL) {
  1036.         return l;
  1037.     }
  1038.     if (l->y < r->y) {
  1039.         l = merge(l, r->left);
  1040.         r->left = l;
  1041.         r = upd(r);
  1042.         return r;
  1043.     }
  1044.     r = merge(l->right, r);
  1045.     l->right = r;
  1046.     l = upd(l);
  1047.     return l;
  1048. }
  1049.  
  1050. pair<Node*, Node*> keySplit(Node *v, int key) { // l's keys <= key, r's keys > key
  1051.     if (v == NULL) {
  1052.         return {v, v};
  1053.     }
  1054.     if (v->x <= key) {
  1055.         auto a = keySplit(v->right, key);
  1056.         v->right = a.first;
  1057.         v = upd(v);
  1058.         return {v, a.second};
  1059.     }
  1060.     auto a = keySplit(v->left, key);
  1061.     v->left = a.second;
  1062.     v = upd(v);
  1063.     return {a.first, v};
  1064. }
  1065.  
  1066. pair<Node*, Node*> sizeSplit(Node *v, int siz) { // l's size is siz
  1067.     if (!v) {
  1068.         return {v, v};
  1069.     }
  1070.     if (sz(v->left) >= siz) {
  1071.         auto a = sizeSplit(v->left, siz);
  1072.         v->left = a.second;
  1073.         v = upd(v);
  1074.         return {a.first, v};
  1075.     }
  1076.     auto a = sizeSplit(v->right, siz - sz(v->left) - 1);
  1077.     v->right = a.first;
  1078.     v = upd(v);
  1079.     return {v, a.second};
  1080. }
  1081.  
  1082. void gogo(Node *v) {
  1083.     if (v == NULL) {
  1084.         return;
  1085.     }
  1086.     gogo(v->left);
  1087.     cerr << v->x << endl;
  1088.     gogo(v->right);
  1089. }
  1090. endsnippet
  1091.  
  1092. snippet fenwick "Fenwick tree"
  1093. struct Fenwick {
  1094.     vector<ll> tree;
  1095.     int n;
  1096.  
  1097.     Fenwick(int n) : n(n) {
  1098.         tree.assign(n, 0);
  1099.     }
  1100.  
  1101.     void point_add(int pos, ll val) {
  1102.         for (; pos < n; pos |= (pos + 1)) {
  1103.             tree[pos] += val;
  1104.         }
  1105.     }
  1106.  
  1107.     ll find_sum(int r) { // [0, r]
  1108.         ll ans = 0;
  1109.         for (; r >= 0; r = (r & (r + 1)) - 1) {
  1110.             ans += tree[r];
  1111.         }
  1112.         return ans;
  1113.     }
  1114.  
  1115.     ll find_sum(int l, int r) { // [l, r)
  1116.         return find_sum(r - 1) - find_sum(l - 1);
  1117.     }
  1118. };
  1119. endsnippet
  1120.  
  1121. snippet Fenwick2D "2D Fenwick tree"
  1122. struct Fenwick2D {
  1123.     vector<vector<ll>> tree;
  1124.     int n, m;
  1125.  
  1126.     Fenwick2D(int n, int m) : n(n), m(m) {
  1127.         tree.assign(n, vector<ll>(m, 0));
  1128.     }
  1129.  
  1130.     void point_add(int posx, int posy, ll val) {
  1131.         for (int x = posx; x < n; x |= (x + 1)) {
  1132.             for (int y = posy; y < m; y |= (y + 1)) {
  1133.                 tree[x][y] += val;
  1134.             }
  1135.         }
  1136.     }
  1137.  
  1138.     ll find_sum(int rx, int ry) { // [0, rx] x [0, ry]
  1139.         ll ans = 0;
  1140.         for (int x = rx; x >= 0; x = (x & (x + 1)) - 1) {
  1141.             for (int y = ry; y >= 0; y = (y & (y + 1)) - 1) {
  1142.                 ans += tree[x][y];
  1143.             }
  1144.         }
  1145.         return ans;
  1146.     }
  1147.  
  1148.     ll find_sum(int lx, int rx, int ly, int ry) { // [lx, rx) x [ly, ry)
  1149.         return find_sum(rx - 1, ry - 1) - find_sum(rx - 1, ly - 1) - find_sum(lx - 1, ry - 1) + find_sum(lx - 1, ly - 1);
  1150.     }
  1151. };
  1152. endsnippet
  1153.  
  1154. snippet modular "modular arithmetics"
  1155. template<int MODULO>
  1156. struct ModularInt {
  1157.     int value;
  1158.  
  1159.     ModularInt(ll llvalue) : value(llvalue % MODULO) {
  1160.         if (value < 0) {
  1161.             value += MODULO;
  1162.         }
  1163.     }
  1164.  
  1165.     ModularInt(const ModularInt<MODULO>& other) : value(other.value) {}
  1166.  
  1167.     inline void operator+=(ModularInt<MODULO> other) {
  1168.         value += other.value;
  1169.         if (value >= MODULO) {
  1170.             value -= MODULO;
  1171.         }
  1172.     }
  1173.  
  1174.     inline ModularInt<MODULO> operator+(ModularInt<MODULO> other) const {
  1175.         return ModularInt<MODULO>(value + other.value >= MODULO ? value + other.value - MODULO : value + other.value);
  1176.     }
  1177.  
  1178.     inline void operator-=(ModularInt<MODULO> other) {
  1179.         value -= other.value;
  1180.         if (value < 0) {
  1181.             value += MODULO;
  1182.         }
  1183.     }
  1184.  
  1185.     inline ModularInt<MODULO> operator-(ModularInt<MODULO> other) const {
  1186.         return ModularInt<MODULO>(value - other.value < 0 ? value - other.value + MODULO : value - other.value);
  1187.     }
  1188.  
  1189.     inline ModularInt<MODULO> operator-() const {
  1190.         return ModularInt<MODULO>(value == 0 ? value : MODULO - value);
  1191.     }
  1192.  
  1193.     inline ModularInt<MODULO>& operator++() {
  1194.         ++value;
  1195.         if (value == MODULO) {
  1196.             value = 0;
  1197.         }
  1198.         return *this;
  1199.     }
  1200.  
  1201.     inline ModularInt<MODULO> operator++(int) {
  1202.         ModularInt<MODULO> old(*this);
  1203.         ++value;
  1204.         if (value == MODULO) {
  1205.             value = 0;
  1206.         }
  1207.         return old;
  1208.     }
  1209.  
  1210.     inline ModularInt<MODULO>& operator--() {
  1211.         --value;
  1212.         if (value == -1) {
  1213.             value = MODULO - 1;
  1214.         }
  1215.         return *this;
  1216.     }
  1217.  
  1218.     inline ModularInt<MODULO> operator--(int) {
  1219.         ModularInt<MODULO> old(*this);
  1220.         --value;
  1221.         if (value == -1) {
  1222.             value = MODULO - 1;
  1223.         }
  1224.         return old;
  1225.     }
  1226.  
  1227.     inline ModularInt<MODULO> operator*(ModularInt<MODULO> other) const {
  1228.         return ModularInt<MODULO>(1LL * value * other.value);
  1229.     }
  1230.  
  1231.     inline void operator*=(ModularInt<MODULO> other) {
  1232.         value = 1LL * value * other.value % MODULO;
  1233.     }
  1234.  
  1235.     friend ModularInt<MODULO> binpow(ModularInt<MODULO> a, ll bll) {
  1236.         if (a.value == 0) {
  1237.             return ModularInt<MODULO>(bll == 0 ? 1 : 0);
  1238.         }
  1239.         int b = bll % (MODULO - 1);
  1240.         int ans = 1;
  1241.         while (b) {
  1242.             if (b & 1) {
  1243.                 ans = 1LL * ans * a % MODULO;
  1244.             }
  1245.             a = 1LL * a * a % MODULO;
  1246.             b >>= 1;
  1247.         }
  1248.         return ModularInt<MODULO>(ans);
  1249.     }
  1250.  
  1251.     inline ModularInt<MODULO> inv() const {
  1252.         return binpow(*this, MODULO - 2);
  1253.     }
  1254.  
  1255.     inline ModularInt<MODULO> operator/(ModularInt<MODULO> other) const {
  1256.         return (*this) * other.inv();
  1257.     }
  1258.  
  1259.     inline void operator/=(ModularInt<MODULO> other) {
  1260.         value = 1LL * value * other.inv().value % MODULO;
  1261.     }
  1262.  
  1263.     inline bool operator==(ModularInt<MODULO> other) const {
  1264.         return value == other.value;
  1265.     }
  1266.  
  1267.     inline bool operator!=(ModularInt<MODULO> other) const {
  1268.         return value != other.value;
  1269.     }
  1270.  
  1271.     explicit operator int() const {
  1272.         return value;
  1273.     }
  1274.  
  1275.     explicit operator bool() const {
  1276.         return value;
  1277.     }
  1278.  
  1279.     explicit operator long long() const {
  1280.         return value;
  1281.     }
  1282.  
  1283.     friend istream& operator>>(istream& inp, const ModularInt<MODULO>& mint) {
  1284.         inp >> mint.value;
  1285.         return inp;
  1286.     }
  1287.  
  1288.     friend ostream& operator<<(ostream& out, const ModularInt<MODULO>& mint) {
  1289.         out << mint.value;
  1290.         return out;
  1291.     }
  1292. };
  1293.  
  1294. const int MOD = ;
  1295.  
  1296. typedef ModularInt<MOD> MInt;
  1297. endsnippet
  1298.  
  1299. snippet table "table graph"
  1300. int dx[] = {0, 1, 0, -1};
  1301. int dy[] = {1, 0, -1, 0};
  1302. int n, m; // DON'T MAKE THEM IN MAIN
  1303.  
  1304. bool check(int x, int y) {
  1305.     return x >= 0 && x < n && y >= 0 && y < m;
  1306. }
  1307. endsnippet
  1308.  
  1309. snippet { "block"
  1310. {
  1311.     $0
  1312. }
  1313. endsnippet
  1314.  
  1315. snippet dsu "Disjoint Set Union"
  1316. struct DSU {
  1317.     vector<int> pr;
  1318.     int n;
  1319.  
  1320.     DSU(int n) : n(n) {
  1321.         pr.resize(n);
  1322.         iota(pr.begin(), pr.end(), 0);
  1323.     }
  1324.  
  1325.     inline int findpr(int v) {
  1326.         return (v == pr[v] ? v : (pr[v] = findpr(pr[v])));
  1327.     }
  1328.  
  1329.     inline bool unite(int v, int u) {
  1330.         v = findpr(v);
  1331.         u = findpr(v);
  1332.         if (u == v) {
  1333.             return false;
  1334.         } else {
  1335.             pr[v] = u;
  1336.             return true;
  1337.         }
  1338.     }
  1339. };
  1340. endsnippet
  1341.  
  1342. snippet deb "debug output"
  1343. #ifdef ONPC
  1344.     void debug_print(string s) {
  1345.         cerr << "\"" << s << "\"";
  1346.     }
  1347.  
  1348.     void debug_print(const char* s) {
  1349.         debug_print((string)s);
  1350.     }
  1351.  
  1352.     void debug_print(bool val) {
  1353.         cerr << (val ? "true" : "false");
  1354.     }
  1355.  
  1356.     void debug_print(int val) {
  1357.         cerr << val;
  1358.     }
  1359.  
  1360.     void debug_print(ll val) {
  1361.         cerr << val;
  1362.     }
  1363.  
  1364.     template<typename F, typename S>
  1365.     void debug_print(pair<F, S> val) {
  1366.         cerr << "(";
  1367.         debug_print(val.first);
  1368.         cerr << ", ";
  1369.         debug_print(val.second);
  1370.         cerr << ")";
  1371.     }
  1372.  
  1373.     void debug_print(vector<bool> val) {
  1374.         cerr << "{";
  1375.         bool first = true;
  1376.         for (bool x : val) {
  1377.             if (!first) {
  1378.                 cerr << ", ";
  1379.             } else {
  1380.                 first = false;
  1381.             }
  1382.             debug_print(x);
  1383.         }
  1384.         cerr << "}";
  1385.     }
  1386.  
  1387.     template<typename T>
  1388.     void debug_print(T val) {
  1389.         cerr << "{";
  1390.         bool first = true;
  1391.         for (const auto &x : val) {
  1392.             if (!first) {
  1393.                 cerr << ", ";
  1394.             } else {
  1395.                 first = false;
  1396.             }
  1397.             debug_print(x);
  1398.         }
  1399.         cerr << "}";
  1400.     }
  1401.  
  1402.     void debug_print_collection() {
  1403.         cerr << endl;
  1404.     }
  1405.  
  1406.     template<typename First, typename... Args>
  1407.     void debug_print_collection(First val, Args... args) {
  1408.         cerr << " ";
  1409.         debug_print(val);
  1410.         debug_print_collection(args...);
  1411.     }
  1412.  
  1413. #define debug(...) cerr << "@@@ " << #__VA_ARGS__ << " ="; debug_print_collection(__VA_ARGS__);
  1414.  
  1415. #else
  1416.     #define debug(...)
  1417. #endif
  1418. endsnippet
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!