API tools faq
paste
gt22

Untitled

gt22
May 18th, 2020
1,322
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 15.21 KB | None | 0 0
raw download clone embed print report
  1. #include <vector>
  2. #include <functional>
  3. #include <optional>
  4. #include <iostream>
  5. #include <set>
  6. #define FAST_ALLOCATOR_MEMORY (230*1024*1024)
  7. #include "optimization.h"
  8.  
  9. using namespace std;
  10. using ll = long long;
  11.  
  12. template<typename T>
  13. struct Monoid;
  14.  
  15. template<typename Mon>
  16. struct ValidMonoid : private Mon {
  17.     using value_type = typename Mon::value_type;
  18.     using T = typename Mon::value_type;
  19.     static_assert(std::is_same_v<decltype(Mon::compose(std::declval<T>(), std::declval<T>())), T>);
  20.     static_assert(std::is_same_v<decltype(Mon::identity()), T>);
  21.     using Mon::compose;
  22.     using Mon::identity;
  23. };
  24.  
  25.  
  26. template<typename T>
  27. struct Updater : Updater<Monoid<T>> {
  28.     using valid = ValidMonoid<Monoid<T>>;
  29. };
  30.  
  31. template<typename Upd>
  32. struct ValidUpdater : private Upd {
  33.     using value_type = typename Upd::value_type;
  34.     using update_type = typename Upd::update_type;
  35.     using T = typename Upd::value_type;
  36.     using U = typename Upd::update_type;
  37.     using valid = ValidMonoid<Upd>;
  38.     static_assert(std::is_same_v<decltype(Upd::update(std::declval<T>(), std::declval<U>(),
  39.                                                       std::declval<size_t>(), std::declval<size_t>())), T>);
  40.     using Upd::update;
  41.     using Upd::compose;
  42.     using Upd::identity;
  43. };
  44.  
  45. template<typename T>
  46. struct Updater<Monoid<T>> : Monoid<T> {
  47.     using M = Monoid<T>;
  48.     using valid = ValidMonoid<M>;
  49.     using value_type = typename M::value_type;
  50.     using update_type = typename M::value_type;
  51.  
  52.     static value_type update(const value_type& a, const update_type& b, size_t l, size_t r) { return M::compose(a, b); }
  53. };
  54.  
  55. template<typename T>
  56. struct STOp {
  57.     using composer = ValidMonoid<Monoid<T>>;
  58.     using updater = ValidUpdater<Updater<T>>;
  59. };
  60.  
  61. template<typename Op>
  62. struct ValidSTOp : Op {
  63.     using compose_valid = ValidMonoid<typename Op::composer>;
  64.     using updater_valid = ValidUpdater<typename Op::updater>;
  65.     static_assert(std::is_same_v<typename Op::composer::value_type, typename Op::updater::value_type>);
  66.     using typename Op::composer;
  67.     using typename Op::updater;
  68. };
  69.  
  70. template<typename Operation>
  71. class SegmentTree {
  72. public:
  73.     using Op = ValidSTOp<STOp<Operation>>;
  74.     using Cm = ValidMonoid<typename Op::composer>;
  75.     using Up = ValidUpdater<typename Op::updater>;
  76.     using T = typename Cm::value_type;
  77.     using U = typename Up::update_type;
  78.  
  79.     explicit SegmentTree(size_t n) : n(n) {
  80.         data.resize(4 * n, Cm::identity());
  81.         updates.resize(data.size(), Up::identity());
  82.     }
  83.  
  84.     explicit SegmentTree(int n) : SegmentTree(static_cast<size_t>(n)) {}
  85.  
  86.     template<typename Cont>
  87.     explicit SegmentTree(const Cont& cont) : SegmentTree(cont.size()) {
  88.         build(cont, 1, 0, n);
  89.     }
  90.  
  91.     T compute(size_t l, size_t r) {
  92.         return compute(1, 0, n, l, r);
  93.     }
  94.  
  95.     void applyToLeaf(size_t i, std::function<T(const T&, size_t, size_t)> f) {
  96.         applyToLeaf(1, 0, n, i, std::move(f));
  97.     }
  98.  
  99.     void applyToLeaf(size_t i, std::function<T(const T&)> f) {
  100.         applyToLeaf(i, [f](const T& t, size_t l, size_t r){ return f(t); });
  101.     }
  102.  
  103.     void set(size_t i, T x) {
  104.         applyToLeaf(i, [&x](const T& y, size_t l, size_t r) { return x; });
  105.     }
  106.  
  107.     void update(size_t i, U upd) {
  108.         applyToLeaf(i, [this, &upd](const T& x, size_t l, size_t r) { return Up::update(x, upd, l, r); });
  109.     }
  110.  
  111.     void update(size_t l, size_t r, U upd) {
  112.         update(1, 0, n, l, r, upd);
  113.     }
  114.  
  115. private:
  116.  
  117.     void check_bounds(size_t v, size_t vl, size_t vr, size_t l, size_t r) {
  118.         assert(v < data.size());
  119.         assert(vl <= n);
  120.         assert(vr <= n);
  121.         assert(l <= n);
  122.         assert(r <= n);
  123.     }
  124.  
  125.     T compute(size_t v, size_t vl, size_t vr, size_t l, size_t r) {
  126.         check_bounds(v, vl, vr, l, r);
  127.         if (disjoint(vl, vr, l, r)) return Cm::identity();
  128.         if (embedded(vl, vr, l, r)) {
  129.             return data[v];
  130.         }
  131.         size_t vm = mid(vl, vr);
  132.         return Up::update(
  133.                 Cm::compose(
  134.                 compute(left(v), vl, vm, l, r),
  135.                 compute(right(v), vm, vr, l, r)
  136.                 ),
  137.                 updates[v], vl, vr
  138.         );
  139.     }
  140.  
  141.     void update(size_t v, size_t vl, size_t vr, size_t l, size_t r, U upd) {
  142.         check_bounds(v, vl, vr, l, r);
  143.         recompute(v, vl, vr);
  144.         if (disjoint(vl, vr, l, r)) return;
  145.         if (embedded(vl, vr, l, r)) {
  146.             updates[v] = Up::compose(updates[v], upd);
  147.             recompute(v, vl, vr);
  148.             return;
  149.         }
  150.         size_t vm = mid(vl, vr);
  151.         push(v);
  152.         update(left(v), vl, vm, l, r, upd);
  153.         update(right(v), vm, vr, l, r, upd);
  154.         recompute(v, vl, vr);
  155.     }
  156.  
  157.     void push(size_t v) {
  158.         assert(v < data.size());
  159.         updates[left(v)] = Up::compose(updates[left(v)], updates[v]);
  160.         updates[right(v)] = Up::compose(updates[right(v)], updates[v]);
  161.         updates[v] = Up::identity();
  162.     }
  163.  
  164.     void applyToLeaf(size_t v, size_t vl, size_t vr, size_t i, std::function<T(const T&, size_t, size_t)> f) {
  165.         check_bounds(v, vl, vr, 0, 0);
  166.         if (vl == i && vr == i + 1) {
  167.             data[v] = f(data[v], vl, vr);
  168.             return;
  169.         }
  170.         size_t vm = mid(vl, vr);
  171.         if (i < vm) applyToLeaf(left(v), vl, vm, i, f);
  172.         else applyToLeaf(right(v), vm, vr, i, f);
  173.         recompute(v, vl, vr);
  174.     }
  175.  
  176.     template<typename Cont>
  177.     void build(const Cont& cnt, size_t v, size_t vl, size_t vr) {
  178.         if(vl + 1 == vr) {
  179.             data[v] = cnt[vl];
  180.             return;
  181.         }
  182.         size_t vm = mid(vl, vr);
  183.         build(cnt, left(v), vl, vm);
  184.         build(cnt, right(v), vm, vr);
  185.         recompute(v, vl, vr);
  186.     }
  187.  
  188.     bool disjoint(size_t vl, size_t vr, size_t l, size_t r) { return vr <= l || r <= vl; }
  189.  
  190.     bool embedded(size_t vl, size_t vr, size_t l, size_t r) { return l <= vl && vr <= r; }
  191.  
  192.     size_t mid(size_t vl, size_t vr) { return (vl + vr + 1) / 2; }
  193.  
  194.     size_t left(size_t i) { return 2 * i; }
  195.  
  196.     size_t right(size_t i) { return 2 * i + 1; }
  197.  
  198.     void recompute(size_t i, size_t vl, size_t vr) {
  199.         check_bounds(i, vl, vr, 0, 0);
  200.         if(vl + 1 == vr) {
  201.             data[i] = Up::update(data[i], updates[i], vl, vr);
  202.             updates[i] = Up::identity();
  203.         } else {
  204.             data[i] = Up::update(
  205.                     Cm::compose(data[left(i)], data[right(i)]),
  206.                     updates[i], vl, vr
  207.             );
  208.         }
  209.     }
  210.  
  211.     size_t n;
  212.     std::vector<T> data;
  213.     std::vector<U> updates;
  214. };
  215.  
  216.  
  217. template<typename T, T id = 0>
  218. struct Sum {
  219. };
  220.  
  221. template<typename T, T id>
  222. struct Monoid<Sum<T, id>> {
  223.     using value_type = T;
  224.  
  225.     static T identity() { return id; };
  226.  
  227.     static T compose(T a, T b) {
  228.         return a + b;
  229.     }
  230. };
  231.  
  232. template<typename T, T id>
  233. struct Updater<Sum<T, id>> : Monoid<Sum<T, id>> {
  234.     using update_type = T;
  235.  
  236.     static T update(T x, T up, size_t l, size_t r) {
  237.         return x + up * (r - l);
  238.     }
  239. };
  240.  
  241. template<typename T, T id = std::numeric_limits<T>::max()>
  242. struct Min {
  243. };
  244.  
  245. template<typename T, T id>
  246. struct Monoid<Min<T, id>> {
  247.     using value_type = T;
  248.  
  249.     static T identity() { return id; };
  250.  
  251.     static T compose(T a, T b) {
  252.         return min(a, b);
  253.     }
  254. };
  255.  
  256. template<typename T, const T* id = &std::numeric_limits<T>::min()>
  257. struct Max {
  258. };
  259.  
  260. template<typename T, const T* id>
  261. struct Monoid<Max<T, id>> {
  262.     using value_type = T;
  263.  
  264.     static T identity() { return *id; };
  265.  
  266.     static T compose(T a, T b) {
  267.         return max(a, b);
  268.     }
  269. };
  270.  
  271. //template<typename T, T* id>
  272. //struct Updater<Max<T, id>> : Monoid<Max<T, id>> {
  273. //
  274. //    using value_type = T;
  275. //    using update_type = T;
  276. //
  277. //    static value_type update(value_type a, update_type b, size_t l, size_t r) {
  278. //        return max(a, b);
  279. //    }
  280. //
  281. //};
  282.  
  283. template<typename T, T id = 0>
  284. struct PureSum {
  285. };
  286.  
  287. template<typename T, T id>
  288. struct Updater<PureSum<T, id>> : Monoid<Sum<T, id>> {
  289.     using update_type = T;
  290.  
  291.     static T update(const T& a, const T& b, size_t l, size_t r) { return a + b; }
  292.  
  293. };
  294.  
  295. struct CountSegments {};
  296.  
  297. struct CSNode {
  298.     enum class Color {
  299.         BLACK,
  300.         WHITE
  301.     };
  302.  
  303.     Color beg, end;
  304.     size_t black_cnt, len;
  305. };
  306.  
  307. std::string to_str(CSNode::Color c) {
  308.     return c == CSNode::Color::BLACK ? "B" : "W";
  309. }
  310. bool debug = false;
  311. template<>
  312. struct Monoid<CountSegments> {
  313.     using value_type = CSNode;
  314.     using Color = CSNode::Color;
  315.     static value_type identity() {
  316.         return {Color::WHITE, Color::WHITE, 0, 0};
  317.     }
  318.  
  319.     static value_type compose(value_type a, value_type b) {
  320.         CSNode res = {a.beg, b.end, a.black_cnt + b.black_cnt - (a.end == Color::BLACK && b.beg == Color::BLACK), a.len + b.len};
  321.         if(debug)
  322.         std::cerr << "Composing "
  323.                   << to_str(a.beg) << "[" << a.black_cnt << "]" << to_str(a.end)
  324.                   << " with "
  325.                   << to_str(b.beg) << "[" << b.black_cnt << "]" << to_str(b.end)
  326.                   << " result "
  327.                   << to_str(res.beg) << "[" << res.black_cnt << "]" << to_str(res.end)
  328.                   << std::endl;
  329.         return res;
  330.     }
  331. };
  332.  
  333.  
  334. template<>
  335. struct Updater<CountSegments> {
  336.  
  337.     using value_type = CSNode;
  338.     using update_type = std::optional<CSNode::Color>;
  339.  
  340.     static update_type identity() {
  341.         return std::optional<CSNode::Color>();
  342.     }
  343.  
  344.     static update_type compose(update_type a, update_type b) {
  345.         if(!b.has_value()) return a;
  346.         return b;
  347.     }
  348.  
  349.     static value_type update(value_type a, update_type u, size_t l, size_t r) {
  350.         if(!u.has_value()) return a;
  351.         CSNode res = {u.value(), u.value(), u.value() == CSNode::Color::BLACK, u.value() == CSNode::Color::BLACK ? (r - l) : 0};
  352.         if(debug)
  353.             std::cerr << "Updating "
  354.                       << to_str(a.beg) << "[" << a.black_cnt << "]" << to_str(a.end)
  355.                       << " to "
  356.                       << to_str(res.beg) << "[" << res.black_cnt << "]" << to_str(res.end)
  357.                       << std::endl;
  358.         return res;
  359.     }
  360. };
  361.  
  362. struct RectUpdater;
  363.  
  364. template<>
  365. struct Updater<RectUpdater> : Monoid<Sum<int>> {
  366.  
  367.     using value_type = pair<int, int>;
  368.     using update_type = int;
  369.  
  370.     static value_type update(value_type rect, update_type k, size_t l, size_t r) {
  371.         return {rect.first + k, rect.second};
  372.     }
  373. };
  374.  
  375. struct CountDisting {};
  376.  
  377. template<>
  378. struct Monoid<CountDisting> {
  379.     using value_type = set<int>;
  380.  
  381.     static value_type identity() {
  382.         return set<int>();
  383.     }
  384.  
  385.     static value_type compose(value_type a, value_type b) {
  386.         set<int> res;
  387.         res.insert(a.begin(), a.end());
  388.         res.insert(b.begin(), b.end());
  389.         return res;
  390.     }
  391. };
  392.  
  393. template<typename T>
  394. struct NoUpdates {};
  395.  
  396. template<typename T>
  397. struct Updater<NoUpdates<T>> {
  398.     using value_type = T;
  399.     using update_type = char;
  400.  
  401.     static update_type identity() {
  402.         return 0;
  403.     }
  404.  
  405.     static update_type compose(update_type a, update_type b) {
  406.         return 0;
  407.     }
  408.  
  409.     static value_type update(value_type a, update_type b, size_t l, size_t r) {
  410.         return a;
  411.     }
  412. };
  413.  
  414. template<typename Op, typename Up>
  415. struct ComplexOp {
  416. };
  417.  
  418. template<typename Op, typename Up>
  419. struct STOp<ComplexOp<Op, Up>> {
  420.     using composer = ValidMonoid<typename STOp<Op>::composer>;
  421.     using updater = ValidUpdater<typename STOp<Up>::updater>;
  422. };
  423.  
  424. using sum_type = size_t;
  425.  
  426. constexpr pair<sum_type, int> identity{0, -1};
  427.  
  428. int main() {
  429.     int n = readInt();
  430.     std::vector<set<int>> data;
  431.     data.reserve(n);
  432.     for (int i = 0; i < n; ++i) {
  433.         data.push_back(set<int>{readInt()});
  434.     }
  435.     SegmentTree<ComplexOp<CountDisting, NoUpdates<set<int>>>> tree(data);
  436.     int k = readInt();
  437.     std::vector<std::tuple<int, int, int>> events;
  438.     for (int i = 0; i < k; ++i) {
  439.         int l = readInt(), r = readInt();
  440.         writeInt(tree.compute(l - 1, r).size(), '\n');
  441.     }
  442. }
  443.  
  444. //int main() {
  445. //    int n = readInt();
  446. //    std::vector<std::tuple<int, int, int, int, int, int>> events;
  447. //    for (int i = 0; i < n; ++i) {
  448. //        int x1 = readInt(), y1 = readInt(), x2 = readInt(), y2 = readInt(), k = readInt();
  449. //        events.emplace_back(x1, 0, y1, y2, k, i);
  450. //        events.emplace_back(x2, 2, y1, y2, k, i);
  451. //    }
  452. //    sort(events.begin(), events.end());
  453. //    std::vector<int> coords{(int) -2e9, (int) 2e9};
  454. //    for (auto [x, type, y1, y2, k, i] : events) {
  455. //        coords.push_back(y1 - 1);
  456. //        coords.push_back(y1 * 1);
  457. //        coords.push_back(y2 * 1);
  458. //    }
  459. //    sort(coords.begin(), coords.end());
  460. //    coords.erase(unique(coords.begin(), coords.end()), coords.end());
  461. //    std::vector<pair<sum_type, int>> rects(n);
  462. //    size_t N = coords.size();
  463. //    SegmentTree<Max<pair<sum_type, int>, &identity>> tree(N);
  464. //    for(auto [x, type, y1, y2, k, i] : events) {
  465. //        y1 = lower_bound(coords.begin(), coords.end(), y1) - coords.begin();
  466. //        y2 = lower_bound(coords.begin(), coords.end(), y2) - coords.begin();
  467. //        switch(type) {
  468. //            case 0: {
  469. //                rects[i] = tree.compute(y2, N); //y2_new < y1_old
  470. //                rects[i].first += k;
  471. //                break;
  472. //            }
  473. //            case 2: {
  474. //                tree.update(y1 - 1, y1, {rects[i].first, i});
  475. //                break;
  476. //            }
  477. //        }
  478. //    }
  479. //    int maxI = 0;
  480. //    for (int i = 0; i < n; ++i) {
  481. //        if(rects[i].first > rects[maxI].first) {
  482. //            maxI = i;
  483. //        }
  484. //    }
  485. //    std::vector<int> chain;
  486. //    for(int i = maxI; i != -1; i = rects[i].second) {
  487. //        chain.push_back(i);
  488. //    }
  489. //    std::reverse(chain.begin(), chain.end());
  490. //    writeInt(rects[maxI].first, '\n');
  491. //    for(int i : chain) {
  492. //        writeInt(i + 1, ' ');
  493. //    }
  494. //    writeChar('\n');
  495. //}
  496.  
  497. // x1 y1 x2 y2
  498. // a1 b1 a2 b2
  499. // a1 > x2 && b2 < y1
  500.  
  501. //WWWWWWWWWWW
  502. //WWWWWWWWWWW
  503. //WWBBWWWWWWW
  504. //WWBBBBWWWWW
  505. //WWBBBBWWWWW
  506. //WWBBBBWBBWW
  507. //WWBWBBWBBWW
  508. //WWWWWWWWWWW
  509.  
  510. //int main() {
  511. //    int n = readInt();
  512. //    int N = 1000002;
  513. //    SegmentTree<CountSegments> tree(N);
  514. //    for (int i = 0; i < n; ++i) {
  515. //        debug = i == 5;
  516. //        int color = readChar(), x = readInt(), l = readInt();
  517. //        x += 500000;
  518. //        tree.update(x, x+l, color == 'W' ? CSNode::Color::WHITE : CSNode::Color::BLACK);
  519. //        CSNode ans = tree.compute(0, N);
  520. //        writeInt(ans.black_cnt, ' ');
  521. //        writeInt(ans.len, '\n');
  522. //    }
  523. //}
  524.  
  525. //int main() {
  526. //    int n = readInt(), q = readInt();
  527. //    vector<int> v;
  528. //    v.reserve(n);
  529. //    for (int i = 0; i < n; ++i) {
  530. //        v.push_back(readInt());
  531. //    }
  532. //    SegmentTree<ComplexOp<Max<ll, static_cast<ll>(-1e15)>, PureSum<ll>>> tree(v);
  533. //    for (int i = 0; i < q; ++i) {
  534. //        int cmd = readChar();
  535. //        readChar();
  536. //        readChar();
  537. //        int l = readInt() - 1, r = readInt();
  538. //        if (cmd == 'm') {
  539. //            writeInt(tree.compute(l, r), '\n');
  540. //        } else {
  541. //            int x = readInt();
  542. //            tree.update(l, r, x);
  543. //        }
  544. //    }
  545. //    return 0;
  546. //}
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
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!