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. int BLOCK_SIZE = 1000;
  79.  
  80. struct Trio {
  81.     int First;
  82.     int Second;
  83.     int Third; // 1 -> Query ---> First == l; Second == r;
  84.     // 2 -> Update ---> First = ind; Second == new_elem;
  85. };
  86.  
  87. class Mo3D {
  88. public:
  89.     struct QUERY {
  90.         int l, r, t, id;
  91.  
  92.         bool operator<(const QUERY& other) const {
  93.             int block1_l = l / BLOCK_SIZE;
  94.             int block2_l = other.l / BLOCK_SIZE;
  95.  
  96.             if (block1_l != block2_l) {
  97.                 return block1_l < block2_l;
  98.             }
  99.  
  100.             int block1_r = r / BLOCK_SIZE;
  101.             int block2_r = other.r / BLOCK_SIZE;
  102.  
  103.             if (block1_r != block2_r) {
  104.                 return block1_r < block2_r;
  105.             }
  106.  
  107.             return t > other.t;
  108.         }
  109.     };
  110.  
  111.  
  112.  
  113.  
  114.  
  115.     // --- STATE --- //
  116.  
  117.     map<int, int> cnt;
  118.     int z = 0;
  119.  
  120.     void ADD(int G) {
  121.         cnt[a[G]] += 1;
  122.  
  123.         if (cnt[a[G]] == 0) {
  124.             // no changes
  125.         }
  126.         else if (cnt[a[G]] == 1) {
  127.             ++z;
  128.         }
  129.         else if (cnt[a[G]] == 2) {
  130.             --z;
  131.         }
  132.         else {
  133.             // no changes
  134.         }
  135.     }
  136.  
  137.     void REM(int G) {
  138.         cnt[a[G]] -= 1;
  139.  
  140.         if (cnt[a[G]] == 0) {
  141.             --z;
  142.         }
  143.         else if (cnt[a[G]] == 1) {
  144.             ++z;
  145.         }
  146.         else if (cnt[a[G]] == 2) {
  147.             // no changes
  148.         }
  149.         else {
  150.             // no changes
  151.         }
  152.     }
  153.  
  154.     void ADD_TIME() {
  155.         auto pos_newval = changes[T];
  156.  
  157.         int pos = pos_newval.first;
  158.         int newval = pos_newval.second;
  159.  
  160.         if (pos >= L && pos <= R) {
  161.             cnt[a[pos]] -= 1;
  162.  
  163.             if (cnt[a[pos]] == 0) {
  164.                 --z;
  165.             }
  166.             else if (cnt[a[pos]] == 1) {
  167.                 ++z;
  168.             }
  169.             else if (cnt[a[pos]] == 2) {
  170.                 // no changes
  171.             }
  172.             else {
  173.                 // no changes
  174.             }
  175.  
  176.             cnt[newval] += 1;
  177.  
  178.             if (cnt[newval] == 0) {
  179.                 // no changes
  180.             }
  181.             else if (cnt[newval] == 1) {
  182.                 ++z;
  183.             }
  184.             else if (cnt[newval] == 2) {
  185.                 --z;
  186.             }
  187.             else {
  188.                 // no changes
  189.             }
  190.         }
  191.  
  192.         a[pos] = newval;
  193.     }
  194.  
  195.     void REM_TIME() {
  196.         auto pos_oldval = unchanges[T];
  197.  
  198.         int pos = pos_oldval.first;
  199.         int oldval = pos_oldval.second;
  200.  
  201.         if (pos >= L && pos <= R) {
  202.             cnt[a[pos]] -= 1;
  203.  
  204.             if (cnt[a[pos]] == 0) {
  205.                 --z;
  206.             }
  207.             else if (cnt[a[pos]] == 1) {
  208.                 ++z;
  209.             }
  210.             else if (cnt[a[pos]] == 2) {
  211.                 // no changes
  212.             }
  213.             else {
  214.                 // no changes
  215.             }
  216.  
  217.             cnt[oldval] += 1;
  218.  
  219.             if (cnt[oldval] == 0) {
  220.                 // no changes
  221.             }
  222.             else if (cnt[oldval] == 1) {
  223.                 ++z;
  224.             }
  225.             else if (cnt[oldval] == 2) {
  226.                 --z;
  227.             }
  228.             else {
  229.                 // no changes
  230.             }
  231.         }
  232.  
  233.         a[pos] = oldval;
  234.     }
  235.  
  236.     void add_time() {
  237.         T++;
  238.         ADD_TIME();
  239.     }
  240.  
  241.     void rem_time() {
  242.         REM_TIME();
  243.         T--;
  244.     }
  245.  
  246.     void add_right() {
  247.         R++;
  248.         ADD(R);
  249.     }
  250.  
  251.     void add_left() {
  252.         L--;
  253.         ADD(L);
  254.     }
  255.  
  256.     void rem_right() {
  257.         REM(R);
  258.         R--;
  259.     }
  260.  
  261.     void rem_left() {
  262.         REM(L);
  263.         L++;
  264.     }
  265.  
  266.     auto get_ans() {
  267.         return z;
  268.     }
  269.  
  270.     // --- STATE --- //
  271.  
  272.  
  273.  
  274.  
  275.  
  276.     Mo3D(vector<Trio> Q_, vector<int> a_) : a(a_), ended_a(a_) {
  277.         BLOCK_SIZE = (int)cbrtl(pow((int)a.size(), 2)) + 1;
  278.  
  279.         int t = -1; int j = 0;
  280.         for (int i = 0; i < (int)Q_.size(); i++) {
  281.             if (Q_[i].Third == 1) {
  282.                 Q.push_back({ Q_[i].First, Q_[i].Second, t, j });
  283.                 ++j;
  284.             }
  285.             else {
  286.                 ++t;
  287.                 changes.push_back({ Q_[i].First, Q_[i].Second });
  288.                 unchanges.push_back({ Q_[i].First, ended_a[Q_[i].First] });
  289.                 ended_a[Q_[i].First] = Q_[i].Second;
  290.             }
  291.         }
  292.         sort(Q.begin(), Q.end());
  293.  
  294.         ans.resize((int)Q.size());
  295.         L = 0; R = -1, T = -1;
  296.     }
  297.  
  298.     void GO() {
  299.         for (int i = 0; i < (int)ans.size(); i++) {
  300.             while (R < Q[i].r) {
  301.                 add_right();
  302.             }
  303.  
  304.             while (L > Q[i].l) {
  305.                 add_left();
  306.             }
  307.  
  308.             while (R > Q[i].r) {
  309.                 rem_right();
  310.             }
  311.  
  312.             while (L < Q[i].l) {
  313.                 rem_left();
  314.             }
  315.  
  316.             while (T < Q[i].t) {
  317.                 add_time();
  318.             }
  319.  
  320.             while (T > Q[i].t) {
  321.                 rem_time();
  322.             }
  323.  
  324.             ans[Q[i].id] = get_ans();
  325.         }
  326.     }
  327.  
  328.     void print_ans() {
  329.         for (auto p : ans) {
  330.             cout << p << ' ';
  331.         }
  332.     }
  333.  
  334. private:
  335.     vector<int> ans;
  336.  
  337.     vector<QUERY> Q;
  338.     vector<int> a, ended_a;
  339.  
  340.     vector<pair<int, int>> changes;
  341.     vector<pair<int, int>> unchanges;
  342.  
  343.     int L, R, T;
  344. };
  345.  
  346. void Solve() {
  347.     int n; cin >> n;
  348.     vector<int> a(n);
  349.     for (int i = 0; i < n; i++) {
  350.         cin >> a[i];
  351.     }
  352.  
  353.     vector<Trio> Q;
  354.  
  355.     int q; cin >> q;
  356.     for (int i = 0; i < q; i++) {
  357.         string Type; cin >> Type;
  358.  
  359.         if (Type == "!") {
  360.             int pos, val; cin >> pos >> val;
  361.             --pos;
  362.             Q.push_back({ pos, val, 2 });
  363.         }
  364.         else {
  365.             int l, r; cin >> l >> r;
  366.             --l;
  367.             --r;
  368.             Q.push_back({ l, r, 1 });
  369.         }
  370.     }
  371.  
  372.     Mo3D W(Q, a); W.GO();
  373.     W.print_ans();
  374. }
  375.  
  376. signed main() {
  377.     ios_base::sync_with_stdio(false);
  378.     cin.tie(0);
  379.     cout.tie(0);
  380.  
  381.     /*
  382.                       ________________
  383.                      / Just solved it \
  384.                      |   in my mind   |
  385.                      \________________/
  386.                     /
  387.                    /
  388. 　　　　　／＞　 フ         ___________
  389. 　　　　　| 　_　 _|       |          |
  390. 　 　　　／`ミ _x 彡       |   WA 2   |
  391. 　　 　 /　　　 　 |       |__________|
  392. 　　　 /　 ヽ　　 ﾉ        /          /
  393. 　／￣|　　 |　|　|       /_________ /
  394. 　| (￣ヽ＿_ヽ_)_)
  395. 　＼二つ
  396.  
  397.     */
  398.  
  399.     /*
  400.     freopen("input.txt", "r", stdin);
  401.     freopen("output.txt", "w", stdout);
  402.     */
  403.  
  404.     // auto start = chrono::high_resolution_clock::now();
  405.  
  406.     int multitest = false;
  407.     if (multitest == true) {
  408.         int ctt; cin >> ctt;
  409.  
  410.         for (int i = 0; i < ctt; i++) {
  411.             Solve();
  412.         }
  413.     }
  414.     else {
  415.         Solve();
  416.     }
  417.  
  418.     // auto end = chrono::high_resolution_clock::now();
  419.  
  420.     /*
  421.     cout << "Time taken: "
  422.          << chrono::duration_cast<chrono::milliseconds>(end - start).count()
  423.          << " milliseconds" << endl;
  424.     */
  425.  
  426.     return 0;
  427. }
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/K0ne3K
language:
C++14 (gcc 8.3)
created:
323 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!