Advertisement
Guest User

Untitled

a guest
Jan 21st, 2017
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.07 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int BLK = 707;
  5. int n, m, a[500001], res[500001], out[500001];
  6. vector<pair<pair<int,int>,int> > q;
  7. unordered_map<int,int > cnt;
  8. int main() {
  9.     scanf("%d%d",&n,&m);
  10.     for(int i = 1; i <= n; i++) scanf("%d",a+i);
  11.     for(int i = 0, l, r; i < m; i++) scanf("%d%d",&l,&r), q.emplace_back(make_pair(l, r), i);
  12.     sort(q.begin(), q.end(), [] (pair<pair<int,int>, int> a, pair<pair<int,int>, int> b) {
  13.         return (a.first.first/BLK < b.first.first/BLK || (a.first.first/BLK == b.first.first/BLK && a.first.second < b.first.second));
  14.     });
  15.     int l = 1,r = 1;
  16.     cnt[a[1]] = 1;
  17.     res[1] = 1;
  18.     for(auto p: q) {
  19.         int lf, rg;
  20.         tie(lf, rg) = p.first;
  21.         while(l < lf) res[cnt[a[l]]--]--, res[cnt[a[l++]]]++;
  22.         while(l > lf) res[cnt[a[--l]]++]--, res[cnt[a[l]]]++;
  23.         while(r < rg) res[cnt[a[++r]]++]--, res[cnt[a[r]]]++;
  24.         while(r > rg) res[cnt[a[r]]--]--, res[cnt[a[r--]]]++;
  25.         out[p.second] = res[2];
  26.     }
  27.     for(int i = 0; i < m; i++) printf("%d\n", out[i]);
  28. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement