API tools faq
paste
Advertisement
BaoJIaoPisu

Untitled

BaoJIaoPisu
Oct 8th, 2022
732
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 20.42 KB | None | 0 0
raw download clone embed print report
  1. #define double long double
  2. namespace FFT {
  3.     const int maxf = 1 << 17;
  4.     struct cp {
  5.         double x, y;
  6.         cp(double x = 0, double y = 0) : x(x), y(y) {}
  7.         cp operator + (const cp& rhs) const {
  8.             return cp(x + rhs.x, y + rhs.y);
  9.         }
  10.         cp operator - (const cp& rhs) const {
  11.             return cp(x - rhs.x, y - rhs.y);
  12.         }
  13.         cp operator * (const cp& rhs) const {
  14.             return cp(x * rhs.x - y * rhs.y, x * rhs.y + y * rhs.x);
  15.         }
  16.         cp operator !() const {
  17.             return cp(x, -y);
  18.         }
  19.     } rts[maxf + 1];
  20.     cp fa[maxf], fb[maxf];
  21.     cp fc[maxf], fd[maxf];
  22.  
  23.     int bitrev[maxf];
  24.     void fftinit() {
  25.         int k = 0; while ((1 << k) < maxf) k++;
  26.         bitrev[0] = 0;
  27.         for (int i = 1; i < maxf; i++) {
  28.             bitrev[i] = bitrev[i >> 1] >> 1 | ((i & 1) << k - 1);
  29.         }
  30.         double PI = acos((double) -1.0);
  31.         rts[0] = rts[maxf] = cp(1, 0);
  32.         for (int i = 1; i + i <= maxf; i++) {
  33.             rts[i] = cp(cos(i * 2 * PI / maxf), sin(i * 2 * PI / maxf));
  34.         }
  35.         for (int i = maxf / 2 + 1; i < maxf; i++) {
  36.             rts[i] = !rts[maxf - i];
  37.         }
  38.     }
  39.     void dft(cp a[], int n, int sign) {
  40.         static int isinit;
  41.         if (!isinit) {
  42.             isinit = 1;
  43.             fftinit();
  44.         }
  45.         int d = 0; while ((1 << d) * n != maxf) d++;
  46.         for (int i = 0; i < n; i++) {
  47.             if (i < (bitrev[i] >> d)) {
  48.                 swap(a[i], a[bitrev[i] >> d]);
  49.             }
  50.         }
  51.         for (int len = 2; len <= n; len <<= 1) {
  52.             int delta = maxf / len * sign;
  53.             for (int i = 0; i < n; i += len) {
  54.                 cp *x = a + i,*y = a + i + (len >> 1), *w = sign > 0 ? rts : rts + maxf;
  55.                 for (int k = 0; k + k < len; k++) {
  56.                     cp z = *y * *w;
  57.                     *y = *x - z, *x = *x + z;
  58.                     x++, y++, w += delta;
  59.                 }
  60.             }
  61.         }
  62.         if (sign < 0) {
  63.             for (int i = 0; i < n; i++) {
  64.                 a[i].x /= n;
  65.                 a[i].y /= n;
  66.             }
  67.         }
  68.     }
  69.     void multiply(int a[], int b[], int na, int nb, long long c[], int dup = 0) {
  70.         int n = na + nb - 1; while (n != (n & -n)) n += n & -n;
  71.         for (int i = 0; i < n; i++) fa[i] = fb[i] = cp();
  72.         for (int i = 0; i < na; i++) fa[i] = cp(a[i]);
  73.         for (int i = 0; i < nb; i++) fb[i] = cp(b[i]);
  74.         dft(fa, n, 1);
  75.         if (dup) {
  76.             for (int i = 0; i < n; i++) fb[i] = fa[i];
  77.         }
  78.         else {
  79.             dft(fb, n, 1);
  80.         }
  81.         for (int i = 0; i < n; i++) fa[i] = fa[i] * fb[i];
  82.         dft(fa, n, -1);
  83.         for (int i = 0; i < n; i++) c[i] = (long long) floor(fa[i].x + 0.5);
  84.     }
  85.     void multiply(int a[], int b[], int na, int nb, int c[], int mod = (int) 1e9 + 7, int dup = 0) {
  86.         int n = na + nb - 1;
  87.         while (n != (n & -n)) n += n & -n;
  88.         for (int i = 0; i < n; i++) fa[i] = fb[i] = cp();
  89.         static const int magic = 15;
  90.         for (int i = 0; i < na; i++) fa[i] = cp(a[i] >> magic, a[i] & (1 << magic) - 1);
  91.         for (int i = 0; i < nb; i++) fb[i] = cp(b[i] >> magic, b[i] & (1 << magic) - 1);
  92.         dft(fa, n, 1);
  93.         if (dup) {
  94.             for (int i = 0; i < n; i++) fb[i] = fa[i];
  95.         }
  96.         else {
  97.             dft(fb, n, 1);
  98.         }
  99.         for (int i = 0; i < n; i++) {
  100.             int j = (n - i) % n;
  101.             cp x = fa[i] + !fa[j];
  102.             cp y = fb[i] + !fb[j];
  103.             cp z = !fa[j] - fa[i];
  104.             cp t = !fb[j] - fb[i];
  105.             fc[i] = (x * t + y * z) * cp(0, 0.25);
  106.             fd[i] = x * y * cp(0, 0.25) + z * t * cp(-0.25, 0);
  107.         }
  108.         dft(fc, n, -1), dft(fd, n, -1);
  109.         for (int i = 0; i < n; i++) {
  110.             long long u = ((long long) floor(fc[i].x + 0.5)) % mod;
  111.             long long v = ((long long) floor(fd[i].x + 0.5)) % mod;
  112.             long long w = ((long long) floor(fd[i].y + 0.5)) % mod;
  113.             c[i] = ((u << magic) + v + (w << magic + magic)) % mod;
  114.         }
  115.     }
  116.     vector<int> multiply(vector<int> a, vector<int> b, int mod = (int) 1e9 + 7) {
  117.         static int fa[maxf], fb[maxf], fc[maxf];
  118.         int na = a.size(), nb = b.size();
  119.         for (int i = 0; i < na; i++) fa[i] = a[i];
  120.         for (int i = 0; i < nb; i++) fb[i] = b[i];
  121.         multiply(fa, fb, na, nb, fc, mod, a == b);
  122.         int k = na + nb - 1;
  123.         vector<int> res(k);
  124.         for (int i = 0; i < k; i++) res[i] = fc[i];
  125.         return res;
  126.     }
  127.     int fpow(int a, int k, int p) {
  128.         if (!k) return 1;
  129.         int res = a, t = a; k--;
  130.         while (k) {
  131.             if (k & 1) res = (long long) res * t % p;
  132.             t = (long long) t * t % p;
  133.             k >>= 1;
  134.         }
  135.         return res;
  136.     }
  137.     vector<int> invert(vector<int> a, int n, int mod){
  138.         assert(a[0] != 0);
  139.         vector<int> x(1, fpow(a[0], mod - 2, mod));
  140.         while (x.size() < n) {
  141.             vector<int> tmp(a.begin(), a.begin() + min(a.size(), 2 * x.size()));
  142.             vector<int> nx = multiply(multiply(x, x, mod), tmp, mod);
  143.             x.resize(2 * x.size());
  144.             for (int i = 0; i < x.size(); i++) {
  145.                 x[i] += x[i];
  146.                 x[i] -= nx[i];
  147.                 if (x[i] < 0) x[i] += mod;
  148.                 if (x[i] >= mod) x[i] -= mod;
  149.             }
  150.         }
  151.         x.resize(n);
  152.         return x;
  153.     }
  154.     pair<vector<int>, vector<int> > divmod(vector<int> a, vector<int> b, int mod) {
  155.         int n = a.size(), m = b.size();
  156.         if (n < m) {
  157.             return make_pair(vector<int>(), a);
  158.         }
  159.         reverse(a.begin(), a.end());
  160.         reverse(b.begin(), b.end());
  161.         vector<int> rb = invert(b, n - m + 1, mod);
  162.         vector<int> d = multiply(a, rb, mod);
  163.         reverse(a.begin(), a.end());
  164.         reverse(b.begin(), b.end());
  165.         while (d.size() > n - m + 1) d.pop_back();
  166.         reverse(d.begin(), d.end());
  167.         vector<int> r = multiply(d, b, mod);
  168.         while (r.size() >= m) r.pop_back();
  169.         for (int i = 0; i < m; i++) {
  170.             r[i] = a[i] - r[i];
  171.             if (r[i] < 0) r[i] += mod;
  172.         }
  173.         return make_pair(d, r);
  174.     }
  175.     vector<int> chirpz_transform(vector<int> a, int z, int k, int mod) {
  176.         int n = a.size();
  177.         vector<int> x;
  178.         vector<int> y;
  179.         int iz = fpow(z, mod - 2, mod);
  180.         for (int i = 0; i < n; i++) {
  181.             x.push_back((long long) a[i] * fpow(z, (long long) i * i, mod) % mod);
  182.         }
  183.         for (int i = 1 - n; i < k; i++) {
  184.             y.push_back(fpow(iz, (long long) i * i, mod));
  185.         }
  186.         vector<int> r = FFT::multiply(x, y, mod);
  187.         vector<int> res(k);
  188.         for (int i = 0; i < k; i++) {
  189.             res[i] = (long long) r[i + n - 1] * fpow(z, (long long) i * i, mod) % mod;
  190.         }
  191.         return res;
  192.     }
  193. }
  194. #undef double
  195.  
  196. struct Dinitz {
  197.     struct Edges {
  198.         int u, v;
  199.         ll cap;
  200.  
  201.         Edges() : u(), v(), cap() {}
  202.         Edges(int _u, int _v, ll _cap) : u(_u), v(_v), cap(_cap) {}
  203.     };
  204.  
  205.     vector<vector<int>> g;
  206.     vector<Edges> ed;
  207.     vector<int> dist;
  208.     vector<int> id;
  209.     int S, T;
  210.     int n;
  211.  
  212.     Dinitz() : ed(), n(), S(), T() {}
  213.     Dinitz(int _n, int _S, int _T) {
  214.         n = _n; S = _S; T = _T;
  215.         g.resize(n);
  216.         dist.resize(n);
  217.         id.resize(n);
  218.         for(int i = 0; i < n; i++) g[i].clear();
  219.         ed = vector<Edges>();
  220.     }
  221.  
  222.     void addEdge(int u, int v, ll cap) {
  223.         g[u].pb((int)ed.size());
  224.         ed.pb(Edges(u, v, cap));
  225.         g[v].pb((int)ed.size());
  226.         ed.pb(Edges(v, u, 0));
  227.     }
  228.  
  229.     bool bfs() {
  230.         for(int i = 0; i < n; i++) dist[i] = n + 5;
  231.         queue<int> q;
  232.         q.push(S); dist[S] = 0;
  233.         while(!q.empty()) {
  234.             int u = q.front(); q.pop();
  235.             for(int i : g[u]) {
  236.                 Edges e = ed[i];
  237.                 if(!e.cap) continue;
  238.                 if(dist[e.v] <= dist[u] + 1) continue;
  239.                 dist[e.v] = dist[u] + 1;
  240.                 q.push(e.v);
  241.             }
  242.         }
  243.  
  244.         return dist[T] < n + 5;
  245.     }
  246.  
  247.     ll dfs(int u, ll flow) {
  248.         if(u == T || flow == 0) return flow;
  249.  
  250.         ll ans = 0;
  251.         for(int &i = id[u]; i < (int)g[u].size(); i++) {
  252.             Edges e = ed[g[u][i]];
  253.             if(!e.cap) continue;
  254.             if(dist[e.v] != dist[u] + 1) continue;
  255.             ll f = dfs(e.v, min(flow, e.cap));
  256.             flow -= f;
  257.             ans += f;
  258.             ed[g[u][i]].cap -= f;
  259.             ed[g[u][i] ^ 1].cap += f;
  260.             if(flow == 0) return ans;
  261.         }
  262.  
  263.         return ans;
  264.     }
  265.  
  266.     ll Flow() {
  267.         ll ans = 0;
  268.         while(bfs()) {
  269.             for(int i = 0; i < n; i++) id[i] = 0;
  270.             ans += dfs(S, INF * INF);
  271.         }
  272.  
  273.         return ans;
  274.     }
  275. };
  276.  
  277. vector<int> z_function(string s) {
  278.     int n = (int) s.length();
  279.     vector<int> z(n);
  280.     for (int i = 1, l = 0, r = 0; i < n; ++i) {
  281.         if (i <= r)
  282.             z[i] = min (r - i + 1, z[i - l]);
  283.         while (i + z[i] < n && s[z[i]] == s[i + z[i]])
  284.             ++z[i];
  285.         if (i + z[i] - 1 > r)
  286.             l = i, r = i + z[i] - 1;
  287.     }
  288.     return z;
  289. }
  290.  
  291. struct LiChaoTree {
  292.     int n;
  293.     struct Line {
  294.         ll a = 0, b = INF * INF;
  295.  
  296.         Line(ll _a = 0, ll _b = 0) : a(_a), b(_b) {}
  297.     };
  298.  
  299.     vector<Line> Node;
  300.  
  301.     LiChaoTree(int _n = 0) {
  302.         n = _n;
  303.         Node.resize(4 * n + 7);
  304.     }
  305.  
  306. private:   
  307.     ll f(Line u, ll x) {return u.a * x + u.b;}
  308.  
  309.     void AddLine(Line u, int L, int R, int id) {
  310.         int mid = (L + R) >> 1;
  311.         bool left = f(u, L) < f(Node[id], L);
  312.         bool m = f(u, mid) < f(Node[id], mid);
  313.  
  314.         if(m) swap(u, Node[id]);
  315.  
  316.         if(L == R) return;
  317.         if(m != left) AddLine(u, L, mid, id << 1);
  318.         else AddLine(u, mid + 1, R, id << 1 | 1);
  319.     }
  320.  
  321.     ll Get(int L, int R, int x, int id) {
  322.         if(L > x || R < x) return INF * INF;
  323.         int mid = (L + R) >> 1;
  324.  
  325.         ll ans = f(Node[id], x);
  326.  
  327.         if(L == R) return ans;
  328.         if(x <= mid) minimize(ans, Get(L, mid, x, id << 1));
  329.         else minimize(ans, Get(mid + 1, R, x, id << 1 | 1));
  330.         return ans;
  331.     }
  332.  
  333. public:
  334.     void addLine(ll a, ll b) {
  335.         AddLine(Line(a, b), 1, n, 1);
  336.     }
  337.  
  338.     ll get(int x) {
  339.         return Get(1, n, x, 1);
  340.     }
  341. };
  342.  
  343. namespace NTT {
  344.     const int mod = MOD;
  345.     const int maxf = (1 << 19);
  346.     int rts[maxf + 1];
  347.     int bitrev[maxf];
  348.     int iv[maxf + 1];
  349.  
  350.     int fpow(int a, int k) {
  351.         if (!k) return 1;
  352.         int res = a, tmp = a;
  353.         k--;
  354.         while (k) {
  355.             if (k & 1) {
  356.                 res = (long long) res * tmp % mod;
  357.             }
  358.             tmp = (long long) tmp * tmp % mod;
  359.             k >>= 1;
  360.         }
  361.         return res;
  362.     }
  363.     int prt() {
  364.         vector<int> dvs;
  365.         for (int i = 2; i * i < mod; i++) {
  366.             if ((mod - 1) % i) continue;
  367.             dvs.push_back(i);
  368.             if (i * i != mod - 1) dvs.push_back((mod - 1) / i);
  369.         }
  370.         for (int i = 2; i < mod; i++) {
  371.             int flag = 1;
  372.             for (int j = 0; j < dvs.size(); j++) {
  373.                 if (fpow(i, dvs[j]) == 1) {
  374.                     flag = 0;
  375.                     break;
  376.                 }
  377.             }
  378.             if (flag) return i;
  379.         }
  380.         assert(0);
  381.         return -1;
  382.     }
  383.    
  384.     void NTT() {
  385.         int k = 0; while ((1 << k) < maxf) k++;
  386.         bitrev[0] = 0;
  387.         for (int i = 1; i < maxf; i++) {
  388.             bitrev[i] = bitrev[i >> 1] >> 1 | ((i & 1) << k - 1);
  389.         }
  390.         int pw = fpow(prt(), (mod - 1) / maxf);
  391.         rts[0] = 1;
  392.         for (int i = 1; i <= maxf; i++) {
  393.             rts[i] = (long long) rts[i - 1] * pw % mod;
  394.         }
  395.         for (int i = 1; i <= maxf; i <<= 1) {
  396.             iv[i] = fpow(i, mod - 2);
  397.         }
  398.     }
  399.  
  400.     void dft(int a[], int n, int sign) {
  401.         int d = 0; while ((1 << d) * n != maxf) d++;
  402.         for (int i = 0; i < n; i++) {
  403.             if (i < (bitrev[i] >> d)) {
  404.                 swap(a[i], a[bitrev[i] >> d]);
  405.             }
  406.         }
  407.         for (int len = 2; len <= n; len <<= 1) {
  408.             int delta = maxf / len * sign;
  409.             for (int i = 0; i < n; i += len) {
  410.                 int *w = sign > 0 ? rts : rts + maxf;
  411.                 for (int k = 0; k + k < len; k++) {
  412.                     int &a1 = a[i + k + (len >> 1)], &a2 = a[i + k];
  413.                     int t = (long long) *w * a1 % mod;
  414.                     a1 = a2 - t;
  415.                     a2 = a2 + t;
  416.                     a1 += a1 < 0 ? mod : 0;
  417.                     a2 -= a2 >= mod ? mod : 0;
  418.                     w += delta;
  419.                 }
  420.             }
  421.         }
  422.         if (sign < 0) {
  423.             int in = iv[n];
  424.             for (int i = 0; i < n; i++) {
  425.                 a[i] = (long long) a[i] * in % mod;
  426.             }
  427.         }
  428.     }
  429.     void multiply(int a[], int b[], int na, int nb, int c[]) {
  430.         static int fa[maxf], fb[maxf];
  431.         int n = na + nb - 1; while (n != (n & -n)) n += n & -n;
  432.         for (int i = 0; i < n; i++) fa[i] = fb[i] = 0;
  433.         for (int i = 0; i < na; i++) fa[i] = a[i];
  434.         for (int i = 0; i < nb; i++) fb[i] = b[i];
  435.         dft(fa, n, 1), dft(fb, n, 1);
  436.         for (int i = 0; i < n; i++) fa[i] = (long long) fa[i] * fb[i] % mod;
  437.         dft(fa, n, -1);
  438.         for (int i = 0; i < n; i++) c[i] = fa[i];
  439.     }
  440.     vector<int> multiply(vector<int> a, vector<int> b) {
  441.         NTT();
  442.         static int fa[maxf], fb[maxf], fc[maxf];
  443.         int na = a.size(), nb = b.size();
  444.         for (int i = 0; i < na; i++) fa[i] = a[i];
  445.         for (int i = 0; i < nb; i++) fb[i] = b[i];
  446.         multiply(fa, fb, na, nb, fc);
  447.         int k = na + nb - 1;
  448.         vector<int> res(k);
  449.         for (int i = 0; i < k; i++) res[i] = fc[i];
  450.         return res;
  451.     }
  452. };
  453.  
  454.  
  455. struct SGTBeats {
  456.   const ll inf = 1e18;
  457.   int n, n0;
  458.   ll max_v[4 * N], smax_v[4 * N], max_c[4 * N];
  459.   ll min_v[4 * N], smin_v[4 * N], min_c[4 * N];
  460.   ll sum[4 * N];
  461.   ll len[4 * N], ladd[4 * N], lval[4 * N];
  462.  
  463.   void update_node_max(int k, ll x) {
  464.     sum[k] += (x - max_v[k]) * max_c[k];
  465.  
  466.     if (max_v[k] == min_v[k]) {
  467.       max_v[k] = min_v[k] = x;
  468.     } else if (max_v[k] == smin_v[k]) {
  469.       max_v[k] = smin_v[k] = x;
  470.     } else {
  471.       max_v[k] = x;
  472.     }
  473.  
  474.     if (lval[k] != inf && x < lval[k]) {
  475.       lval[k] = x;
  476.     }
  477.   }
  478.   void update_node_min(int k, ll x) {
  479.     sum[k] += (x - min_v[k]) * min_c[k];
  480.  
  481.     if (max_v[k] == min_v[k]) {
  482.       max_v[k] = min_v[k] = x;
  483.     } else if (smax_v[k] == min_v[k]) {
  484.       min_v[k] = smax_v[k] = x;
  485.     } else {
  486.       min_v[k] = x;
  487.     }
  488.  
  489.     if (lval[k] != inf && lval[k] < x) {
  490.       lval[k] = x;
  491.     }
  492.   }
  493.   void push(int k) {
  494.     if (n0 - 1 <= k) return;
  495.     if (lval[k] != inf) {
  496.       updateall(2 * k + 1, lval[k]);
  497.       updateall(2 * k + 2, lval[k]);
  498.       lval[k] = inf;
  499.       return;
  500.     }
  501.     if (ladd[k] != 0) {
  502.       addall(2 * k + 1, ladd[k]);
  503.       addall(2 * k + 2, ladd[k]);
  504.       ladd[k] = 0;
  505.     }
  506.     if (max_v[k] < max_v[2 * k + 1]) {
  507.       update_node_max(2 * k + 1, max_v[k]);
  508.     }
  509.     if (min_v[2 * k + 1] < min_v[k]) {
  510.       update_node_min(2 * k + 1, min_v[k]);
  511.     }
  512.  
  513.     if (max_v[k] < max_v[2 * k + 2]) {
  514.       update_node_max(2 * k + 2, max_v[k]);
  515.     }
  516.     if (min_v[2 * k + 2] < min_v[k]) {
  517.       update_node_min(2 * k + 2, min_v[k]);
  518.     }
  519.   }
  520.   void update(int k) {
  521.     sum[k] = sum[2 * k + 1]  +  sum[2 * k + 2];
  522.  
  523.     if (max_v[2 * k + 1] < max_v[2 * k + 2]) {
  524.       max_v[k] = max_v[2 * k + 2];
  525.       max_c[k] = max_c[2 * k + 2];
  526.       smax_v[k] = max(max_v[2 * k + 1], smax_v[2 * k + 2]);
  527.     } else if (max_v[2 * k + 1] > max_v[2 * k + 2]) {
  528.       max_v[k] = max_v[2 * k + 1];
  529.       max_c[k] = max_c[2 * k + 1];
  530.       smax_v[k] = max(smax_v[2 * k + 1], max_v[2 * k + 2]);
  531.     } else {
  532.       max_v[k] = max_v[2 * k + 1];
  533.       max_c[k] = max_c[2 * k + 1]  +  max_c[2 * k + 2];
  534.       smax_v[k] = max(smax_v[2 * k + 1], smax_v[2 * k + 2]);
  535.     }
  536.  
  537.     if (min_v[2 * k + 1] < min_v[2 * k + 2]) {
  538.       min_v[k] = min_v[2 * k + 1];
  539.       min_c[k] = min_c[2 * k + 1];
  540.       smin_v[k] = min(smin_v[2 * k + 1], min_v[2 * k + 2]);
  541.     } else if (min_v[2 * k + 1] > min_v[2 * k + 2]) {
  542.       min_v[k] = min_v[2 * k + 2];
  543.       min_c[k] = min_c[2 * k + 2];
  544.       smin_v[k] = min(min_v[2 * k + 1], smin_v[2 * k + 2]);
  545.     } else {
  546.       min_v[k] = min_v[2 * k + 1];
  547.       min_c[k] = min_c[2 * k + 1]  +  min_c[2 * k + 2];
  548.       smin_v[k] = min(smin_v[2 * k + 1], smin_v[2 * k + 2]);
  549.     }
  550.   }
  551.   void _update_min(ll x, int a, int b, int k, int l, int r) {
  552.     if (b <= l || r <= a || max_v[k] <= x) {
  553.       return;
  554.     }
  555.     if (a <= l && r <= b && smax_v[k] < x) {
  556.       update_node_max(k, x);
  557.       return;
  558.     }
  559.     push(k);
  560.     _update_min(x, a, b, 2 * k + 1, l, (l + r) / 2);
  561.     _update_min(x, a, b, 2 * k + 2, (l + r) / 2, r);
  562.     update(k);
  563.   }
  564.   void _update_max(ll x, int a, int b, int k, int l, int r) {
  565.     if (b <= l || r <= a || x <= min_v[k]) {
  566.       return;
  567.     }
  568.     if (a <= l && r <= b && x < smin_v[k]) {
  569.       update_node_min(k, x);
  570.       return;
  571.     }
  572.     push(k);
  573.     _update_max(x, a, b, 2 * k + 1, l, (l + r) / 2);
  574.     _update_max(x, a, b, 2 * k + 2, (l + r) / 2, r);
  575.     update(k);
  576.   }
  577.   void addall(int k, ll x) {
  578.     max_v[k] += x;
  579.     if (smax_v[k] != -inf) smax_v[k] += x;
  580.     min_v[k] += x;
  581.     if (smin_v[k] != inf) smin_v[k] += x;
  582.  
  583.     sum[k] += len[k] * x;
  584.     if (lval[k] != inf) {
  585.       lval[k] += x;
  586.     } else {
  587.       ladd[k] += x;
  588.     }
  589.   }
  590.   void updateall(int k, ll x) {
  591.     max_v[k] = x; smax_v[k] = -inf;
  592.     min_v[k] = x; smin_v[k] = inf;
  593.     max_c[k] = min_c[k] = len[k];
  594.  
  595.     sum[k] = x * len[k];
  596.     lval[k] = x; ladd[k] = 0;
  597.   }
  598.   void _add_val(ll x, int a, int b, int k, int l, int r) {
  599.     if (b <= l || r <= a) {
  600.       return;
  601.     }
  602.     if (a <= l && r <= b) {
  603.       addall(k, x);
  604.       return;
  605.     }
  606.     push(k);
  607.     _add_val(x, a, b, 2 * k + 1, l, (l + r) / 2);
  608.     _add_val(x, a, b, 2 * k + 2, (l + r) / 2, r);
  609.     update(k);
  610.   }
  611.   void _update_val(ll x, int a, int b, int k, int l, int r) {
  612.     if (b <= l || r <= a) {
  613.       return;
  614.     }
  615.     if (a <= l && r <= b) {
  616.       updateall(k, x);
  617.       return;
  618.     }
  619.     push(k);
  620.     _update_val(x, a, b, 2 * k + 1, l, (l + r) / 2);
  621.     _update_val(x, a, b, 2 * k + 2, (l + r) / 2, r);
  622.     update(k);
  623.   }
  624.  
  625.   ll _query_max(int a, int b, int k, int l, int r) {
  626.     if (b <= l || r <= a) {
  627.       return -inf;
  628.     }
  629.     if (a <= l && r <= b) {
  630.       return max_v[k];
  631.     }
  632.     push(k);
  633.     ll lv = _query_max(a, b, 2 * k + 1, l, (l + r) / 2);
  634.     ll rv = _query_max(a, b, 2 * k + 2, (l + r) / 2, r);
  635.     return max(lv, rv);
  636.   }
  637.  
  638.   ll _query_min(int a, int b, int k, int l, int r) {
  639.     if (b <= l || r <= a) {
  640.       return inf;
  641.     }
  642.     if (a <= l && r <= b) {
  643.       return min_v[k];
  644.     }
  645.     push(k);
  646.     ll lv = _query_min(a, b, 2 * k + 1, l, (l + r) / 2);
  647.     ll rv = _query_min(a, b, 2 * k + 2, (l + r) / 2, r);
  648.     return min(lv, rv);
  649.   }
  650.  
  651.   ll _query_sum(int a, int b, int k, int l, int r) {
  652.     if (b <= l || r <= a) {
  653.       return 0;
  654.     }
  655.     if (a <= l && r <= b) {
  656.       return sum[k];
  657.     }
  658.     push(k);
  659.     ll lv = _query_sum(a, b, 2 * k + 1, l, (l + r) / 2);
  660.     ll rv = _query_sum(a, b, 2 * k + 2, (l + r) / 2, r);
  661.     return lv + rv;
  662.   }
  663.  
  664.   SGTBeats(int n) {
  665.     SGTBeats(n, nullptr);
  666.   }
  667.  
  668.   SGTBeats(int n, ll *a) : n(n) {
  669.     n0 = 1;
  670.     while (n0 < n) n0 <<= 1;
  671.     for (int i = 0; i < 2 * n0; ++i) ladd[i] = 0, lval[i] = inf;
  672.     len[0] = n0;
  673.     for (int i = 0; i < n0 - 1; ++i) len[2 * i + 1] = len[2 * i + 2] = (len[i] >> 1);
  674.  
  675.     for (int i = 0; i < n; ++i) {
  676.       max_v[n0 - 1 + i] = min_v[n0 - 1 + i] = sum[n0 - 1 + i] = (a != nullptr ? a[i] : 0);
  677.       smax_v[n0 - 1 + i] =  -inf;
  678.       smin_v[n0 - 1 + i] = inf;
  679.       max_c[n0 - 1 + i] = min_c[n0 - 1 + i] = 1;
  680.     }
  681.     for (int i = n; i < n0; ++i) {
  682.       max_v[n0 - 1 + i] = smax_v[n0 - 1 + i] =  -inf;
  683.       min_v[n0 - 1 + i] = smin_v[n0 - 1 + i] = inf;
  684.       max_c[n0 - 1 + i] = min_c[n0 - 1 + i] = 0;
  685.     }
  686.     for (int i = n0 - 2; i >= 0; i--) {
  687.       update(i);
  688.     }
  689.   }
  690.  
  691.   // all queries are performed on [l, r) segment
  692.  
  693.   // range minimize query
  694.   void update_min(int a, int b, ll x) {
  695.     _update_min(x, a, b, 0, 0, n0);
  696.   }
  697.   // range maximize query
  698.   void update_max(int a, int b, ll x) {
  699.     _update_max(x, a, b, 0, 0, n0);
  700.   }
  701.   // range add query
  702.   void add_val(int a, int b, ll x) {
  703.     _add_val(x, a, b, 0, 0, n0);
  704.   }
  705.   // range update query
  706.   void update_val(int a, int b, ll x) {
  707.     _update_val(x, a, b, 0, 0, n0);
  708.   }
  709.   // range minimum query
  710.   ll query_max(int a, int b) {
  711.     return _query_max(a, b, 0, 0, n0);
  712.   }
  713.   // range maximum query
  714.   ll query_min(int a, int b) {
  715.     return _query_min(a, b, 0, 0, n0);
  716.   }
  717.   // range sum query
  718.   ll query_sum(int a, int b) {
  719.     return _query_sum(a, b, 0, 0, n0);
  720.   }
  721. };
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!