Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int BLK = 707;
- int n, m, a[500001], res[500001], out[500001];
- vector<pair<pair<int,int>,int> > q;
- unordered_map<int,int > cnt;
- int main() {
- scanf("%d%d",&n,&m);
- for(int i = 1; i <= n; i++) scanf("%d",a+i);
- for(int i = 0, l, r; i < m; i++) scanf("%d%d",&l,&r), q.emplace_back(make_pair(l, r), i);
- sort(q.begin(), q.end(), [] (pair<pair<int,int>, int> a, pair<pair<int,int>, int> b) {
- return (a.first.first/BLK < b.first.first/BLK || (a.first.first/BLK == b.first.first/BLK && a.first.second < b.first.second));
- });
- int l = 1,r = 1;
- cnt[a[1]] = 1;
- res[1] = 1;
- for(auto p: q) {
- int lf, rg;
- tie(lf, rg) = p.first;
- while(l < lf) res[cnt[a[l]]--]--, res[cnt[a[l++]]]++;
- while(l > lf) res[cnt[a[--l]]++]--, res[cnt[a[l]]]++;
- while(r < rg) res[cnt[a[++r]]++]--, res[cnt[a[r]]]++;
- while(r > rg) res[cnt[a[r]]--]--, res[cnt[a[r--]]]++;
- out[p.second] = res[2];
- }
- for(int i = 0; i < m; i++) printf("%d\n", out[i]);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement