//cct de problema am cod de 67 asta e foarte aproape dar cu un cct de arbore cand nu e bine sa simulezi direct
#pragma GCC optimize("O3,unroll-loops")
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
struct Node {
int minpoz;
int st, dr;
};
struct Query {
int left, right, ind;
};
int n, q;
int cnt;
int v[600005];
pair<int, int> qs[600005];
Node pool[15000005];
int root[600005];
vector<Query> qs_mex[400005];
int nxt[600005];
int freq[400005];
// Folosim array-uri flat în loc de vector<vector<int>> pentru a
// elimina overhead-ul de alocare memorie în timpul testelor mari
int head[600005], next_node[600005];
int q_head[600005], q_next[600005], q_left[600005], q_ind[600005];
int q_cnt = 0;
int path_st[600005];
int path_sz = 0;
int rez_arr[600005];
void update(int cur, int prev, int left, int right, int poz, int val) {
if(left == right) {
pool[cur].minpoz = val;
return;
}
int mij = (left + right) / 2;
if(poz <= mij) {
cnt++;
pool[cur].st = cnt;
pool[pool[cur].st] = pool[pool[prev].st];
pool[cur].dr = pool[prev].dr;
update(pool[cur].st, pool[prev].st, left, mij, poz, val);
} else {
cnt++;
pool[cur].dr = cnt;
pool[pool[cur].dr] = pool[pool[prev].dr];
pool[cur].st = pool[prev].st;
update(pool[cur].dr, pool[prev].dr, mij+1, right, poz, val);
}
pool[cur].minpoz = min(pool[pool[cur].st].minpoz, pool[pool[cur].dr].minpoz);
}
int find_mex(int node, int left, int right, int st) {
if(left == right) return left;
int mij = (left + right) / 2;
if(pool[pool[node].st].minpoz < st) {
return find_mex(pool[node].st, left, mij, st);
} else {
return find_mex(pool[node].dr, mij+1, right, st);
}
}
int query_st(int node, int left, int right, int qleft, int qright) {
if(qright < left || right < qleft) return n + 1;
if(qleft <= left && right <= qright) return pool[node].minpoz;
int mij = (left + right) / 2;
return min(query_st(pool[node].st, left, mij, qleft, qright),
query_st(pool[node].dr, mij + 1, right, qleft, qright));
}
// DFS-ul calculează câte segmente se pot forma folosind o căutare binară
// pe path-ul părinților, direct în O(log N) per query.
void dfs(int u) {
path_st[path_sz++] = u - 1; // adăugăm nodul pe stack (adjustat cu indexul original)
// Răspundem offline la toate query-urile care se termină în nodul curent `u`
for (int e = q_head[u]; e != -1; e = q_next[e]) {
int L_bound = q_left[e] - 1;
int* it = std::lower_bound(path_st, path_st + path_sz, L_bound);
int idx = it - path_st;
int ans = path_sz - 1 - idx;
if(ans < 0) ans = 0;
rez_arr[q_ind[e] - 1] = ans;
}
// Continuăm DFS-ul în copiii din arbore
for (int v = head[u]; v != -1; v = next_node[v]) {
dfs(v + 1);
}
path_sz--;
}
std::vector<int> solve(int N, std::vector<int> &init, int Q, std::vector<std::pair<int, int>> &initqs) {
n = N;
q = Q;
for(int i = 0; i < n; i++) v[i + 1] = init[i];
for(int i = 0; i < q; i++) {
qs[i + 1] = initqs[i];
qs[i + 1].first++;
qs[i + 1].second++;
}
// Resetăm tot ce e global (fiind funcție `solve`, e best practice)
cnt = 0;
for(int i = 0; i <= 400002; i++) {
qs_mex[i].clear();
}
for(int i = 1; i <= n; i++) {
cnt++;
root[i] = cnt;
update(root[i], root[i - 1], 1, 400005, v[i], i);
}
for(int i = 1; i <= q; i++) {
int mex = find_mex(root[qs[i].second], 1, 400005, qs[i].first);
if(mex == 1) {
rez_arr[i - 1] = qs[i].second - qs[i].first + 1;
continue;
}
qs_mex[mex].push_back({qs[i].first, qs[i].second, i});
}
// Aici era bug-ul! Iterezi DOAR până la max posibil MEX (400002)
for(int i = 2; i <= 400002; i++) {
if(qs_mex[i].empty()) continue;
// Calculăm ce ne-ar costa cele 2 metode
long long cost_sim = 1LL * qs_mex[i].size() * (n / i) * 15LL;
long long cost_dfs = n;
if (cost_dfs < cost_sim) {
// Metoda 1: Two Pointers + Arbore DFS (Când avem multe query-uri sau M mic)
int distinct = 0;
for(int j = 0; j <= i; j++) freq[j] = 0;
int L = 1;
for (int r = 1; r <= n; r++) {
if (v[r] < i) {
if (freq[v[r]] == 0) distinct++;
freq[v[r]]++;
}
while (distinct == i - 1) {
if (v[L] < i) {
if (freq[v[L]] == 1) break;
freq[v[L]]--;
}
L++;
}
if (distinct == i - 1) nxt[r] = L;
else nxt[r] = 0;
}
// Construim legăturile pentru DFS
for(int j = -1; j <= n; j++) {
head[j + 1] = -1;
q_head[j + 1] = -1;
}
for (int r = 1; r <= n; r++) {
int p = nxt[r] - 1;
if (p < 0) p = -1;
next_node[r] = head[p + 1];
head[p + 1] = r;
}
q_cnt = 0;
for (auto it : qs_mex[i]) {
int u = it.right;
q_left[q_cnt] = it.left;
q_ind[q_cnt] = it.ind;
q_next[q_cnt] = q_head[u + 1];
q_head[u + 1] = q_cnt++;
}
// Root node-urile virtuale (-1 și 0 mapate cu shift de +1)
path_sz = 0;
dfs(0);
dfs(1);
} else {
// Metoda 2: Simularea originală folosind Persistent Segment Tree
for(auto it: qs_mex[i]) {
int ans = 0;
int cur = it.right;
while(cur >= it.left) {
int nxt_val = query_st(root[cur], 1, 400005, 1, i - 1);
if(nxt_val < it.left) break;
ans++;
cur = nxt_val - 1;
}
rez_arr[it.ind - 1] = ans;
}
}
}
vector<int> rez(q);
for(int i = 0; i < q; i++) {
rez[i] = rez_arr[i];
}
return rez;
}
