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. struct PersistentImplicitSegmentTree {
  79.     struct Node {
  80.         int sum;
  81.         Node* left;
  82.         Node* right;
  83.  
  84.         Node() : sum(0), left(nullptr), right(nullptr) {}
  85.         Node(Node* left, Node* right, int sum) : left(left), right(right), sum(sum) {}
  86.     };
  87.  
  88.     PersistentImplicitSegmentTree(int size) : n(size) {
  89.         roots.push_back(nullptr);
  90.     }
  91.  
  92.     void change(int pos, int val) {
  93.         Current_root = updatePoint(Current_root, 0, n - 1, pos, val);
  94.     }
  95.  
  96.     int query_v(int version, int l, int r) {
  97.         return queryRange(roots[version], 0, n - 1, l, r);
  98.     }
  99.  
  100.     Node* Current_root = nullptr;
  101.     vector<Node*> roots;
  102.     int n;
  103.  
  104.     Node* updatePoint(Node* node, int l, int r, int pos, int val) {
  105.         if (!node) {
  106.             node = new Node();
  107.         }
  108.  
  109.         if (l == r) {
  110.             return new Node(nullptr, nullptr, val);
  111.         }
  112.  
  113.         int mid = l + (r - l) / 2;
  114.         Node* newNode = new Node(*node);
  115.  
  116.         if (pos <= mid) {
  117.             newNode->left = updatePoint(node->left, l, mid, pos, val);
  118.         }
  119.         else {
  120.             newNode->right = updatePoint(node->right, mid + 1, r, pos, val);
  121.         }
  122.  
  123.         newNode->sum = (newNode->left ? newNode->left->sum : 0) + (newNode->right ? newNode->right->sum : 0);
  124.  
  125.         return newNode;
  126.     }
  127.  
  128.     int queryRange(Node* node, int l, int r, int const_l, int const_r) {
  129.         if (!node) {
  130.             return 0;
  131.         }
  132.  
  133.         if (const_l > r || const_r < l) {
  134.             return 0;
  135.         }
  136.  
  137.         if (const_l <= l && r <= const_r) {
  138.             return node->sum;
  139.         }
  140.  
  141.         int mid = l + (r - l) / 2;
  142.  
  143.         int leftSum = queryRange(node->left, l, mid, const_l, const_r);
  144.         int rightSum = queryRange(node->right, mid + 1, r, const_l, const_r);
  145.  
  146.         return leftSum + rightSum;
  147.     }
  148. };
  149.  
  150. void Solve() {
  151.     int n; cin >> n;
  152.     vector<int> a(n);
  153.     for (int i = 0; i < n; i++) {
  154.         cin >> a[i];
  155.     }
  156.  
  157.     map<int, int> last;
  158.     for (int i = 0; i < n; i++) {
  159.         last[a[i]] = -1;
  160.     }
  161.  
  162.     map<int, int> last_last;
  163.     for (int i = 0; i < n; i++) {
  164.         last_last[a[i]] = -1;
  165.     }
  166.  
  167.     PersistentImplicitSegmentTree ST(inf);
  168.     for (int i = 0; i < n; i++) {
  169.         if (last[a[i]] == -1 && last_last[a[i]] == -1) {
  170.             ST.change(i, 1);
  171.  
  172.             last[a[i]] = i;
  173.         }
  174.         else if (last[a[i]] != -1 && last_last[a[i]] == -1) {
  175.             ST.change(i, 1);
  176.             ST.change(last[a[i]], -1);
  177.  
  178.             last_last[a[i]] = last[a[i]];
  179.             last[a[i]] = i;
  180.         }
  181.         else {
  182.             ST.change(i, 1);
  183.             ST.change(last[a[i]], -1);
  184.             ST.change(last_last[a[i]], 0);
  185.  
  186.             last_last[a[i]] = last[a[i]];
  187.             last[a[i]] = i;
  188.         }
  189.  
  190.         ST.roots.push_back(ST.Current_root);
  191.     }
  192.  
  193.     int q; cin >> q;
  194.     for (int i = 0; i < q; i++) {
  195.         int l, r; cin >> l >> r;
  196.  
  197.         --l;
  198.         --r;
  199.  
  200.         cout << ST.query_v(r + 1, l, r) << endl;
  201.     }
  202. }
  203.  
  204. signed main() {
  205.     ios_base::sync_with_stdio(false);
  206.     cin.tie(0);
  207.     cout.tie(0);
  208.  
  209.     /*
  210.                       ________________
  211.                      / Just solved it \
  212.                      |   in my mind   |
  213.                      \________________/
  214.                     /
  215.                    /
  216. 　　　　　／＞　 フ         ___________
  217. 　　　　　| 　_　 _|       |          |
  218. 　 　　　／`ミ _x 彡       |   WA 2   |
  219. 　　 　 /　　　 　 |       |__________|
  220. 　　　 /　 ヽ　　 ﾉ        /          /
  221. 　／￣|　　 |　|　|       /_________ /
  222. 　| (￣ヽ＿_ヽ_)_)
  223. 　＼二つ
  224.  
  225.     */
  226.  
  227.     /*
  228.     freopen("input.txt", "r", stdin);
  229.     freopen("output.txt", "w", stdout);
  230.     */
  231.  
  232.     // auto start = chrono::high_resolution_clock::now();
  233.  
  234.     int multitest = false;
  235.     if (multitest == true) {
  236.         int ctt; cin >> ctt;
  237.  
  238.         for (int i = 0; i < ctt; i++) {
  239.             Solve();
  240.         }
  241.     }
  242.     else {
  243.         Solve();
  244.     }
  245.  
  246.     // auto end = chrono::high_resolution_clock::now();
  247.  
  248.     /*
  249.     cout << "Time taken: "
  250.          << chrono::duration_cast<chrono::milliseconds>(end - start).count()
  251.          << " milliseconds" << endl;
  252.     */
  253.  
  254.     return 0;
  255. }
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/1jsy5o
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!