23:I[344796,["/_next/static/chunks/083cs_iw_ie0y.js","/_next/static/chunks/2p-3dpla3vag0.js","/_next/static/chunks/00mfjk9z2ewie.js","/_next/static/chunks/0ynk8uq7fqs0l.js","/_next/static/chunks/0uf80u9-0x190.js","/_next/static/chunks/14j8vn9k5ltv3.js","/_next/static/chunks/3j3dyiamo-u3s.js","/_next/static/chunks/10fiiv3_svxbv.js"],"default"] 2b:I[27201,["/_next/static/chunks/083cs_iw_ie0y.js","/_next/static/chunks/2p-3dpla3vag0.js","/_next/static/chunks/00mfjk9z2ewie.js","/_next/static/chunks/0ynk8uq7fqs0l.js","/_next/static/chunks/0uf80u9-0x190.js","/_next/static/chunks/14j8vn9k5ltv3.js","/_next/static/chunks/3j3dyiamo-u3s.js"],"IconMark"] 24:Tb34,

Online Occurrences

You are given an array a of length n (1-indexed).

For a subarray from index l to index r (inclusive), define beauty(l, r) as the maximum integer x such that the value x appears at least x times in the subarray a[l..r]. If no positive integer satisfies this, beauty(l, r) = 0.

You are given q queries. Each query provides two integers l and r. The queries are encoded (online): let S be the sum of the answers to all previous queries (for the first query, S = 0). Before answering query i, decode l and r as follows:

l = ((l + S - 1) mod n) + 1
r = ((r + S - 1) mod n) + 1
if l > r, then swap l and r.

The answer to query i is beauty(l, r) on the decoded indices. Note that S is the running sum of decoded answers and is used (not reduced modulo anything) when decoding subsequent queries.

Output a single integer: the sum of the answers to all q queries, taken modulo 10⁹+7.

Input format

The first line contains two integers n and q.
The second line contains n integers a[1], a[2], …, a[n].
Each of the next q lines contains two integers l and r (the encoded query values).

Output format

Print a single integer — the sum of all query answers modulo 10⁹+7.

Constraints

1 ≤ n ≤ 2 × 10⁵
1 ≤ q ≤ 2 × 10⁵
0 ≤ a[i] ≤ 10⁹
0 ≤ l, r ≤ 10⁹ (encoded values; they are decoded as described above)

Example

Input:

Output:

Explanation: n = 3, array = [2, 2, 2].

Query 1: S = 0. l = ((1 + 0 - 1) mod 3) + 1 = 1, r = ((1 + 0 - 1) mod 3) + 1 = 1. Subarray a[1..1] = [2]; value 2 appears 1 time (< 2), so beauty = 0.
Query 2: S = 0. l = ((1 - 1) mod 3) + 1 = 1, r = ((3 - 1) mod 3) + 1 = 3. Subarray a[1..3] = [2, 2, 2]; value 2 appears 3 times (≥ 2), so beauty = 2.

Sum = 0 + 2 = 2.

Function description

Your program reads from standard input and writes to standard output exactly as described in the Input/Output format above.

