fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define FastIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  3. #define sino(b) cout<<(b ? "YES\n":"NO\n")
  4. #define casos(t) int t; cin >> t; while(t--)
  5. #define print(b) cout << (b) << endl
  6. #define input(n, a) for(int i=0; i<n; ++i) cin>>a[i];
  7. #define ln cout<<endl
  8. #define pb push_back
  9. #define pf push_front
  10. #define pob pop_back
  11. #define pof pop_front
  12. #define forn(i,n) for(int i=0; i < int(n); ++i)
  13. #define F first
  14. #define S second
  15. #define sz(x) int((x).size())
  16. #define sDBG(x) for(auto &el : x) {cout << el << " ";} cout<<endl;
  17. #define DBG(x) cout << #x << " = " << x << endl;
  18. #define DBGMap(x) for(auto &el : x) {cout << el.F << ": " << el.S ;} cout<<endl;
  19. #define all(i) i.begin(), i.end()
  20. #define rall(x) (x).rbegin(), (x).rend()
  21. #define stp(a,b) cout << fixed << setprecision(a) <<(b) << endl;
  22. #define lw(c, x) int(lower_bound((c).begin(), (c).end(), (x)) - (c).begin())
  23. #define up(c, x) int(upper_bound((c).begin(), (c).end(), (x)) - (c).begin())
  24. #define kill(x) {cout << x << endl; return;}
  25. using namespace std;
  26. typedef long long ll;
  27. typedef long double ld;
  28. typedef pair<int,int> pii;
  29. typedef pair<int,pii> piii;
  30. typedef pair<long long ,long long> pll;
  31. typedef vector<int> vi;
  32. typedef vector<ll> vl;
  33. typedef vector<pii> vii;
  34.  
  35. const int MAXN = 2e5 + 5;
  36. int arr[MAXN];
  37. int freq[MAXN];
  38. int cnt_distinct = 0;
  39. int block_size;
  40.  
  41. void add(int idx) {
  42.     int val = arr[idx];
  43.     if (freq[val] == 0) cnt_distinct++;
  44.     freq[val]++;
  45. }
  46.  
  47. void remove(int idx) {
  48.     int val = arr[idx];
  49.     freq[val]--;
  50.     if (freq[val] == 0) cnt_distinct--;
  51. }
  52.  
  53. int get_answer() {
  54.     return cnt_distinct;
  55. }
  56.  
  57. struct Query {
  58.     int l, r, idx;
  59.  
  60.     bool operator<(const Query& other) const {
  61.         int b1 = l / block_size;
  62.         int b2 = other.l / block_size;
  63.         if (b1 != b2) return b1 < b2;
  64.         return (b1 & 1) ? (r < other.r) : (r > other.r);
  65.     }
  66. };
  67.  
  68. void solve() {
  69.     int n, q;
  70.  
  71.     forn(i, n) cin >> arr[i];
  72.  
  73.     block_size = max(1, (int)sqrt(n));
  74.  
  75.     vector<Query> queries(q);
  76.     forn(i, q) {
  77.         cin >> queries[i].l >> queries[i].r;
  78.         queries[i].idx = i;
  79.     }
  80.  
  81.     sort(all(queries));
  82.  
  83.     vi ans(q);
  84.     int cur_l = 0, cur_r = -1;
  85.     cnt_distinct = 0;
  86.  
  87.     for (auto &q : queries) {
  88.         while (cur_l > q.l) { cur_l--; add(cur_l); }
  89.         while (cur_r < q.r) { cur_r++; add(cur_r); }
  90.         while (cur_l < q.l) { remove(cur_l); cur_l++; }
  91.         while (cur_r > q.r) { remove(cur_r); cur_r--; }
  92.  
  93.         ans[q.idx] = get_answer();
  94.     }
  95.  
  96.     for (int i = cur_l; i <= cur_r; i++) freq[arr[i]] = 0;
  97.  
  98.     forn(i, q) print(ans[i]);
  99. }
  100.  
  101. int main() {
  102.     FastIO;
  103.     solve();
  104.     return 0;
  105. }
  106.  
  107. // (づ｡◕‿‿◕｡)づ 1811
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/rq92Xg
language:
C++14 (gcc 8.3)
created:
2 hours 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!