fork download
copy 
  1. // #define _CRT_SECURE_NO_WARNINGS 
  2.  
  3. #include <iostream> 
  4. #include <algorithm> 
  5. #include <cmath> 
  6. #include <climits> 
  7. #include <vector> 
  8. #include <queue> 
  9. #include <deque> 
  10. #include <array> 
  11. #include <list> 
  12. #include <stack> 
  13. #include <tuple> 
  14. #include <set> 
  15. #include <unordered_set> 
  16. #include <map> 
  17. #include <unordered_map> 
  18. #include <string> 
  19. #include <cstring> 
  20. #include <random> 
  21. #include <bitset> 
  22. #include <iomanip> 
  23. #include <iterator> 
  24. #include <functional> 
  25. #include <ctime> 
  26. #include <chrono> 
  27. #include <cctype> 
  28. #include <fstream> 
  29. #include <ranges> 
  30. #include <numeric> 
  31. #include <complex> 
  32. #include <cassert> 
  33.  
  34. using namespace std;
  35.  
  36. // #pragma GCC optimize("Ofast") 
  37. // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  38.  
  39. #define int               long long 
  40. #define sz(x)             ((int)(x).size()) 
  41. #define mp                make_pair 
  42. #define all(x)            (x).begin(), (x).end() 
  43. #define pb                push_back 
  44. #define pf                push_front 
  45. #define ff                first 
  46. #define ss                second 
  47. #define unique(x)         (x).erase(unique(all(x)), (x).end()) 
  48. #define min3(a, b, c)     min(a, min(b, c)) 
  49. #define max3(a, b, c)     max(a, max(b, c)) 
  50. #define FOR(i, a, b)      for (int i = (a); i <= (b); i++) 
  51. #define ROF(i, a, b)      for (int i = (a); i >= (b); i--) 
  52.  
  53. using vi = vector<int>;
  54. using vd = vector<double>;
  55. using vpii = vector<pair<int, int>>;
  56. using vpdd = vector<pair<double, double>>;
  57. using pii = pair<int, int>;
  58. using pdd = pair<double, double>;
  59.  
  60. template <typename Container>
  61. void PRINT(const Container& container) {
  62.     for (const auto& e : container) {
  63.         cout << e << ' ';
  64.     } cout << '\n';
  65. }
  66.  
  67. void print_double(double ans, int num) {
  68.     cout << fixed << setprecision(num) << ans << '\n';
  69. }
  70.  
  71. const int inf = 1e18;
  72. const double eps = 1e-9;
  73. const double PI = 3.141592653589793;
  74.  
  75. string alh = "abcdefghijklmnopqrstuvwxyz";
  76. string ALH = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  77.  
  78. class SegmentTree2D {
  79. private:
  80.     struct Node {
  81.         map<int, Node*> children;
  82.         int value = 0;
  83.     };
  84.  
  85.     Node* root;
  86.  
  87.     void update(Node*& node, int x, int y, int val, int xLeft, int xRight, int yLeft, int yRight) {
  88.         if (!node) {
  89.             node = new Node();
  90.         }
  91.  
  92.         if (xLeft == xRight && yLeft == yRight) {
  93.             node->value += val;
  94.             return;
  95.         }
  96.  
  97.         int midX = (xLeft + xRight) / 2;
  98.         int midY = (yLeft + yRight) / 2;
  99.  
  100.         if (x <= midX) {
  101.             if (y <= midY) {
  102.                 update(node->children[0], x, y, val, xLeft, midX, yLeft, midY);
  103.             }
  104.             else {
  105.                 update(node->children[1], x, y, val, xLeft, midX, midY + 1, yRight);
  106.             }
  107.         }
  108.         else {
  109.             if (y <= midY) {
  110.                 update(node->children[2], x, y, val, midX + 1, xRight, yLeft, midY);
  111.             }
  112.             else {
  113.                 update(node->children[3], x, y, val, midX + 1, xRight, midY + 1, yRight);
  114.             }
  115.         }
  116.  
  117.         node->value = 0;
  118.         for (auto& [_, child] : node->children) {
  119.             if (child) {
  120.                 node->value += child->value;
  121.             }
  122.         }
  123.     }
  124.  
  125.     int query(Node* node, int x1, int y1, int x2, int y2, int xLeft, int xRight, int yLeft, int yRight) {
  126.         if (!node || x1 > xRight || x2 < xLeft || y1 > yRight || y2 < yLeft) {
  127.             return 0;
  128.         }
  129.  
  130.         if (x1 <= xLeft && xRight <= x2 && y1 <= yLeft && yRight <= y2) {
  131.             return node->value;
  132.         }
  133.  
  134.         int midX = (xLeft + xRight) / 2;
  135.         int midY = (yLeft + yRight) / 2;
  136.  
  137.         int sum = 0;
  138.         sum += query(node->children[0], x1, y1, x2, y2, xLeft, midX, yLeft, midY);
  139.         sum += query(node->children[1], x1, y1, x2, y2, xLeft, midX, midY + 1, yRight);
  140.         sum += query(node->children[2], x1, y1, x2, y2, midX + 1, xRight, yLeft, midY);
  141.         sum += query(node->children[3], x1, y1, x2, y2, midX + 1, xRight, midY + 1, yRight);
  142.  
  143.         return sum;
  144.     }
  145.  
  146. public:
  147.     SegmentTree2D() { root = nullptr; }
  148.  
  149.     void update(int x, int y, int value) {
  150.         update(root, x, y, value, 0, inf, 0, inf);
  151.     }
  152.  
  153.     int query(int x1, int y1, int x2, int y2) {
  154.         return query(root, x1, y1, x2, y2, 0, inf, 0, inf);
  155.     }
  156. };
  157.  
  158. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  159.  
  160. class Treap {
  161. public:
  162.     struct TreapNode {
  163.         int value, priority;
  164.         TreapNode* left, * right;
  165.         int size;
  166.  
  167.         TreapNode(int v) :
  168.             value(v), priority(rng()),
  169.             left(nullptr), right(nullptr),
  170.             size(1) {
  171.         }
  172.     };
  173.  
  174.     Treap() : root(nullptr) {}
  175.  
  176.     void insert(int value) {
  177.         insert(root, new TreapNode(value));
  178.     }
  179.  
  180.     void remove(int value) {
  181.         remove(root, value);
  182.     }
  183.  
  184.     int Count_L(int x) {
  185.         return Count_L(root, x);
  186.     }
  187.  
  188.     int Count_R(int x) {
  189.         return Count_R(root, x);
  190.     }
  191.  
  192. private:
  193.     TreapNode* root;
  194.  
  195.     int getSize(TreapNode* node) {
  196.         return node ? node->size : 0;
  197.     }
  198.  
  199.     void updateSize(TreapNode* node) {
  200.         if (node) {
  201.             node->size = 1 + getSize(node->left) + getSize(node->right);
  202.         }
  203.     }
  204.  
  205.     void split(TreapNode* node, int key, TreapNode*& left, TreapNode*& right) {
  206.         if (!node) {
  207.             left = right = nullptr;
  208.             return;
  209.         }
  210.  
  211.         if (node->value <= key) {
  212.             split(node->right, key, node->right, right);
  213.             left = node;
  214.         }
  215.         else {
  216.             split(node->left, key, left, node->left);
  217.             right = node;
  218.         }
  219.  
  220.         updateSize(node);
  221.     }
  222.  
  223.     void merge(TreapNode*& node, TreapNode* left, TreapNode* right) {
  224.         if (!left || !right) {
  225.             node = left ? left : right;
  226.             return;
  227.         }
  228.  
  229.         if (left->priority > right->priority) {
  230.             merge(left->right, left->right, right);
  231.             node = left;
  232.         }
  233.         else {
  234.             merge(right->left, left, right->left);
  235.             node = right;
  236.         }
  237.  
  238.         updateSize(node);
  239.     }
  240.  
  241.     void insert(TreapNode*& node, TreapNode* newNode) {
  242.         if (!node) {
  243.             node = newNode;
  244.             return;
  245.         }
  246.  
  247.         if (newNode->priority > node->priority) {
  248.             split(node, newNode->value, newNode->left, newNode->right);
  249.             node = newNode;
  250.         }
  251.         else {
  252.             insert(newNode->value <= node->value ? node->left : node->right, newNode);
  253.         }
  254.  
  255.         updateSize(node);
  256.     }
  257.  
  258.     void remove(TreapNode*& node, int value) {
  259.         if (!node) {
  260.             return;
  261.         }
  262.  
  263.         if (node->value == value) {
  264.             TreapNode* temp = node;
  265.             merge(node, node->left, node->right);
  266.             delete temp;
  267.         }
  268.         else {
  269.             remove(value < node->value ? node->left : node->right, value);
  270.         }
  271.  
  272.         updateSize(node);
  273.     }
  274.  
  275.     int Count_L(TreapNode* node, int x) {
  276.         if (!node) {
  277.             return 0;
  278.         }
  279.  
  280.         if (node->value <= x) {
  281.             return 1 + getSize(node->left) + Count_L(node->right, x);
  282.         }
  283.         else {
  284.             return Count_L(node->left, x);
  285.         }
  286.     }
  287.  
  288.     int Count_R(TreapNode* node, int x) {
  289.         if (!node) {
  290.             return 0;
  291.         }
  292.  
  293.         if (node->value >= x) {
  294.             return 1 + getSize(node->right) + Count_R(node->left, x);
  295.         }
  296.         else {
  297.             return Count_R(node->right, x);
  298.         }
  299.     }
  300. };
  301.  
  302. class SegmentTree {
  303. public:
  304.     SegmentTree(const vector<int> a) {
  305.         n = 1;
  306.         while (n < (int)a.size()) {
  307.             n <<= 1;
  308.         }
  309.         tree.resize(2 * n);
  310.         build(a, 1, 0, n - 1);
  311.     }
  312.  
  313.     void update(int pos, int W, int U) {
  314.         update(1, 0, n - 1, pos, W, U);
  315.     }
  316.  
  317.     int query_L(int l, int r, int x) {
  318.         return query_L(1, 0, n - 1, l, r, x);
  319.     }
  320.  
  321.     int query_R(int l, int r, int x) {
  322.         return query_R(1, 0, n - 1, l, r, x);
  323.     }
  324.  
  325. private:
  326.     int n;
  327.     vector<Treap> tree;
  328.  
  329.     void build(const vector<int>& a, int v, int tl, int tr) {
  330.         if (tl == tr) {
  331.             if (tl < (int)a.size()) {
  332.                 tree[v].insert(a[tl]);
  333.             }
  334.         }
  335.         else {
  336.             int tm = (tl + tr) / 2;
  337.  
  338.             build(a, 2 * v, tl, tm);
  339.             build(a, 2 * v + 1, tm + 1, tr);
  340.  
  341.             for (int i = tl; i <= tr; ++i) {
  342.                 if (i < (int)a.size()) {
  343.                     tree[v].insert(a[i]);
  344.                 }
  345.             }
  346.         }
  347.     }
  348.  
  349.     void update(int v, int tl, int tr, int pos, int W, int U) {
  350.         if (tl == tr) {
  351.             tree[v].remove(W);
  352.             tree[v].insert(U);
  353.         }
  354.         else {
  355.             int tm = (tl + tr) / 2;
  356.             if (pos <= tm) {
  357.                 update(2 * v, tl, tm, pos, W, U);
  358.             }
  359.             else {
  360.                 update(2 * v + 1, tm + 1, tr, pos, W, U);
  361.             }
  362.             tree[v].remove(W);
  363.             tree[v].insert(U);
  364.         }
  365.     }
  366.  
  367.     int query_L(int v, int tl, int tr, int l, int r, int x) {
  368.         if (l > r || tl > r || tr < l) {
  369.             return 0;
  370.         }
  371.  
  372.         if (tl >= l && tr <= r) {
  373.             return tree[v].Count_L(x);
  374.         }
  375.  
  376.         int tm = (tl + tr) / 2;
  377.  
  378.         return query_L(2 * v, tl, tm, l, min(r, tm), x) +
  379.             query_L(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, x);
  380.     }
  381.  
  382.     int query_R(int v, int tl, int tr, int l, int r, int x) {
  383.         if (l > r || tl > r || tr < l) {
  384.             return 0;
  385.         }
  386.  
  387.         if (tl >= l && tr <= r) {
  388.             return tree[v].Count_R(x);
  389.         }
  390.  
  391.         int tm = (tl + tr) / 2;
  392.  
  393.         return query_R(2 * v, tl, tm, l, min(r, tm), x) +
  394.             query_R(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, x);
  395.     }
  396. };
  397.  
  398. void Solve() {
  399.     int n; cin >> n;
  400.  
  401.     vector<int> a(n);
  402.     for (int i = 0; i < n; i++) {
  403.         cin >> a[i];
  404.     }
  405.  
  406.     vector<int> base(n);
  407.     for (int i = 0; i < n; i++) {
  408.         base[i] = 0;
  409.     }
  410.  
  411.     SegmentTree LAST(base);
  412.  
  413.     map<int, int> last_id;
  414.     for (int i = 0; i < n; i++) {
  415.         last_id[a[i]] = -1;
  416.     }
  417.  
  418.     vector<int> last(n);
  419.     for (int i = 0; i < n; i++) {
  420.         LAST.update(i, 0, last_id[a[i]]);
  421.  
  422.         last[i] = 1'000'000 - last_id[a[i]];
  423.         last_id[a[i]] = i;
  424.     }
  425.  
  426.     SegmentTree FUTURE(base);
  427.  
  428.     map<int, int> future_id;
  429.     for (int i = 0; i < n; i++) {
  430.         future_id[a[i]] = n;
  431.     }
  432.  
  433.     vector<int> future(n);
  434.     for (int i = n - 1; i >= 0; i--) {
  435.         FUTURE.update(i, 0, future_id[a[i]]);
  436.  
  437.         future[i] = future_id[a[i]];
  438.         future_id[a[i]] = i;
  439.     }
  440.  
  441.     vector<int> X;
  442.     for (int i = 0; i < n; i++) {
  443.         X.push_back(last[i]);
  444.     }
  445.  
  446.     vector<int> Y;
  447.     for (int i = 0; i < n; i++) {
  448.         Y.push_back(future[i]);
  449.     }
  450.  
  451.     vector<pair<int, int>> points;
  452.     for (int i = 0; i < n; i++) {
  453.         points.push_back({ X[i], Y[i] });
  454.     }
  455.  
  456.     SegmentTree2D ST;
  457.     for (auto p : points) {
  458.         ST.update(p.first, p.second, 1);
  459.     }
  460.  
  461.     map<int, set<int>> POSITIONS;
  462.     for (int i = 0; i < n; i++) {
  463.         POSITIONS[a[i]].insert(i);
  464.     }
  465.     for (int i = 0; i < n; i++) {
  466.         if (POSITIONS[a[i]].find(-1) == POSITIONS[a[i]].end()) {
  467.             POSITIONS[a[i]].insert(-1);
  468.         }
  469.         if (POSITIONS[a[i]].find(n) == POSITIONS[a[i]].end()) {
  470.             POSITIONS[a[i]].insert(n);
  471.         }
  472.     }
  473.  
  474.     int q; cin >> q;
  475.     for (int i = 0; i < q; i++) {
  476.         string Type; cin >> Type;
  477.  
  478.         if (Type == "!") {
  479.             int pos, val; cin >> pos >> val;
  480.  
  481.             --pos;
  482.  
  483.             if (a[pos] == val) {
  484.                 continue;
  485.             }
  486.  
  487.             if (future[pos] != n) {
  488.                 LAST.update(future[pos], pos, 1'000'000 - last[pos]);
  489.                 ST.update(last[future[pos]], future[future[pos]], -1);
  490.             }
  491.             if (1'000'000 - last[pos] != -1) {
  492.                 FUTURE.update(1'000'000 - last[pos], pos, future[pos]);
  493.                 ST.update(last[1'000'000 - last[pos]], future[1'000'000 - last[pos]], -1);
  494.             }
  495.  
  496.             if (future[pos] != n) {
  497.                 last[future[pos]] = last[pos];
  498.                 ST.update(last[future[pos]], future[future[pos]], 1);
  499.             }
  500.             if (1'000'000 - last[pos] != -1) {
  501.                 future[1'000'000 - last[pos]] = future[pos];
  502.                 ST.update(last[1'000'000 - last[pos]], future[1'000'000 - last[pos]], 1);
  503.             }
  504.  
  505.             ST.update(last[pos], future[pos], -1);
  506.  
  507.             POSITIONS[a[pos]].erase(pos);
  508.             POSITIONS[val].insert(pos);
  509.  
  510.             if (POSITIONS[val].find(-1) == POSITIONS[val].end()) {
  511.                 POSITIONS[val].insert(-1);
  512.             }
  513.             if (POSITIONS[val].find(n) == POSITIONS[val].end()) {
  514.                 POSITIONS[val].insert(n);
  515.             }
  516.  
  517.             int Last_for_val = *(--POSITIONS[val].lower_bound(pos));
  518.             int Future_for_val = *POSITIONS[val].upper_bound(pos);
  519.  
  520.             LAST.update(pos, 1'000'000 - last[pos], Last_for_val);
  521.             FUTURE.update(pos, future[pos], Future_for_val);
  522.  
  523.             last[pos] = 1'000'000 - Last_for_val;
  524.             future[pos] = Future_for_val;
  525.  
  526.             a[pos] = val;
  527.  
  528.             ST.update(last[pos], future[pos], 1);
  529.  
  530.             if (Future_for_val != n) {
  531.                 LAST.update(Future_for_val, Last_for_val, pos);
  532.                 ST.update(last[Future_for_val], future[Future_for_val], -1);
  533.             }
  534.             if (Last_for_val != -1) {
  535.                 FUTURE.update(Last_for_val, Future_for_val, pos);
  536.                 ST.update(last[Last_for_val], future[Last_for_val], -1);
  537.             }
  538.  
  539.             if (Future_for_val != n) {
  540.                 last[Future_for_val] = 1'000'000 - pos;
  541.                 ST.update(last[Future_for_val], future[Future_for_val], 1);
  542.             }
  543.             if (Last_for_val != -1) {
  544.                 future[Last_for_val] = pos;
  545.                 ST.update(last[Last_for_val], future[Last_for_val], 1);
  546.             }
  547.         }
  548.         else {
  549.             int l, r; cin >> l >> r;
  550.  
  551.             --l;
  552.             --r;
  553.  
  554.             int min_X = 1'000'000 - l;
  555.             int min_Y = r;
  556.  
  557.             cout << ST.query(min_X + 1, min_Y + 1, inf, inf) - LAST.query_L(r + 1, n - 1, l - 1) - FUTURE.query_R(0, l - 1, r + 1) << endl;
  558.         }
  559.     }
  560. }
  561.  
  562. signed main() {
  563.     ios_base::sync_with_stdio(false);
  564.     cin.tie(0);
  565.     cout.tie(0);
  566.  
  567.     /*
  568.                       ________________
  569.                      / Just solved it \
  570.                      |   in my mind   |
  571.                      \________________/
  572.                     /
  573.                    /
  574. 　　　　　／＞　 フ         ___________
  575. 　　　　　| 　_　 _|       |          |
  576. 　 　　　／`ミ _x 彡       |   WA 2   |
  577. 　　 　 /　　　 　 |       |__________|
  578. 　　　 /　 ヽ　　 ﾉ        /          /
  579. 　／￣|　　 |　|　|       /_________ /
  580. 　| (￣ヽ＿_ヽ_)_)
  581. 　＼二つ
  582.  
  583.     */
  584.  
  585.     /*
  586.     freopen("input.txt", "r", stdin);
  587.     freopen("output.txt", "w", stdout);
  588.     */
  589.  
  590.     // auto start = chrono::high_resolution_clock::now();
  591.  
  592.     int multitest = false;
  593.     if (multitest == true) {
  594.         int ctt; cin >> ctt;
  595.  
  596.         for (int i = 0; i < ctt; i++) {
  597.             Solve();
  598.         }
  599.     }
  600.     else {
  601.         Solve();
  602.     }
  603.  
  604.     // auto end = chrono::high_resolution_clock::now();
  605.  
  606.     /*
  607.     cout << "Time taken: "
  608.          << chrono::duration_cast<chrono::milliseconds>(end - start).count()
  609.          << " milliseconds" << endl;
  610.     */
  611.  
  612.     return 0;
  613. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:29:10: fatal error: ranges: No such file or directory
 #include <ranges>
          ^~~~~~~~
compilation terminated.
stdout
copy 
Standard output is empty
https://ideone.com/ciuyJb
language:
C++14 (gcc 8.3)
created:
315 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!