25:T9fb,#include using namespace std; static const long long MOD = 1000000007LL; // Persistent segment tree over positions [1..n], storing max "beauty value" // reachable for a window starting at some s>=l and ending at e<=r. // For each value v with occurrence positions p[0..c-1], every window of v // consecutive occurrences [p[i], p[i+v-1]] contributes value v at start p[i] // with end p[i+v-1]. Sweeping starts s from n down to 1, we add all points // whose start == s into a persistent segtree keyed by end position holding // max value. Query for (l,r): on the root for start s=l, take max value over // ends <= r. This yields beauty(l,r). int n; vector L, R, V; int newNode(){ L.push_back(0); R.push_back(0); V.push_back(0); return (int)V.size()-1; } int update(int prev,int lo,int hi,int idx,int w){ int cur=newNode(); L[cur]=L[prev]; R[cur]=R[prev]; V[cur]=V[prev]; if(lo==hi){ V[cur]=max(V[cur],w); return cur; } int mid=(lo+hi)>>1; if(idx<=mid) L[cur]=update(L[prev],lo,mid,idx,w); else R[cur]=update(R[prev],mid+1,hi,idx,w); int lv = L[cur]?V[L[cur]]:0, rv = R[cur]?V[R[cur]]:0; V[cur]=max(lv,rv); return cur; } int query(int node,int lo,int hi,int qr){ if(!node||qr<=0) return 0; if(hi<=qr) return V[node]; int mid=(lo+hi)>>1; int res=query(L[node],lo,mid,qr); if(qr>mid) res=max(res,query(R[node],mid+1,hi,qr)); return res; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int q; if(!(cin>>n>>q)) return 0; vector a(n+1); int mx=0; for(int i=1;i<=n;i++){ cin>>a[i]; mx=max(mx,a[i]); } vector> pos(mx+1); for(int i=1;i<=n;i++) if(a[i]>=1) pos[a[i]].push_back(i); // buckets[s] = list of (end, value) vector>> buckets(n+2); for(int v=1;v<=mx;v++){ int c=(int)pos[v].size(); if(c>=v) for(int i=0;i+v-1 root(n+2,0); for(int s=n;s>=1;s--){ int cur=root[s+1]; for(auto &pe:buckets[s]) cur=update(cur,1,n,pe.first,pe.second); root[s]=cur; } long long pref=0,total=0; for(int i=0;i>l0>>r0; long long l=((l0+pref-1)%n+n)%n+1; long long r=((r0+pref-1)%n+n)%n+1; if(l>r) swap(l,r); int ans=query(root[(int)l],1,n,(int)r); total=(total+ans)%MOD; pref=(pref+ans)%MOD; } cout< mx: mx = a[i] pos = [[] for _ in range(mx + 1)] for i in range(1, n + 1): if a[i] >= 1: pos[a[i]].append(i) # buckets[s] = list of (end, value): a window of `value` consecutive # occurrences of `value` starting at position s and ending at `end`. buckets = [[] for _ in range(n + 2)] for v in range(1, mx + 1): p = pos[v] c = len(p) if c >= v: for i in range(c - v + 1): buckets[p[i]].append((p[i + v - 1], v)) # Iterative persistent segment tree over end-positions [1..n], max value. LF = [0]; RT = [0]; VAL = [0] def build_update(prev, idx, w): # returns new root after setting position idx = max(old, w) stack = [] node = prev lo, hi = 1, n # create path new_root = len(VAL) cur_prev = prev # We'll build recursively via explicit loop using a helper list. path = [] l, h = 1, n p = prev while l != h: cur = len(VAL) LF.append(LF[p]); RT.append(RT[p]); VAL.append(VAL[p]) m = (l + h) >> 1 if idx <= m: path.append((cur, 'L')); p = LF[p]; h = m else: path.append((cur, 'R')); p = RT[p]; l = m + 1 leaf = len(VAL) LF.append(0); RT.append(0); VAL.append(max(VAL[p], w)) child = leaf for cur, side in reversed(path): if side == 'L': LF[cur] = child else: RT[cur] = child lv = VAL[LF[cur]] if LF[cur] else 0 rv = VAL[RT[cur]] if RT[cur] else 0 VAL[cur] = lv if lv > rv else rv child = cur return path[0][0] if path else leaf def query(node, qr): # max value over end-positions [1..qr] res = 0 lo, hi = 1, n # iterative descent collecting full covered subtrees stack = [(node, 1, n)] while stack: nd, l, h = stack.pop() if not nd or qr <= 0: continue if h <= qr: if VAL[nd] > res: res = VAL[nd] continue m = (l + h) >> 1 stack.append((LF[nd], l, m)) if qr > m: stack.append((RT[nd], m + 1, h)) return res roots = [0] * (n + 2) for s in range(n, 0, -1): cur = roots[s + 1] for e, w in buckets[s]: cur = build_update(cur, e, w) roots[s] = cur pref = 0 total = 0 for _ in range(q): l0 = int(next(it)); r0 = int(next(it)) l = ((l0 + pref - 1) % n) + 1 r = ((r0 + pref - 1) % n) + 1 if l > r: l, r = r, l ans = query(roots[l], r) total = (total + ans) % MOD pref = (pref + ans) % MOD sys.stdout.write(str(total % MOD) + "\n") if __name__ == "__main__": solve() 27:Tec0,import java.io.*; import java.util.*; public class Main { static final long MOD = 1000000007L; static int n; static int[] lf, rt, val; static int ptr; static int update(int prev, int lo, int hi, int idx, int w) { int cur = ++ptr; lf[cur] = lf[prev]; rt[cur] = rt[prev]; val[cur] = val[prev]; if (lo == hi) { if (w > val[cur]) val[cur] = w; return cur; } int m = (lo + hi) >>> 1; if (idx <= m) lf[cur] = update(lf[prev], lo, m, idx, w); else rt[cur] = update(rt[prev], m + 1, hi, idx, w); int lv = lf[cur] == 0 ? 0 : val[lf[cur]]; int rv = rt[cur] == 0 ? 0 : val[rt[cur]]; val[cur] = Math.max(lv, rv); return cur; } static int query(int node, int lo, int hi, int qr) { if (node == 0 || qr <= 0) return 0; if (hi <= qr) return val[node]; int m = (lo + hi) >>> 1; int res = query(lf[node], lo, m, qr); if (qr > m) res = Math.max(res, query(rt[node], m + 1, hi, qr)); return res; } public static void main(String[] args) throws Exception { DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16)); n = nextInt(in); int q = nextInt(in); int[] a = new int[n + 1]; int mx = 0; for (int i = 1; i <= n; i++) { a[i] = nextInt(in); if (a[i] > mx) mx = a[i]; } ArrayList[] pos = new ArrayList[mx + 1]; for (int i = 0; i <= mx; i++) pos[i] = new ArrayList<>(); for (int i = 1; i <= n; i++) if (a[i] >= 1) pos[a[i]].add(i); ArrayList[] buckets = new ArrayList[n + 2]; for (int i = 0; i <= n + 1; i++) buckets[i] = new ArrayList<>(); long nodes = 1; for (int v = 1; v <= mx; v++) { ArrayList p = pos[v]; int c = p.size(); if (c >= v) for (int i = 0; i + v - 1 < c; i++) { buckets[p.get(i)].add(new int[]{p.get(i + v - 1), v}); nodes += 1 + ceilLog(n); } } int cap = (int) Math.min(Integer.MAX_VALUE - 8, nodes + 8); lf = new int[cap]; rt = new int[cap]; val = new int[cap]; ptr = 0; int[] root = new int[n + 2]; for (int s = n; s >= 1; s--) { int cur = root[s + 1]; for (int[] pe : buckets[s]) cur = update(cur, 1, n, pe[0], pe[1]); root[s] = cur; } long pref = 0, total = 0; for (int i = 0; i < q; i++) { long l0 = nextLong(in), r0 = nextLong(in); long lv = ((l0 + pref - 1) % n + n) % n + 1; long rv = ((r0 + pref - 1) % n + n) % n + 1; int l = (int) lv, r = (int) rv; if (l > r) { int t = l; l = r; r = t; } int ans = query(root[l], 1, n, r); total = (total + ans) % MOD; pref = (pref + ans) % MOD; } System.out.println(total % MOD); } static int ceilLog(int x) { int r = 1; while ((1 << r) < x) r++; return r + 1; } private static int nextInt(DataInputStream in) throws IOException { int ret = 0, b; boolean neg = false; do { b = in.read(); } while (b != '-' && (b < '0' || b > '9')); if (b == '-') { neg = true; b = in.read(); } while (b >= '0' && b <= '9') { ret = ret * 10 + (b - '0'); b = in.read(); } return neg ? -ret : ret; } private static long nextLong(DataInputStream in) throws IOException { long ret = 0; int b; boolean neg = false; do { b = in.read(); } while (b != '-' && (b < '0' || b > '9')); if (b == '-') { neg = true; b = in.read(); } while (b >= '0' && b <= '9') { ret = ret * 10 + (b - '0'); b = in.read(); } return neg ? -ret : ret; } } 28:T73a,import java.io.*; import java.util.*; public class Main { static final long MOD = 1000000007L; static long get_ans(int n, int q, int[] a, int[][] queries) { return 0L; } public static void main(String[] args) throws Exception { FastScanner fs = new FastScanner(System.in); Integer nObj = fs.nextIntNullable(); if (nObj == null) return; int n = nObj; int q = fs.nextInt(); int[] a = new int[n]; for (int i = 0; i < n; i++) a[i] = fs.nextInt(); int[][] queries = new int[q][2]; for (int i = 0; i < q; i++) { queries[i][0] = fs.nextInt(); queries[i][1] = fs.nextInt(); } long ans = get_ans(n, q, a, queries); ans %= MOD; if (ans < 0) ans += MOD; System.out.println(ans); } static class FastScanner { private final InputStream in; private final byte[] buffer = new byte[1 << 16]; private int ptr = 0, len = 0; FastScanner(InputStream in) { this.in = in; } private int read() throws IOException { if (ptr >= len) { len = in.read(buffer); ptr = 0; if (len <= 0) return -1; } return buffer[ptr++]; } Integer nextIntNullable() throws IOException { int c; do { c = read(); if (c == -1) return null; } while (c <= ' '); int sign = 1; if (c == '-') { sign = -1; c = read(); } int val = 0; while (c > ' ') { val = val * 10 + (c - '0'); c = read(); } return val * sign; } int nextInt() throws IOException { return nextIntNullable(); } } } 29:T85b,# Online Occurrences ## Problem Description You are given an array `a` of length `n` (1-indexed). For a subarray from index `l` to index `r` (inclusive), define `beauty(l, r)` as the maximum integer `x` such that the value `x` appears at least `x` times in the subarray `a[l..r]`. If no positive integer satisfies this, `beauty(l, r) = 0`. You are given `q` queries. Each query provides two integers `l` and `r`. The queries are **encoded (online)**: let `S` be the sum of the answers to all previous queries (for the first query, `S = 0`). Before answering query `i`, decode `l` and `r` as follows: ``` l = ((l + S - 1) mod n) + 1 r = ((r + S - 1) mod n) + 1 if l > r, then swap l and r ``` The answer to query `i` is `beauty(l, r)` on the decoded indices. Note that `S` is the running sum of decoded answers and is used (not reduced modulo anything) when decoding subsequent queries. Output a single integer: the sum of the answers to all `q` queries, taken modulo `10^9 + 7`. ## Input Format - The first line contains two integers `n` and `q`. - The second line contains `n` integers `a[1], a[2], …, a[n]`. - Each of the next `q` lines contains two integers `l` and `r` (the encoded query values). ## Output Format Print a single integer — the sum of all query answers modulo `10^9 + 7`. ## Examples ### Example 1 **Input** ``` 3 2 2 2 2 1 1 1 3 ``` **Output** ``` 2 ``` **Explanation** - `n = 3`, array = `[2, 2, 2]`. - Query 1: `S = 0`. `l = ((1 + 0 - 1) mod 3) + 1 = 1`, `r = ((1 + 0 - 1) mod 3) + 1 = 1`. Subarray `a[1..1] = [2]`; value `2` appears 1 time (< 2), so beauty = 0. - Query 2: `S = 0`. `l = ((1 - 1) mod 3) + 1 = 1`, `r = ((3 - 1) mod 3) + 1 = 3`. Subarray `a[1..3] = [2, 2, 2]`; value `2` appears 3 times (≥ 2), so beauty = 2. - Sum = 0 + 2 = 2. ## Constraints - `1 ≤ n ≤ 2 × 10^5` - `1 ≤ q ≤ 2 × 10^5` - `0 ≤ a[i] ≤ 10^9` - `0 ≤ l, r ≤ 10^9` (encoded values; they are decoded as described above) ## Notes - The answer is required modulo `10^9 + 7`. - The online nature means that the queries are not known in advance; the decoding depends on the answers to previous queries.2a:T959a,# Online Occurrences ## Solution 1: Subarray Frequency Counting ### Intuition - For one query, the most direct idea is to look at the whole chosen subarray and count how many times each number appears. - Once those counts are known, we only need to keep the largest number whose count is at least that number. - This works because the beauty is defined exactly by that condition. - The drawback is that we repeat a full scan for every query, so it becomes slow when there are many queries. ### Approach - Decode each query using the running sum of previous answers. - Scan the chosen subarray and count the frequency of every value. - Check all counted values and keep the largest one whose frequency is large enough. - Add that beauty to both the running answer and the online shift for future queries. ### Pseudocode ```pseudocode getBeauty(a, l, r) { /* Store how many times each value appears in the current subarray */ freq = empty map /* Scan the subarray and build the frequency map */ for i = l to r { /* Increase the count of the current value */ freq[a[i]] = freq[a[i]] + 1 } /* Start with zero because beauty can be zero */ beauty = 0 /* Check every distinct value seen in the subarray */ for each entry in freq { /* Read the value itself and its frequency */ value = entry.first count = entry.second /* Only a positive value with enough copies can become beauty */ if value > 0 and count >= value { /* Keep the maximum valid value */ beauty = max(beauty, value) } } /* Return the beauty found for this range */ return beauty } getAns(n, a, queries) { /* Use the required modulo for the final answer */ MOD = 1000000007 /* Keep the sum of answers modulo MOD */ total = 0 /* Keep the online shift modulo n because queries only need modulo n */ shift = 0 /* Process queries in the given order */ for each query in queries { /* Decode the left border using the current shift */ l = (query[0] + shift) mod n + 1 /* Decode the right border using the current shift */ r = (query[1] + shift) mod n + 1 /* Put the borders in the correct order */ if l > r { /* Swap so the range becomes valid */ temp = l l = r r = temp } /* Compute beauty on zero-based array indices */ beauty = getBeauty(a, l - 1, r - 1) /* Add this query answer to the final sum */ total = (total + beauty) mod MOD /* Update the online shift for future queries */ shift = (shift + beauty) mod n } /* Return the required sum of answers */ return total } ``` ### Code Implementation #### C++ ```cpp #include using namespace std; class solution { public: int getBeauty(vector& a, int l, int r) { unordered_map freq; for (int i = l; i <= r; i++) { freq[a[i]]++; } int beauty = 0; for (auto& entry : freq) { int value = entry.first; int count = entry.second; if (value > 0 && count >= value) { beauty = max(beauty, value); } } return beauty; } long long getAns(int n, vector& a, vector>& queries) { const long long MOD = 1000000007LL; long long total = 0; long long shift = 0; for (auto& query : queries) { int l = (query[0] + shift) % n + 1; int r = (query[1] + shift) % n + 1; if (l > r) { swap(l, r); } int beauty = getBeauty(a, l - 1, r - 1); total = (total + beauty) % MOD; shift = (shift + beauty) % n; } return total; } }; ``` #### Python ```python class solution: def getBeauty(self, a, l, r): freq = {} for i in range(l, r + 1): freq[a[i]] = freq.get(a[i], 0) + 1 beauty = 0 for value, count in freq.items(): if value > 0 and count >= value: beauty = max(beauty, value) return beauty def getAns(self, n, a, queries): MOD = 1000000007 total = 0 shift = 0 for query in queries: l = (query[0] + shift) % n + 1 r = (query[1] + shift) % n + 1 if l > r: l, r = r, l beauty = self.getBeauty(a, l - 1, r - 1) total = (total + beauty) % MOD shift = (shift + beauty) % n return total ``` #### Java ```java import java.util.*; class Solution { public int getBeauty(int[] a, int l, int r) { HashMap freq = new HashMap<>(); for (int i = l; i <= r; i++) { freq.put(a[i], freq.getOrDefault(a[i], 0) + 1); } int beauty = 0; for (Map.Entry entry : freq.entrySet()) { int value = entry.getKey(); int count = entry.getValue(); if (value > 0 && count >= value) { beauty = Math.max(beauty, value); } } return beauty; } public long getAns(int n, int[] a, int[][] queries) { long MOD = 1000000007L; long total = 0; long shift = 0; for (int[] query : queries) { int l = (int)((query[0] + shift) % n) + 1; int r = (int)((query[1] + shift) % n) + 1; if (l > r) { int temp = l; l = r; r = temp; } int beauty = getBeauty(a, l - 1, r - 1); total = (total + beauty) % MOD; shift = (shift + beauty) % n; } return total; } } ``` #### JavaScript ```javascript class Solution { static getBeauty(a, l, r) { const freq = new Map(); for (let i = l; i <= r; i++) { freq.set(a[i], (freq.get(a[i]) || 0) + 1); } let beauty = 0; for (const [value, count] of freq.entries()) { if (value > 0 && count >= value) { beauty = Math.max(beauty, value); } } return beauty; } static getAns(n, a, queries) { const MOD = 1000000007; let total = 0; let shift = 0; for (const query of queries) { let l = (query[0] + shift) % n + 1; let r = (query[1] + shift) % n + 1; if (l > r) { [l, r] = [r, l]; } const beauty = Solution.getBeauty(a, l - 1, r - 1); total = (total + beauty) % MOD; shift = (shift + beauty) % n; } return total; } } ``` ### Complexity Analysis **Time Complexity:** `O(q * n)` in the worst case * For each query, decoding the online range costs `O(1)`. * Scanning the chosen subarray and checking its counted values can take `O(n)` in the worst case. * The dominant term is `O(q * n)` because this full subarray work may happen for every query. **Space Complexity:** `O(n)` * The frequency map for one query can store up to all distinct values from the chosen subarray. * Aside from that, only a few extra variables are used, costing `O(1)`. * Total space used is `O(n)`. ## Solution 2: Candidate Value Filtering with Position Lists ### Intuition - A number can only be the beauty if it appears at least that many times in the whole array, not just inside one query. - That means many values can be ignored forever. In fact, the useful values are very few, because their values add up to at most the array length. - For each useful value, we store all its positions. Then for any query, we can count how many times it appears in the range with binary search. - This avoids scanning the whole subarray every time, but we still test all useful values for every query. ### Approach - Count how many times every value from 1 to the array length appears, and store all of their positions. - Keep only those values whose total frequency is at least their value. - For each decoded query, test these candidate values from largest to smallest using binary search on their position lists. - The first candidate whose count inside the range is large enough is the beauty for that query. ### Pseudocode ```pseudocode countInRange(posList, l, r) { /* Find the first occurrence not smaller than the left border */ leftIndex = lowerBound(posList, l) /* Find the first occurrence greater than the right border */ rightIndex = upperBound(posList, r) /* The difference gives the number of positions inside the range */ return rightIndex - leftIndex } getAns(n, a, queries) { /* Use the required modulo for the final answer */ MOD = 1000000007 /* Store positions only for values that could ever be beauty */ positions = array of n + 1 empty lists /* Count total occurrences for values from 1 to n */ freq = array of n + 1 filled with 0 /* Build frequency counts and position lists */ for i = 0 to n - 1 { /* Ignore values larger than n because they can never be beauty */ if a[i] >= 1 and a[i] <= n { /* Increase the total frequency of this value */ freq[a[i]] = freq[a[i]] + 1 /* Save its one-based position */ positions[a[i]].push_back(i + 1) } } /* Keep only globally possible beauty values */ candidates = empty list /* A value is useful only if the whole array already contains enough copies */ for value = 1 to n { /* Add every globally valid candidate */ if freq[value] >= value { candidates.push_back(value) } } /* Prepare the online answer tracking */ total = 0 shift = 0 /* Process the queries in order */ for each query in queries { /* Decode the left border */ l = (query[0] + shift) mod n + 1 /* Decode the right border */ r = (query[1] + shift) mod n + 1 /* Make the range valid */ if l > r { /* Swap the two borders */ temp = l l = r r = temp } /* Start with zero because beauty may not exist */ beauty = 0 /* Try larger candidates first so we can stop early */ for i = candidates.size() - 1 down to 0 { /* Read the current candidate value */ value = candidates[i] /* Count how many times this value appears in the query range */ count = countInRange(positions[value], l, r) /* If this candidate works, it is the best one */ if count >= value { /* Save the answer and stop checking smaller values */ beauty = value break } } /* Add the answer to the final sum */ total = (total + beauty) mod MOD /* Update the online shift */ shift = (shift + beauty) mod n } /* Return the required sum of answers */ return total } ``` ### Code Implementation #### C++ ```cpp #include using namespace std; class solution { public: int countInRange(vector& posList, int l, int r) { int leftIndex = lower_bound(posList.begin(), posList.end(), l) - posList.begin(); int rightIndex = upper_bound(posList.begin(), posList.end(), r) - posList.begin(); return rightIndex - leftIndex; } long long getAns(int n, vector& a, vector>& queries) { const long long MOD = 1000000007LL; vector freq(n + 1, 0); vector> positions(n + 1); for (int i = 0; i < n; i++) { if (a[i] >= 1 && a[i] <= n) { freq[a[i]]++; positions[a[i]].push_back(i + 1); } } vector candidates; for (int value = 1; value <= n; value++) { if (freq[value] >= value) { candidates.push_back(value); } } long long total = 0; long long shift = 0; for (auto& query : queries) { int l = (query[0] + shift) % n + 1; int r = (query[1] + shift) % n + 1; if (l > r) { swap(l, r); } int beauty = 0; for (int i = (int)candidates.size() - 1; i >= 0; i--) { int value = candidates[i]; int count = countInRange(positions[value], l, r); if (count >= value) { beauty = value; break; } } total = (total + beauty) % MOD; shift = (shift + beauty) % n; } return total; } }; ``` #### Python ```python from bisect import bisect_left, bisect_right class solution: def countInRange(self, posList, l, r): leftIndex = bisect_left(posList, l) rightIndex = bisect_right(posList, r) return rightIndex - leftIndex def getAns(self, n, a, queries): MOD = 1000000007 freq = [0] * (n + 1) positions = [[] for _ in range(n + 1)] for i, value in enumerate(a): if 1 <= value <= n: freq[value] += 1 positions[value].append(i + 1) candidates = [] for value in range(1, n + 1): if freq[value] >= value: candidates.append(value) total = 0 shift = 0 for query in queries: l = (query[0] + shift) % n + 1 r = (query[1] + shift) % n + 1 if l > r: l, r = r, l beauty = 0 for value in reversed(candidates): count = self.countInRange(positions[value], l, r) if count >= value: beauty = value break total = (total + beauty) % MOD shift = (shift + beauty) % n return total ``` #### Java ```java import java.util.*; class Solution { public int countInRange(ArrayList posList, int l, int r) { int leftIndex = lowerBound(posList, l); int rightIndex = upperBound(posList, r); return rightIndex - leftIndex; } private int lowerBound(ArrayList list, int target) { int left = 0; int right = list.size(); while (left < right) { int mid = left + (right - left) / 2; if (list.get(mid) >= target) { right = mid; } else { left = mid + 1; } } return left; } private int upperBound(ArrayList list, int target) { int left = 0; int right = list.size(); while (left < right) { int mid = left + (right - left) / 2; if (list.get(mid) > target) { right = mid; } else { left = mid + 1; } } return left; } public long getAns(int n, int[] a, int[][] queries) { long MOD = 1000000007L; int[] freq = new int[n + 1]; @SuppressWarnings("unchecked") ArrayList[] positions = new ArrayList[n + 1]; for (int i = 0; i <= n; i++) { positions[i] = new ArrayList<>(); } for (int i = 0; i < n; i++) { if (a[i] >= 1 && a[i] <= n) { freq[a[i]]++; positions[a[i]].add(i + 1); } } ArrayList candidates = new ArrayList<>(); for (int value = 1; value <= n; value++) { if (freq[value] >= value) { candidates.add(value); } } long total = 0; long shift = 0; for (int[] query : queries) { int l = (int)((query[0] + shift) % n) + 1; int r = (int)((query[1] + shift) % n) + 1; if (l > r) { int temp = l; l = r; r = temp; } int beauty = 0; for (int i = candidates.size() - 1; i >= 0; i--) { int value = candidates.get(i); int count = countInRange(positions[value], l, r); if (count >= value) { beauty = value; break; } } total = (total + beauty) % MOD; shift = (shift + beauty) % n; } return total; } } ``` #### JavaScript ```javascript class Solution { static lowerBound(list, target) { let left = 0; let right = list.length; while (left < right) { const mid = (left + right) >> 1; if (list[mid] >= target) { right = mid; } else { left = mid + 1; } } return left; } static upperBound(list, target) { let left = 0; let right = list.length; while (left < right) { const mid = (left + right) >> 1; if (list[mid] > target) { right = mid; } else { left = mid + 1; } } return left; } static countInRange(posList, l, r) { const leftIndex = Solution.lowerBound(posList, l); const rightIndex = Solution.upperBound(posList, r); return rightIndex - leftIndex; } static getAns(n, a, queries) { const MOD = 1000000007; const freq = new Array(n + 1).fill(0); const positions = Array.from({ length: n + 1 }, () => []); for (let i = 0; i < n; i++) { if (a[i] >= 1 && a[i] <= n) { freq[a[i]]++; positions[a[i]].push(i + 1); } } const candidates = []; for (let value = 1; value <= n; value++) { if (freq[value] >= value) { candidates.push(value); } } let total = 0; let shift = 0; for (const query of queries) { let l = (query[0] + shift) % n + 1; let r = (query[1] + shift) % n + 1; if (l > r) { [l, r] = [r, l]; } let beauty = 0; for (let i = candidates.length - 1; i >= 0; i--) { const value = candidates[i]; const count = Solution.countInRange(positions[value], l, r); if (count >= value) { beauty = value; break; } } total = (total + beauty) % MOD; shift = (shift + beauty) % n; } return total; } } ``` ### Complexity Analysis **Time Complexity:** `O(n + q * c * log n)`, where `c` is the number of candidate values * Building frequencies and position lists takes `O(n)`. * Each query checks all candidate values, and each check uses two binary searches, so one query costs `O(c * log n)`. * The dominant term is `O(n + q * c * log n)`, and since `c = O(sqrt(n))`, the worst-case bound becomes `O(n + q * sqrt(n) * log n)`. **Space Complexity:** `O(n)` * The position lists store each useful array index once, so they use `O(n)` total memory. * Aside from that, only small helper lists and scalar variables are used, costing `O(c)` and `O(1)`. * Total space used is `O(n)`. ## Solution 3: Persistent Segment Tree over Occurrence Windows ### Intuition - For a value to be valid inside a range, that range must contain some block of that many occurrences of the same value. - If a value appears at positions 3, 8, 10, 14 and the value is 3, then every group of 3 consecutive occurrences gives one interval that must fit completely inside the query. - So the problem becomes: among all prebuilt intervals, find the largest value whose interval starts late enough and ends early enough for the query. - This turns the online query into a fast range maximum query, which is exactly what a persistent segment tree can support. ### Approach - For each value that can ever be a beauty, build all intervals formed by consecutive required occurrences. - Group these intervals by their starting position. - Build persistent segment tree versions from right to left, so each version contains all intervals whose start is at least that position. - For each decoded query, use the version of its left border and ask for the maximum stored value among interval ends up to the right border. ### Pseudocode ```pseudocode update(prevNode, left, right, pos, value) { /* Create a new node by copying the previous version */ curNode = clone(prevNode) /* This segment now knows about one more candidate value */ treeMax[curNode] = max(treeMax[curNode], value) /* Stop when the segment became a single position */ if left == right { /* Return the new persistent node */ return curNode } /* Split the segment into two halves */ mid = (left + right) / 2 /* Update only the half that contains the target end position */ if pos <= mid { /* Rebuild the left child while keeping the right child shared */ leftChild[curNode] = update(leftChild[prevNode], left, mid, pos, value) } else { /* Rebuild the right child while keeping the left child shared */ rightChild[curNode] = update(rightChild[prevNode], mid + 1, right, pos, value) } /* Return the root of the new version */ return curNode } queryRange(node, left, right, ql, qr) { /* An empty node or disjoint segment contributes nothing */ if node == 0 or qr < left or right < ql { /* Return zero because no valid beauty exists here */ return 0 } /* A fully covered segment already stores the needed maximum */ if ql <= left and right <= qr { /* Return the stored answer for this whole segment */ return treeMax[node] } /* Split the current segment to continue the search */ mid = (left + right) / 2 /* Search both halves and keep the larger beauty */ bestLeft = queryRange(leftChild[node], left, mid, ql, qr) bestRight = queryRange(rightChild[node], mid + 1, right, ql, qr) /* Return the best answer from both sides */ return max(bestLeft, bestRight) } getAns(n, a, queries) { /* Use the required modulo for the final answer */ MOD = 1000000007 /* Count useful values and record their one-based positions */ freq = array of n + 1 filled with 0 positions = array of n + 1 empty lists /* Only values from 1 to n can ever be beauty */ for i = 0 to n - 1 { /* Ignore values that are too large or non-positive */ if a[i] >= 1 and a[i] <= n { /* Count the value in the whole array */ freq[a[i]] = freq[a[i]] + 1 /* Save its one-based position */ positions[a[i]].push_back(i + 1) } } /* Group all valid occurrence windows by their starting position */ byStart = array of n + 2 empty lists /* Build one interval for every block of required consecutive occurrences */ for value = 1 to n { /* Only globally possible beauty values are useful */ if freq[value] >= value { /* Every window of this many occurrences creates one interval */ for i = 0 to freq[value] - value { /* The interval starts at the first occurrence of the window */ start = positions[value][i] /* The interval ends at the last occurrence of the window */ end = positions[value][i + value - 1] /* Save this interval together with the value it proves */ byStart[start].push_back({end, value}) } } } /* Create the empty persistent segment tree node */ leftChild.push_back(0) rightChild.push_back(0) treeMax.push_back(0) /* Prepare one root for every possible left border */ roots = array of n + 2 filled with 0 roots[n + 1] = 0 /* Build versions from right to left */ for start = n down to 1 { /* Begin from the version of the next position */ root = roots[start + 1] /* Insert every interval whose start is exactly this position */ for each entry in byStart[start] { /* Read the interval end and the proved beauty value */ end = entry.first value = entry.second /* Add this interval into the current version */ root = update(root, 1, n, end, value) } /* Save the version for this left border */ roots[start] = root } /* Prepare the online answer tracking */ total = 0 shift = 0 /* Answer queries one by one */ for each query in queries { /* Decode the left border */ l = (query[0] + shift) mod n + 1 /* Decode the right border */ r = (query[1] + shift) mod n + 1 /* Make the range valid */ if l > r { /* Swap the borders */ temp = l l = r r = temp } /* Query all intervals fully contained inside this range */ beauty = queryRange(roots[l], 1, n, 1, r) /* Add the beauty to the final answer */ total = (total + beauty) mod MOD /* Update the online shift for later queries */ shift = (shift + beauty) mod n } /* Return the required sum of answers */ return total } ``` ### Code Implementation #### C++ ```cpp #include using namespace std; class solution { public: struct Node { int left; int right; int val; }; vector seg; int update(int prev, int l, int r, int pos, int value) { int cur = (int)seg.size(); seg.push_back(seg[prev]); seg[cur].val = max(seg[cur].val, value); if (l == r) { return cur; } int mid = (l + r) / 2; if (pos <= mid) { seg[cur].left = update(seg[prev].left, l, mid, pos, value); } else { seg[cur].right = update(seg[prev].right, mid + 1, r, pos, value); } return cur; } int queryRange(int node, int l, int r, int ql, int qr) { if (node == 0 || qr < l || r < ql) { return 0; } if (ql <= l && r <= qr) { return seg[node].val; } int mid = (l + r) / 2; return max( queryRange(seg[node].left, l, mid, ql, qr), queryRange(seg[node].right, mid + 1, r, ql, qr) ); } long long getAns(int n, vector& a, vector>& queries) { const long long MOD = 1000000007LL; vector freq(n + 1, 0); vector> positions(n + 1); for (int i = 0; i < n; i++) { if (a[i] >= 1 && a[i] <= n) { freq[a[i]]++; positions[a[i]].push_back(i + 1); } } vector>> byStart(n + 2); for (int value = 1; value <= n; value++) { if (freq[value] >= value) { for (int i = 0; i + value - 1 < freq[value]; i++) { int start = positions[value][i]; int end = positions[value][i + value - 1]; byStart[start].push_back({end, value}); } } } seg.clear(); seg.push_back({0, 0, 0}); vector roots(n + 2, 0); roots[n + 1] = 0; for (int start = n; start >= 1; start--) { int root = roots[start + 1]; for (auto& entry : byStart[start]) { int end = entry.first; int value = entry.second; root = update(root, 1, n, end, value); } roots[start] = root; } long long total = 0; long long shift = 0; for (auto& query : queries) { int l = (query[0] + shift) % n + 1; int r = (query[1] + shift) % n + 1; if (l > r) { swap(l, r); } int beauty = queryRange(roots[l], 1, n, 1, r); total = (total + beauty) % MOD; shift = (shift + beauty) % n; } return total; } }; ``` #### Python ```python class solution: def __init__(self): self.leftChild = [0] self.rightChild = [0] self.treeMax = [0] def update(self, prev, l, r, pos, value): cur = len(self.treeMax) self.leftChild.append(self.leftChild[prev]) self.rightChild.append(self.rightChild[prev]) self.treeMax.append(max(self.treeMax[prev], value)) if l == r: return cur mid = (l + r) // 2 if pos <= mid: self.leftChild[cur] = self.update(self.leftChild[prev], l, mid, pos, value) else: self.rightChild[cur] = self.update(self.rightChild[prev], mid + 1, r, pos, value) return cur def queryRange(self, node, l, r, ql, qr): if node == 0 or qr < l or r < ql: return 0 if ql <= l and r <= qr: return self.treeMax[node] mid = (l + r) // 2 return max( self.queryRange(self.leftChild[node], l, mid, ql, qr), self.queryRange(self.rightChild[node], mid + 1, r, ql, qr) ) def getAns(self, n, a, queries): MOD = 1000000007 freq = [0] * (n + 1) positions = [[] for _ in range(n + 1)] for i, value in enumerate(a): if 1 <= value <= n: freq[value] += 1 positions[value].append(i + 1) byStart = [[] for _ in range(n + 2)] for value in range(1, n + 1): if freq[value] >= value: for i in range(freq[value] - value + 1): start = positions[value][i] end = positions[value][i + value - 1] byStart[start].append((end, value)) self.leftChild = [0] self.rightChild = [0] self.treeMax = [0] roots = [0] * (n + 2) for start in range(n, 0, -1): root = roots[start + 1] for end, value in byStart[start]: root = self.update(root, 1, n, end, value) roots[start] = root total = 0 shift = 0 for query in queries: l = (query[0] + shift) % n + 1 r = (query[1] + shift) % n + 1 if l > r: l, r = r, l beauty = self.queryRange(roots[l], 1, n, 1, r) total = (total + beauty) % MOD shift = (shift + beauty) % n return total ``` #### Java ```java import java.util.*; class Solution { private int[] leftChild; private int[] rightChild; private int[] treeMax; private int nodes; private void ensureCapacity() { if (nodes < treeMax.length) { return; } int newSize = treeMax.length * 2; leftChild = Arrays.copyOf(leftChild, newSize); rightChild = Arrays.copyOf(rightChild, newSize); treeMax = Arrays.copyOf(treeMax, newSize); } private int update(int prev, int l, int r, int pos, int value) { ensureCapacity(); int cur = nodes++; leftChild[cur] = leftChild[prev]; rightChild[cur] = rightChild[prev]; treeMax[cur] = Math.max(treeMax[prev], value); if (l == r) { return cur; } int mid = (l + r) / 2; if (pos <= mid) { leftChild[cur] = update(leftChild[prev], l, mid, pos, value); } else { rightChild[cur] = update(rightChild[prev], mid + 1, r, pos, value); } return cur; } private int queryRange(int node, int l, int r, int ql, int qr) { if (node == 0 || qr < l || r < ql) { return 0; } if (ql <= l && r <= qr) { return treeMax[node]; } int mid = (l + r) / 2; return Math.max( queryRange(leftChild[node], l, mid, ql, qr), queryRange(rightChild[node], mid + 1, r, ql, qr) ); } public long getAns(int n, int[] a, int[][] queries) { long MOD = 1000000007L; int[] freq = new int[n + 1]; @SuppressWarnings("unchecked") ArrayList[] positions = new ArrayList[n + 1]; for (int i = 0; i <= n; i++) { positions[i] = new ArrayList<>(); } for (int i = 0; i < n; i++) { if (a[i] >= 1 && a[i] <= n) { freq[a[i]]++; positions[a[i]].add(i + 1); } } @SuppressWarnings("unchecked") ArrayList[] byStart = new ArrayList[n + 2]; for (int i = 0; i <= n + 1; i++) { byStart[i] = new ArrayList<>(); } for (int value = 1; value <= n; value++) { if (freq[value] >= value) { for (int i = 0; i + value - 1 < freq[value]; i++) { int start = positions[value].get(i); int end = positions[value].get(i + value - 1); byStart[start].add(new int[]{end, value}); } } } leftChild = new int[4]; rightChild = new int[4]; treeMax = new int[4]; nodes = 1; int[] roots = new int[n + 2]; roots[n + 1] = 0; for (int start = n; start >= 1; start--) { int root = roots[start + 1]; for (int[] entry : byStart[start]) { int end = entry[0]; int value = entry[1]; root = update(root, 1, n, end, value); } roots[start] = root; } long total = 0; long shift = 0; for (int[] query : queries) { int l = (int)((query[0] + shift) % n) + 1; int r = (int)((query[1] + shift) % n) + 1; if (l > r) { int temp = l; l = r; r = temp; } int beauty = queryRange(roots[l], 1, n, 1, r); total = (total + beauty) % MOD; shift = (shift + beauty) % n; } return total; } } ``` #### JavaScript ```javascript class Solution { static update(prev, l, r, pos, value, leftChild, rightChild, treeMax) { const cur = treeMax.length; leftChild.push(leftChild[prev] || 0); rightChild.push(rightChild[prev] || 0); treeMax.push(Math.max(treeMax[prev] || 0, value)); if (l === r) { return cur; } const mid = (l + r) >> 1; if (pos <= mid) { leftChild[cur] = Solution.update(leftChild[prev] || 0, l, mid, pos, value, leftChild, rightChild, treeMax); } else { rightChild[cur] = Solution.update(rightChild[prev] || 0, mid + 1, r, pos, value, leftChild, rightChild, treeMax); } return cur; } static queryRange(node, l, r, ql, qr, leftChild, rightChild, treeMax) { if (node === 0 || qr < l || r < ql) { return 0; } if (ql <= l && r <= qr) { return treeMax[node]; } const mid = (l + r) >> 1; return Math.max( Solution.queryRange(leftChild[node] || 0, l, mid, ql, qr, leftChild, rightChild, treeMax), Solution.queryRange(rightChild[node] || 0, mid + 1, r, ql, qr, leftChild, rightChild, treeMax) ); } static getAns(n, a, queries) { const MOD = 1000000007; const freq = new Array(n + 1).fill(0); const positions = Array.from({ length: n + 1 }, () => []); for (let i = 0; i < n; i++) { if (a[i] >= 1 && a[i] <= n) { freq[a[i]]++; positions[a[i]].push(i + 1); } } const byStart = Array.from({ length: n + 2 }, () => []); for (let value = 1; value <= n; value++) { if (freq[value] >= value) { for (let i = 0; i + value - 1 < freq[value]; i++) { const start = positions[value][i]; const end = positions[value][i + value - 1]; byStart[start].push([end, value]); } } } const leftChild = [0]; const rightChild = [0]; const treeMax = [0]; const roots = new Array(n + 2).fill(0); for (let start = n; start >= 1; start--) { let root = roots[start + 1]; for (const [end, value] of byStart[start]) { root = Solution.update(root, 1, n, end, value, leftChild, rightChild, treeMax); } roots[start] = root; } let total = 0; let shift = 0; for (const query of queries) { let l = (query[0] + shift) % n + 1; let r = (query[1] + shift) % n + 1; if (l > r) { [l, r] = [r, l]; } const beauty = Solution.queryRange(roots[l], 1, n, 1, r, leftChild, rightChild, treeMax); total = (total + beauty) % MOD; shift = (shift + beauty) % n; } return total; } } ``` ### Complexity Analysis **Time Complexity:** `O((n + q) * log n)` in the worst case * Building frequencies, positions, and all occurrence windows takes `O(n)` because the total number of useful windows is at most `n`. * Building the persistent segment tree inserts each useful window once, costing `O(log n)` per window, and each query also costs `O(log n)`. * The dominant term is `O((n + q) * log n)` because both preprocessing insertions and online queries are logarithmic. **Space Complexity:** `O(n * log n)` * The persistent segment tree stores a new path of nodes for every inserted window, and each insertion creates `O(log n)` nodes. * The position lists, grouped windows, and root array together use `O(n)` extra memory. * Total space used is `O(n * log n)`.1c:[["$","script",null,{"type":"application/ld+json","dangerouslySetInnerHTML":{"__html":"{\"@context\":\"https://schema.org\",\"@type\":\"LearningResource\",\"learningResourceType\":\"Coding Question\",\"name\":\"Online Occurrences\",\"description\":\"Online Occurrences You are given an array a of length n (1-indexed). For a subarray from index l to index r (inclusive), define beauty(l, r) as the maximum integer x such that the value x appears at least x times in the subarray a[l..r] . If no positive integer satisfies this, beauty(l, r) = 0. You are given q queries. Each query provides two integers l and r . The queries are encoded (online) : let S be the sum of the answers to all previous queries (for the first query, S = 0 ). Before answeri\",\"educationalLevel\":\"medium\",\"about\":{\"@type\":\"Organization\",\"name\":\"Cisco_8th june_on campus\"},\"provider\":{\"@type\":\"Organization\",\"name\":\"OAHelper\",\"url\":\"https://oahelper.in\"},\"isPartOf\":{\"@type\":\"WebSite\",\"name\":\"OAHelper\",\"url\":\"https://oahelper.in\"},\"url\":\"https://oahelper.in/problems/NDA5NHww/online-occurrences\"}"}}],["$","script",null,{"type":"application/ld+json","dangerouslySetInnerHTML":{"__html":"{\"@context\":\"https://schema.org\",\"@type\":\"BreadcrumbList\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https://oahelper.in/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Problems\",\"item\":\"https://oahelper.in/problems\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"Online Occurrences\",\"item\":\"https://oahelper.in/problems/NDA5NHww/online-occurrences\"}]}"}}],["$","section",null,{"className":"sr-only","aria-hidden":"true","children":[["$","p",null,{"children":["Company: ","Cisco_8th june_on campus"]}],["$","p",null,{"children":["Difficulty: ","medium"]}],false,["$","div",null,{"children":[["$","h2",null,{"children":"Problem Statement"}],["$","p",null,{"children":"Online Occurrences You are given an array a of length n (1-indexed). For a subarray from index l to index r (inclusive), define beauty(l, r) as the maximum integer x such that the value x appears at least x times in the subarray a[l..r] . If no positive integer satisfies this, beauty(l, r) = 0. You are given q queries. Each query provides two integers l and r . The queries are encoded (online) : let S be the sum of the answers to all previous queries (for the first query, S = 0 ). Before answering query i , decode l and r as follows: l = ((l + S - 1) mod n) + 1 r = ((r + S - 1) mod n) + 1 if l > r , then swap l and r . The answer to query i is beauty(l, r) on the decoded indices. Note that S is the running sum of decoded answers and is used (not reduced modulo anything) when decoding subsequent queries. Output a single integer: the sum of the answers to all q queries, taken modulo 10 9 +7 . Input format The first line contains two integers n and q . The second line contains n intege"}]]}],false,["$","nav",null,{"aria-label":"Related company pages","children":[["$","$Lb",null,{"href":"/company-questions/cisco8th-juneon-campus","children":["More ","Cisco_8th june_on campus"," OA questions"]}],["$","$Lb",null,{"href":"/interview-experiences","children":"Interview experiences"}]]}]]}],["$","$L23",null,{"id":"NDA5NHww","initialQuestion":{"id":"NDA5NHww","title":"Online Occurrences","google_doc_link":null,"problem_statement":"$24","solution_cpp":"$25","solution_python":"$26","solution_java":"$27","pregiven_code_cpp":"#include \nusing namespace std;\n\nstatic const long long MOD = 1000000007LL;\n\nlong long get_ans(int n, int q, const vector& a, const vector>& queries) {\n (void)n;\n (void)q;\n (void)a;\n (void)queries;\n return 0;\n}\n\nint main() {\n ios::sync_with_stdio(false);\n cin.tie(nullptr);\n\n int n, q;\n if (!(cin >> n >> q)) return 0;\n\n vector a(n);\n for (int i = 0; i < n; ++i) cin >> a[i];\n\n vector> queries(q);\n for (int i = 0; i < q; ++i) {\n int l, r;\n cin >> l >> r;\n queries[i] = {l, r};\n }\n\n long long ans = get_ans(n, q, a, queries);\n cout << (ans % MOD + MOD) % MOD << \"\\n\";\n return 0;\n}\n","pregiven_code_python":"import sys\n\ndef get_ans(n, q, a, queries):\n pass\n\ndef main():\n data = sys.stdin.buffer.read().split()\n if not data:\n return\n it = iter(data)\n n = int(next(it))\n q = int(next(it))\n a = [int(next(it)) for _ in range(n)]\n queries = []\n for _ in range(q):\n l = int(next(it))\n r = int(next(it))\n queries.append((l, r))\n MOD = 1000000007\n ans = get_ans(n, q, a, queries)\n print(ans % MOD)\n\nif __name__ == \"__main__\":\n main()\n","pregiven_code_java":"$28","difficulty":"medium","question_type":"coding","premium_required":0,"created_at":"2026-06-08T20:16:56.190888+00:00","updated_at":"2026-08-09T23:32:24.880486+00:00","solution_code":null,"solution":null,"pregiven_code":"#include \nusing namespace std;\n\nstatic const long long MOD = 1000000007LL;\n\nlong long get_ans(int n, int q, const vector& a, const vector>& queries) {\n (void)n;\n (void)q;\n (void)a;\n (void)queries;\n return 0;\n}\n\nint main() {\n ios::sync_with_stdio(false);\n cin.tie(nullptr);\n\n int n, q;\n if (!(cin >> n >> q)) return 0;\n\n vector a(n);\n for (int i = 0; i < n; ++i) cin >> a[i];\n\n vector> queries(q);\n for (int i = 0; i < q; ++i) {\n int l, r;\n cin >> l >> r;\n queries[i] = {l, r};\n }\n\n long long ans = get_ans(n, q, a, queries);\n cout << (ans % MOD + MOD) % MOD << \"\\n\";\n return 0;\n}\n","input_test_case":"[\"1 1\\n1\\n1 1\", \"2 1\\n1 2\\n1 2\"]","output_test_case":"[\"1\", \"1\"]","lc_tags":"[\"Array\", \"Hash Table\", \"Counting\", \"Binary Search\", \"Segment Tree\", \"Data Stream\"]","visual_animation":null,"difficulty_score":70,"md_problem_statement":"$29","unique_company_name":"cisco","sql_solution":null,"bash_solution":null,"js_solution":null,"editorial":"$2a","hidden_test_cases_blob_count":34,"youtube_tutorial":null,"prompt_solution":null,"campus_type":null,"college_name":null,"role":null,"hidden_test_cases_ref":null,"is_mock_oa":false,"publication_status":"published","has_image":true,"company_name":"Cisco_8th june_on campus","is_first_in_company":true,"company_ref":"MTQ2MHww","total_test_cases":15,"hidden_test_cases_count":13},"isQotdToday":false,"qotdReward":5}]] 1e:null 22:[["$","title","0",{"children":"Online Occurrences - Cisco_8th june_on campus OA Question | OAHelper"}],["$","meta","1",{"name":"description","content":"Online Occurrences (Cisco_8th june_on campus OA) - medium: Online Occurrences You are given an array a of length n (1-indexed). For a subarray from index l to index r (inclusive), define beauty(l, r) as the maximum inte…"}],["$","meta","2",{"name":"author","content":"OAHelper Team"}],["$","meta","3",{"name":"keywords","content":"Cisco_8th june_on campus OA question, Cisco_8th june_on campus online assessment, Online Occurrences, medium, online assessment, coding question, OA practice, interview preparation"}],["$","meta","4",{"name":"robots","content":"index, follow"}],["$","meta","5",{"name":"googlebot","content":"index, follow, max-video-preview:-1, max-image-preview:large, max-snippet:-1"}],["$","link","6",{"rel":"canonical","href":"https://oahelper.in/problems/NDA5NHww/online-occurrences"}],["$","meta","7",{"name":"google-site-verification","content":"MCxApq58khiH0y4KRigRUpoTS3ckefkhoCSHRIRLiXo"}],["$","meta","8",{"property":"og:title","content":"Online Occurrences - Cisco_8th june_on campus OA Question | OAHelper"}],["$","meta","9",{"property":"og:description","content":"Online Occurrences (Cisco_8th june_on campus OA) - medium: Online Occurrences You are given an array a of length n (1-indexed). For a subarray from index l to index r (inclusive), define beauty(l, r) as the maximum inte…"}],["$","meta","10",{"property":"og:url","content":"https://oahelper.in/problems/NDA5NHww/online-occurrences"}],["$","meta","11",{"property":"og:site_name","content":"OAHelper"}],["$","meta","12",{"property":"og:image","content":"https://oahelper.in/campus-ceo-favicon.png?v=11"}],["$","meta","13",{"property":"og:image:width","content":"256"}],["$","meta","14",{"property":"og:image:height","content":"256"}],["$","meta","15",{"property":"og:image:alt","content":"Online Occurrences - Cisco_8th june_on campus OA Question"}],["$","meta","16",{"property":"og:type","content":"website"}],["$","meta","17",{"name":"twitter:card","content":"summary_large_image"}],["$","meta","18",{"name":"twitter:title","content":"Online Occurrences - Cisco_8th june_on campus OA Question | OAHelper"}],["$","meta","19",{"name":"twitter:description","content":"Online Occurrences (Cisco_8th june_on campus OA) - medium: Online Occurrences You are given an array a of length n (1-indexed). For a subarray from index l to index r (inclusive), define beauty(l, r) as the maximum inte…"}],["$","meta","20",{"name":"twitter:image","content":"https://oahelper.in/campus-ceo-favicon.png?v=11"}],["$","link","21",{"rel":"shortcut icon","href":"/campus-ceo-favicon.png?v=11"}],["$","link","22",{"rel":"icon","href":"/campus-ceo-favicon-128.png?v=11","sizes":"128x128","type":"image/png"}],["$","link","23",{"rel":"icon","href":"/campus-ceo-favicon.png?v=11","sizes":"256x256","type":"image/png"}],["$","link","24",{"rel":"icon","href":"/campus-ceo-favicon-512.png?v=11","sizes":"512x512","type":"image/png"}],["$","link","25",{"rel":"apple-touch-icon","href":"/campus-ceo-favicon-512.png?v=11","sizes":"180x180","type":"image/png"}],["$","$L2b","26",{}]]