Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int MAXN = 3e4 + 10;
- vector<tuple<int, int, int> > queries;
- set<int> poss;
- map<int, int> Comp;
- int Freq[MAXN];
- int FFreq[MAXN];
- int temp[MAXN];
- int resp[MAXN];
- int T;
- bool cmp(tuple<int, int, int> a, tuple<int, int, int> b)
- {
- auto [aP, aQ, aId] = a;
- auto [bP, bQ, bId] = b;
- if (aP / T == bP / T) return aQ < bQ;
- return aP < bP;
- }
- void add(int x)
- {
- Freq[x]++;
- FFreq[Freq[x]]++;
- }
- void remove(int x)
- {
- FFreq[Freq[x]]--;
- Freq[x]--;
- }
- int BUSCA_BINARIA(int N)
- {
- int ini = 1; int fim = N;
- while (ini < fim)
- {
- int m = (ini + fim) / 2;
- if (ini == fim-1) m = fim;
- if (m <= FFreq[m]) ini = m;
- else fim = m-1;
- }
- return ini;
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- int N, Q;
- cin >> N >> Q;
- T = sqrt(N) + 1;
- for (int i = 1; i <= N; i++) {cin >> temp[i]; poss.insert(temp[i]);}
- int count = 0;
- for (auto t : poss) Comp[t] = ++count;
- for (int i = 1; i <= N; i++) temp[i] = Comp[temp[i]];
- for (int q = 1; q <= Q; q++)
- {
- int X, Y;
- cin >> X >> Y;
- queries.emplace_back(X, Y, q);
- }
- sort(queries.begin(), queries.end(), cmp);
- int p = get<0>(queries[0]); int q = get<1>(queries[0]);
- for (int i = p; i <= q; i++) add(temp[i]);
- for (auto query : queries)
- {
- auto [l, r, id] = query;
- // cerr << p << " " << q << " " << l << " " << r << '\n';
- while (p > l) add(temp[--p]);
- while (q < r) add(temp[++q]);
- while (p < l) remove(temp[p++]);
- while (q > r) remove(temp[q--]);
- resp[id] = BUSCA_BINARIA(N);
- }
- for (int i = 1; i <= Q; i++) cout << resp[i] << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
