fork download
  1. #include <bits/stdc++.h>
  2.  
  3. struct S { ... }; // Segment tree element type
  4. const S e = ...; // The identity element
  5. S op(S a, S b) { ... } // Compute a ยท b
  6.  
  7. struct F { ... }; // Lazy mapping type
  8. const F id = ...; // The identity mapping
  9. S mapping(F f, S x) { ... } // Compute f(x)
  10. F composition(F f, F g) { ... } // Compute f โˆ˜ g
  11. F inv(F f) { ... } // Compute f^(-1)
  12.  
  13. class lazy_segtree {
  14. public:
  15. explicit lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
  16. size = 1; log = 0;
  17. while (size < _n) size *= 2, log++;
  18. d = std::vector<S>(2 * size, e);
  19. lz = std::vector<F>(size, id);
  20. for (int i = 0; i < _n; i++) d[size + i] = v[i];
  21. for (int i = size - 1; i >= 1; i--) d[i] = op(d[2 * i], d[2 * i + 1]);
  22. }
  23.  
  24. S prod(int l, int r) const { // const!!!
  25. return prod(1, 0, size, id, l, r);
  26. }
  27.  
  28. void apply(int l, int r, F f) {
  29. apply(1, 0, size, id, l, r, f);
  30. }
  31.  
  32. public:
  33. int _n, size, log;
  34. std::vector<S> d;
  35. std::vector<F> lz;
  36.  
  37. void update(int k) { d[k] = mapping(lz[k], op(d[2 * k], d[2 * k + 1])); }
  38. void all_apply(int k, F f) {
  39. d[k] = mapping(f, d[k]);
  40. if (k < size) lz[k] = composition(f, lz[k]);
  41. }
  42.  
  43. S prod(int k, int cl, int cr, F g, int l, int r) const { // const!!!
  44. if (l <= cl && cr <= r) return mapping(g, d[k]);
  45.  
  46. int cm = (cl + cr) / 2;
  47. F h = composition(g, lz[k]);
  48. if (r <= cm) return prod(2 * k, cl, cm, h, l, r);
  49. if (l >= cm) return prod(2 * k + 1, cm, cr, h, l, r);
  50. return op(prod(2 * k, cl, cm, h, l, r),
  51. prod(2 * k + 1, cm, cr, h, l, r));
  52. }
  53.  
  54. void apply(int k, int cl, int cr, F g, int l, int r, F f) {
  55. if (l <= cl && cr <= r) {
  56. all_apply(k, composition(inv(g), composition(f, g)));
  57. return;
  58. }
  59.  
  60. int cm = (cl + cr) / 2;
  61. F h = composition(g, lz[k]);
  62. if (r <= cm)
  63. apply(2 * k, cl, cm, h, l, r, f);
  64. else if (l >= cm)
  65. apply(2 * k + 1, cm, cr, h, l, r, f);
  66. else {
  67. apply(2 * k, cl, cm, h, l, r, f);
  68. apply(2 * k + 1, cm, cr, h, l, r, f);
  69. }
  70. update(k);
  71. }
  72. };
Compilation error #stdin compilation error #stdout 0s 0KB
stdin
Standard input is empty
compilation info
prog.cpp:3:12: error: expected unqualified-id before ‘...’ token
 struct S { ... }; // Segment tree element type
            ^~~
prog.cpp:4:13: error: expected primary-expression before ‘...’ token
 const S e = ...; // The identity element
             ^~~
prog.cpp: In function ‘S op(S, S)’:
prog.cpp:5:18: error: expected primary-expression before ‘...’ token
 S op(S a, S b) { ... } // Compute a · b
                  ^~~
prog.cpp:5:22: warning: no return statement in function returning non-void [-Wreturn-type]
 S op(S a, S b) { ... } // Compute a · b
                      ^
prog.cpp: At global scope:
prog.cpp:7:12: error: expected unqualified-id before ‘...’ token
 struct F { ... }; // Lazy mapping type
            ^~~
prog.cpp:8:14: error: expected primary-expression before ‘...’ token
 const F id = ...; // The identity mapping
              ^~~
prog.cpp: In function ‘S mapping(F, S)’:
prog.cpp:9:23: error: expected primary-expression before ‘...’ token
 S mapping(F f, S x) { ... } // Compute f(x)
                       ^~~
prog.cpp:9:27: warning: no return statement in function returning non-void [-Wreturn-type]
 S mapping(F f, S x) { ... } // Compute f(x)
                           ^
prog.cpp: In function ‘F composition(F, F)’:
prog.cpp:10:27: error: expected primary-expression before ‘...’ token
 F composition(F f, F g) { ... } // Compute f โˆ˜ g
                           ^~~
prog.cpp:10:31: warning: no return statement in function returning non-void [-Wreturn-type]
 F composition(F f, F g) { ... } // Compute f โˆ˜ g
                               ^
prog.cpp: In function ‘F inv(F)’:
prog.cpp:11:14: error: expected primary-expression before ‘...’ token
 F inv(F f) { ... } // Compute f^(-1)
              ^~~
prog.cpp:11:18: warning: no return statement in function returning non-void [-Wreturn-type]
 F inv(F f) { ... } // Compute f^(-1)
                  ^
stdout
Standard output is empty