⚙️AlgorithmAdvanced

Mo's Algorithm - With Updates

Key Points

•
Mo's algorithm with updates treats array modifications as a third dimension called time and answers range queries on the correct version of the array.
•
We sort queries by blocks in (l, r, t) using block size $B = n^{2/3}$ to balance movements across left, right, and time dimensions.
•
Each query is answered by moving pointers L and R and applying or rolling back updates until we reach the required time step.
•
The add/remove functions must update the maintained answer in O(1) when an element enters or leaves the current range.
•
Coordinate compression is essential when values can be large or arbitrary because we need an array-indexed frequency table.
•
Total time is typically O((n + q) $n^{2/3}$ ) with careful O(1) add/remove/apply/revert operations and good cache-friendly ordering.
•
Use 64-bit integers for answers that count pairs or sums to avoid overflow, and be meticulous with inclusive boundaries.
•
Hilbert/gilbert order or alternating sort parity can further improve constants but do not change the asymptotic bound.

Prerequisites

→Mo's algorithm (static) — Understanding how add/remove operations maintain a range aggregate in O(1) is essential before adding the time dimension.
→Coordinate compression — Efficient frequency tables require mapping large values to a compact index space.
→Big-O notation and asymptotics — To understand why B = n^{2/3} balances movements and yields O((n+q) n^{2/3}) complexity.
→Prefix, frequency, and counting techniques — Many Mo-friendly aggregates rely on simple frequency updates and combinatorial counts.
→Sorting and custom comparators — Queries must be sorted in a specific 3D order to achieve locality and performance.
→Inclusive range handling and indexing — Avoid off-by-one bugs when moving L/R pointers and converting 1-based to 0-based indices.

Detailed Explanation

Tap terms for definitions

01Overview

Mo's algorithm with updates extends the classic offline range query technique to handle point updates mixed with queries. In standard Mo's algorithm, we sort queries by blocks of L and R so that, moving from one query to the next, we modify the current range minimally and maintain the answer in O(1) per add/remove operation. With updates, we introduce a third coordinate—time t—which counts how many updates have occurred before a query in the original sequence. We then sort queries in 3D blocks (l, r, t), and for each query we move L and R as usual, but we also move T forward or backward, applying or rolling back updates so that the working array matches the version required by the query. The heart of the algorithm remains the same: define add/remove/apply/revert operations that change the maintained answer in constant time. To keep these O(1), we typically focus on problems such as counting distinct elements, counting equal pairs, computing XOR, or maintaining sums of simple functions of frequencies. To make frequency tables fast, we often coordinate-compress values so that we can index counts with a flat array. The widely-used block size choice is B = n^{2/3} (where n is the array size or a scale comparable to n and the number of operations), which balances movements along L, R, and the time dimension and yields a total running time around O((n + q) n^{2/3}).

02Intuition & Analogies

Imagine you are a librarian responsible for a long bookshelf (the array). People ask you two kinds of requests: 1) queries like "How many unique book titles are between shelf positions L and R right now?" and 2) updates like "Replace the book at position p with a different title." If you answered every request in order from scratch, you would waste time re-counting. Instead, you plan a route to visit queries in a smart order so that between consecutive queries you only move your hands slightly along the shelf and make small changes. That’s classic Mo’s algorithm. Now, suppose some queries refer to the shelf after certain replacements have already happened. You need time travel. For each query, you must ensure that your current shelf matches the version after T updates. So between queries, you not only slide your hands left/right (changing the covered range), but you also time-travel by applying or undoing updates until your shelf matches the required moment. The trick is to keep simple, constant-time routines: when your left hand moves one step, you either add or remove a single book from your count; when you time-travel forward, you apply one pending replacement (and adjust your counts only if that shelf position is currently between your hands). This way, no matter the order of requests, each small motion—left, right, back in time, forward in time—costs roughly the same and is very cheap. Choosing an appropriate block size B ≈ n^{2/3} for the sorting order balances how often you move hands versus how often you time-travel, so total work stays manageable.

03Formal Definition

We are given an initial array A of length n and a sequence of q operations. Each operation is either a point update U(p, x): set A[p] := x, or a range query Q(l, r): compute a function F over the subarray A[l..r] at the version of A that results after processing all updates that occur before this query in the original sequence. We process queries offline. Define the time coordinate t(Q) as the number of updates preceding query Q in input order. A 3D Mo ordering sorts queries by block indices (

⌊

l/B

⌋

⌊

r/B

⌋

, t), possibly with alternating parity to improve locality, where B =

Θ

(

n^{2/3}

). Maintain four operations: addRight(i), addLeft(i), removeRight(i), removeLeft(i), each updating an aggregate data structure (e.g., frequency table) so that the answer for the current range [L..R] is correct. Also maintain apply(u) and revert(u) to move the array's version forward/backward by one update u = (p, old, now): if p

\in

[L..R], remove the contribution of A[p], change A[p], and re-add the new value. Between any two queries in sorted order, adjust (L, R, T) by unit steps using these routines until they match the next query’s (l, r, t). If add/remove/apply/revert are O(1), the total time is O((n + q)

n^{2/3}

) for typical parameters. Space is O(n +

σ

), where

σ

is the number of distinct values after coordinate compression.

04When to Use

Use Mo’s algorithm with updates when you must answer many offline range queries on an array that is also modified by point assignments, and when your per-element contribution function supports O(1) add/remove/apply/revert. Typical targets include problems like: counting distinct values in a subarray after some updates; counting equal pairs or computing \sum f(freq[value]) for simple f; computing XOR or parity-based aggregates; and other statistics that can be updated by changing frequency counters of individual values. Prefer this approach when online data structures are complicated or have higher constants (e.g., segment trees with heavy lazy logic or complex "rollback" variants), and when all queries and updates are known in advance. If the function F is not easily maintained via add/remove (e.g., order statistics requiring balanced trees or heavy rebalancing), Mo’s may not be ideal. Also, Mo’s is particularly suitable when q is large (e.g., comparable to n) so that the offline reordering and pointer-walking strategy pays off. For purely static queries (no updates), standard Mo with B ≈ \sqrt{n} is simpler and faster. If updates are rare or you need online answers, consider Fenwick/segment trees with point updates and range queries instead.

⚠️Common Mistakes

Forgetting coordinate compression: If values are large (e.g., up to 1e9) and you use them as indices in frequency arrays, your program will blow up memory or time. Always compress initial values and all update values. 2) Mishandling time-travel: When applying/reverting an update, you must adjust the maintained answer only if the updated index lies within [L..R]. Failing to check this leads to incorrect answers. 3) Off-by-one in ranges: Mo usually uses inclusive indices. Be consistent about 0-based vs 1-based and what add/remove does at boundaries. 4) Not storing the old value of an update: To revert an update, you need both old and new values. Record them during input parsing while simulating updates on a temporary array. 5) Wrong sorting key or block size: Use integer block indices \lfloor x/B \rfloor. For many mixed workloads, B ≈ n^{2/3} balances movements; wildly different B can degrade performance. 6) Non-O(1) maintenance: If add/remove/apply/revert do more than constant work (e.g., use maps with many collisions or complex rebalancing), the theoretical bound no longer applies. 7) Integer overflow: Pair counts or sums may exceed 32-bit range; use 64-bit (long long). 8) Forgetting to reset the working array to the initial version before processing: After collecting updates with a temporary simulation, reinitialize the working array to the compressed initial values before the Mo sweep.

Key Formulas

3D Mo Block Size

B = Θ (n^{2/3})

Explanation: Choosing block size proportional to $n^{2/3}$ balances movements along L, R, and time t. This yields near-optimal performance for Mo's algorithm with point updates.

Time Complexity

T (n, q, u) = O ((n + q) n^{2/3})

Explanation: When add/remove/apply/revert are O(1), the total running time for n-sized array and q operations (with u updates, often u $\approx$ q) is roughly proportional to (n + q) times $n^{2/3}$ .

Block Index

block (x) = ⌊ \frac{x}{B} ⌋

Explanation: We discretize coordinates by dividing them into blocks of size B. Sorting by these block indices clusters queries to keep pointer movements small.

Equal Pairs in a Range

pairs = v \sum (2 f _{v}) = v \sum \frac{f _{v} ( f _{v} - 1 )}{2}

Explanation: The number of equal pairs in the current range is the sum over all values v of combinations of their frequency taken two at a time. Maintaining $f_{v}$ lets us update this in O(1) per add/remove.

O(1) Update for Pairs

Δ pairs_{add x} = f_{x}, Δ pairs_{remove x} = - (f_{x} - 1)

Explanation: Adding x increases pairs by the number of existing x’s; removing x decreases pairs by the new count after decrement. This enables constant-time maintenance.

O(1) Update for Distinct Count

Δ distinct_{add x} = [f_{x} = 0], Δ distinct_{remove x} = - [f_{x} = 1]

Explanation: Adding x increases the distinct count if its previous frequency was zero; removing x decreases it if its frequency becomes zero. Here [P] is 1 if P is true, else 0.

XOR Is Its Own Inverse

XOR (S △ {x}) = XOR (S) \oplus x

Explanation: When adding or removing the same element x from a multiset under XOR, the aggregate toggles by x. This makes XOR aggregates ideal for Mo's algorithm.

Complexity Analysis

Let n be the array length and q the total number of operations (queries + updates), with u updates and m queries. Mo’s algorithm with updates processes queries offline after sorting by 3D blocks (l, r, t). Each step that adjusts L, R, or T changes the maintained answer in O(1) using frequency tables or similar structures. The sorting cost is O(m log m), which is usually dominated by traversal cost for large instances. The traversal cost arises from pointer movements. Empirically and in standard analyses, choosing block size B = Θ(

n^{2/3}

) balances the expected number of moves across spatial

\frac{L}{R}

and temporal (T) dimensions, yielding total time T(n, q, u) = O((n + q)

n^{2/3}

). This matches the intuition that we visit O(

\frac{n}{B}

\frac{n}{B}

\frac{u}{B}

) blocks and spend O(B) work per boundary in practice, while alternating parity or Hilbert-like order improves locality constants. Space usage is O(n +

σ),

where σ is the number of distinct values after coordinate compression, because we keep the current array, a frequency array of size

σ,

and the list of updates/queries. For aggregates like equal pairs, distinct count, or XOR, add/remove/apply/revert are O(1), so the above bounds hold. If add/remove are not constant (e.g., requiring balanced trees), complexity degrades accordingly. Also, beware that large constants and cache behavior matter; in practice, 3D Mo is slower than classic Mo and requires careful implementation to realize the theoretical bound.

Code Examples

Mo's Algorithm with Updates: Count Equal Pairs in a Range

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // We support two types of operations from input:
5 //  Q l r   -> query on [l, r] (1-based, inclusive), at the version after all prior updates
6 //  U p x   -> point update: set A[p] = x
7 // Task: For each Q, output the number of equal pairs inside [l, r].
8 // Answer equals sum_v C(freq[v], 2) = sum_v freq[v]*(freq[v]-1)/2.
9 
10 struct Update {
11     int idx;      // index being updated (0-based)
12     int oldVal;   // compressed old value
13     int newVal;   // compressed new value
14 };
15 
16 struct Query {
17     int l, r;     // 0-based inclusive
18     int t;        // number of updates applied before this query in input order
19     int id;       // original index of this query to place answer
20 };
21 
22 int main() {
23     ios::sync_with_stdio(false);
24     cin.tie(nullptr);
25 
26     int n, q; // n = array size, q = number of operations (Q or U)
27     if (!(cin >> n >> q)) return 0;
28     vector<long long> Araw(n);
29     for (int i = 0; i < n; ++i) cin >> Araw[i];
30 
31     // Read operations while collecting values for compression.
32     vector<tuple<char,int,long long>> ops; ops.reserve(q);
33     vector<long long> allVals; allVals.reserve(n + q);
34     for (int i = 0; i < n; ++i) allVals.push_back(Araw[i]);
35 
36     for (int i = 0; i < q; ++i) {
37         char type; cin >> type;
38         if (type == 'Q') {
39             int l, r; cin >> l >> r; // 1-based
40             ops.emplace_back(type, (int)ops.size(), 0); // placeholder second is unused for Q
41             // We'll store l,r later when building queries
42             // Keep a marker by storing type and a dummy value
43             ops.back() = make_tuple(type, (l<<16) | r, 0LL); // pack l and r temporarily
44         } else if (type == 'U') {
45             int p; long long x; cin >> p >> x; // 1-based index, new value x
46             ops.emplace_back(type, p, x);
47             allVals.push_back(x);
48         } else {
49             return 0; // invalid
50         }
51     }
52 
53     // Coordinate compress all values (initial + all update new values).
54     sort(allVals.begin(), allVals.end());
55     allVals.erase(unique(allVals.begin(), allVals.end()), allVals.end());
56     auto enc = [&](long long v) {
57         return (int)(lower_bound(allVals.begin(), allVals.end(), v) - allVals.begin());
58     };
59 
60     // Build updates with (old,new) using a temporary simulation on raw values,
61     // then compress both old and new.
62     vector<long long> curRaw = Araw; // simulate to track old values
63     vector<Update> updates; updates.reserve(q);
64     vector<Query> queries; queries.reserve(q);
65 
66     int tCount = 0; // number of updates seen so far while parsing ops
67     int qCount = 0; // number of queries
68 
69     for (int i = 0; i < (int)ops.size(); ++i) {
70         char type = get<0>(ops[i]);
71         if (type == 'U') {
72             int p1 = get<1>(ops[i]);
73             long long x = get<2>(ops[i]);
74             int p = p1 - 1; // to 0-based
75             long long oldRaw = curRaw[p];
76             long long newRaw = x;
77             // record and apply to simulation
78             updates.push_back({p, enc(oldRaw), enc(newRaw)});
79             curRaw[p] = newRaw;
80             ++tCount;
81         } else {
82             // Unpack l and r from the packed integer
83             int packed = get<1>(ops[i]);
84             int l1 = (packed >> 16);
85             int r1 = (packed & 0xFFFF);
86             int l = l1 - 1, r = r1 - 1; // to 0-based
87             queries.push_back({l, r, tCount, qCount});
88             ++qCount;
89         }
90     }
91 
92     // Build the initial compressed array (after compression mapping)
93     vector<int> A(n);
94     for (int i = 0; i < n; ++i) A[i] = enc(Araw[i]);
95 
96     // Choose block size B ~ n^{2/3}
97     int B = max(1, (int)round(pow(max(1, n), 2.0/3.0)));
98 
99     auto block = [&](int x){ return x / B; };
100 
101     // Sort queries by (l-block, r-block, t), with alternating parity to improve locality
102     sort(queries.begin(), queries.end(), [&](const Query& a, const Query& b){
103         int blA = block(a.l), blB = block(b.l);
104         if (blA != blB) return blA < blB;
105         int brA = block(a.r), brB = block(b.r);
106         if (brA != brB) return (brA < brB) ^ (blA & 1); // alternate by l-block parity
107         return (a.t < b.t) ^ ( (brA & 1) ); // alternate by r-block parity
108     });
109 
110     // Frequency table sized by number of distinct compressed values
111     int SIG = (int)allVals.size();
112     vector<int> freq(SIG, 0);
113 
114     // Current state for Mo traversal
115     int L = 0, R = -1; // current range is empty
116     int T = 0;         // number of applied updates
117     vector<int> curA = A; // working array we mutate while applying/reverting updates
118 
119     long long answer = 0; // number of equal pairs in current [L..R]
120 
121     auto add = [&](int pos){
122         int x = curA[pos];
123         long long f = freq[x];
124         answer += f;   // C(f+1,2) - C(f,2) = f
125         freq[x] = (int)(f + 1);
126     };
127     auto removePos = [&](int pos){
128         int x = curA[pos];
129         long long f = freq[x];
130         // After removal, new frequency will be f-1; decrease pairs by (f-1)
131         freq[x] = (int)(f - 1);
132         answer -= (f - 1);
133     };
134 
135     auto applyUpdate = [&](const Update& u){
136         int p = u.idx;
137         if (L <= p && p <= R) {
138             // Remove old contribution and add new
139             removePos(p);
140             curA[p] = u.newVal;
141             add(p);
142         } else {
143             curA[p] = u.newVal;
144         }
145     };
146     auto revertUpdate = [&](const Update& u){
147         int p = u.idx;
148         if (L <= p && p <= R) {
149             removePos(p);
150             curA[p] = u.oldVal;
151             add(p);
152         } else {
153             curA[p] = u.oldVal;
154         }
155     };
156 
157     vector<long long> ans(qCount, 0);
158 
159     size_t upSz = updates.size();
160 
161     // Process queries
162     for (const auto& qu : queries) {
163         int l = qu.l, r = qu.r, t = qu.t;
164         // Move time T to t
165         while (T < t) { applyUpdate(updates[T]); ++T; }
166         while (T > t) { --T; revertUpdate(updates[T]); }
167         // Move L and R
168         while (R < r) { ++R; add(R); }
169         while (R > r) { removePos(R); --R; }
170         while (L < l) { removePos(L); ++L; }
171         while (L > l) { --L; add(L); }
172         ans[qu.id] = answer;
173     }
174 
175     // Output answers in the order of queries
176     for (int i = 0; i < qCount; ++i) {
177         cout << ans[i] << '\n';
178     }
179     return 0;
180 }
181

Reads an initial array and a mixed sequence of queries and updates. It builds a time-aware query list where each query carries t = number of prior updates. Coordinate compression is used for fast frequency tables. The algorithm maintains a working array curA that reflects the current time T. For each query in 3D Mo order, it moves T forward/backward by applying/reverting updates, then adjusts L and R with O(1) add/remove functions to maintain the number of equal pairs. The final answers are printed in input query order.

Time: O((n + q) n^{2/3}) expected, plus O(q log q) for sortingSpace: O(n + q + σ), where σ is the number of distinct compressed values

Mo's Algorithm with Updates: Count Distinct Values in a Range

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Same input format as the previous example (Q for query, U for update).
5 // This version maintains the number of distinct values in [l, r].
6 
7 struct Update { int idx, oldVal, newVal; };
8 struct Query  { int l, r, t, id; };
9 
10 int main(){
11     ios::sync_with_stdio(false);
12     cin.tie(nullptr);
13 
14     int n, q; if(!(cin >> n >> q)) return 0;
15     vector<long long> Araw(n);
16     for(int i=0;i<n;++i) cin >> Araw[i];
17 
18     vector<tuple<char,int,long long>> ops; ops.reserve(q);
19     vector<long long> allVals; allVals.reserve(n+q);
20     for(int i=0;i<n;++i) allVals.push_back(Araw[i]);
21 
22     for(int i=0;i<q;++i){
23         char type; cin >> type;
24         if(type=='Q'){
25             int l,r; cin >> l >> r;
26             ops.emplace_back(type, (l<<16)|r, 0LL);
27         }else{
28             int p; long long x; cin >> p >> x;
29             ops.emplace_back(type, p, x);
30             allVals.push_back(x);
31         }
32     }
33 
34     sort(allVals.begin(), allVals.end());
35     allVals.erase(unique(allVals.begin(), allVals.end()), allVals.end());
36     auto enc = [&](long long v){ return (int)(lower_bound(allVals.begin(), allVals.end(), v)-allVals.begin()); };
37 
38     vector<long long> curRaw=Araw;
39     vector<Update> updates; updates.reserve(q);
40     vector<Query> queries; queries.reserve(q);
41     int tCount=0, qCount=0;
42     for(int i=0;i<(int)ops.size();++i){
43         char type=get<0>(ops[i]);
44         if(type=='U'){
45             int p1=get<1>(ops[i]); long long x=get<2>(ops[i]);
46             int p=p1-1; long long oldRaw=curRaw[p]; long long newRaw=x;
47             updates.push_back({p, enc(oldRaw), enc(newRaw)});
48             curRaw[p]=newRaw; ++tCount;
49         }else{
50             int packed=get<1>(ops[i]);
51             int l=(packed>>16)-1, r=(packed & 0xFFFF)-1;
52             queries.push_back({l,r,tCount,qCount}); ++qCount;
53         }
54     }
55 
56     vector<int> A(n); for(int i=0;i<n;++i) A[i]=enc(Araw[i]);
57 
58     int B=max(1,(int)round(pow(max(1,n),2.0/3.0)));
59     auto block=[&](int x){return x/B;};
60     sort(queries.begin(), queries.end(), [&](const Query&a,const Query&b){
61         int bla=block(a.l), blb=block(b.l);
62         if(bla!=blb) return bla<blb;
63         int bra=block(a.r), brb=block(b.r);
64         if(bra!=brb) return (bra<brb) ^ (bla&1);
65         return (a.t<b.t) ^ (bra&1);
66     });
67 
68     int SIG=(int)allVals.size();
69     vector<int> freq(SIG,0);
70     vector<int> curA=A;
71     int L=0, R=-1, T=0; long long distinct=0;
72 
73     auto add=[&](int pos){ int x=curA[pos]; if(freq[x]==0) ++distinct; ++freq[x]; };
74     auto removePos=[&](int pos){ int x=curA[pos]; --freq[x]; if(freq[x]==0) --distinct; };
75 
76     auto applyU=[&](const Update&u){ int p=u.idx; if(L<=p && p<=R){ removePos(p); curA[p]=u.newVal; add(p);} else curA[p]=u.newVal; };
77     auto revertU=[&](const Update&u){ int p=u.idx; if(L<=p && p<=R){ removePos(p); curA[p]=u.oldVal; add(p);} else curA[p]=u.oldVal; };
78 
79     vector<long long> ans(qCount);
80 
81     for(const auto& qu: queries){
82         while(T<qu.t){ applyU(updates[T]); ++T; }
83         while(T>qu.t){ --T; revertU(updates[T]); }
84         while(R<qu.r){ ++R; add(R);} 
85         while(R>qu.r){ removePos(R); --R;}
86         while(L<qu.l){ removePos(L); ++L;}
87         while(L>qu.l){ --L; add(L);}    
88         ans[qu.id]=distinct;
89     }
90 
91     for(int i=0;i<qCount;++i) cout<<ans[i]<<'\n';
92     return 0;
93 }
94

This variant maintains a distinct counter: add increments the distinct count when introducing a previously unseen value; remove decrements when removing the last occurrence. Updates are applied or reverted only affecting the window if their index lies within [L, R]. The 3D Mo ordering is identical to the first example.

Time: O((n + q) n^{2/3}) expected, plus O(q log q) for sortingSpace: O(n + q + σ)

Classic Mo's Algorithm (No Updates) for Comparison: Equal Pairs

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct Query{ int l, r, id; };
5 
6 int main(){
7     ios::sync_with_stdio(false);
8     cin.tie(nullptr);
9 
10     int n, m; if(!(cin>>n>>m)) return 0;
11     vector<int> A(n); for(int i=0;i<n;++i) cin>>A[i];
12 
13     // Coordinate compress for safety
14     vector<int> comp=A; sort(comp.begin(), comp.end()); comp.erase(unique(comp.begin(), comp.end()), comp.end());
15     for(int i=0;i<n;++i) A[i]=(int)(lower_bound(comp.begin(), comp.end(), A[i]) - comp.begin());
16 
17     vector<Query> qs(m);
18     for(int i=0;i<m;++i){ int l,r; cin>>l>>r; qs[i]={l-1,r-1,i}; }
19 
20     int B=max(1,(int)round(sqrt((double)max(1,n))));
21     auto block=[&](int x){return x/B;};
22     sort(qs.begin(), qs.end(), [&](const Query&a, const Query&b){
23         int bla=block(a.l), blb=block(b.l);
24         if(bla!=blb) return bla<blb;
25         return ( (bla&1) ? a.r>b.r : a.r<b.r );
26     });
27 
28     vector<long long> ans(m);
29     vector<int> freq(comp.size(),0);
30     long long pairs=0; int L=0,R=-1;
31     auto add=[&](int pos){ int x=A[pos]; long long f=freq[x]; pairs += f; ++freq[x]; };
32     auto rem=[&](int pos){ int x=A[pos]; long long f=freq[x]; --freq[x]; pairs -= (f-1); };
33 
34     for(const auto& qu: qs){
35         while(R<qu.r){ ++R; add(R);} while(R>qu.r){ rem(R); --R; }
36         while(L<qu.l){ rem(L); ++L; } while(L>qu.l){ --L; add(L); }
37         ans[qu.id]=pairs;
38     }
39 
40     for(int i=0;i<m;++i) cout<<ans[i]<<'\n';
41     return 0;
42 }
43

Provides a baseline: classic 2D Mo (no updates) for counting equal pairs. It uses B ≈ sqrt(n), sorts by (l-block, r with alternating order), and maintains pairs in O(1) per add/remove. Comparing this to the 3D version helps understand the additional time dimension.

Time: O((n + m) \sqrt{n}) expected, plus O(m log m) for sortingSpace: O(n + σ)

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// We support two types of operations from input:
5	// Q l r -> query on [l, r] (1-based, inclusive), at the version after all prior updates
6	// U p x -> point update: set A[p] = x
7	// Task: For each Q, output the number of equal pairs inside [l, r].
8	// Answer equals sum_v C(freq[v], 2) = sum_v freq[v]*(freq[v]-1)/2.
9
10	struct Update {
11	int idx; // index being updated (0-based)
12	int oldVal; // compressed old value
13	int newVal; // compressed new value
14	};
15
16	struct Query {
17	int l, r; // 0-based inclusive
18	int t; // number of updates applied before this query in input order
19	int id; // original index of this query to place answer
20	};
21
22	int main() {
23	ios::sync_with_stdio(false);
24	cin.tie(nullptr);
25
26	int n, q; // n = array size, q = number of operations (Q or U)
27	if (!(cin >> n >> q)) return 0;
28	vector<long long> Araw(n);
29	for (int i = 0; i < n; ++i) cin >> Araw[i];
30
31	// Read operations while collecting values for compression.
32	vector<tuple<char,int,long long>> ops; ops.reserve(q);
33	vector<long long> allVals; allVals.reserve(n + q);
34	for (int i = 0; i < n; ++i) allVals.push_back(Araw[i]);
35
36	for (int i = 0; i < q; ++i) {
37	char type; cin >> type;
38	if (type == 'Q') {
39	int l, r; cin >> l >> r; // 1-based
40	ops.emplace_back(type, (int)ops.size(), 0); // placeholder second is unused for Q
41	// We'll store l,r later when building queries
42	// Keep a marker by storing type and a dummy value
43	ops.back() = make_tuple(type, (l<<16) \| r, 0LL); // pack l and r temporarily
44	} else if (type == 'U') {
45	int p; long long x; cin >> p >> x; // 1-based index, new value x
46	ops.emplace_back(type, p, x);
47	allVals.push_back(x);
48	} else {
49	return 0; // invalid
50	}
51	}
52
53	// Coordinate compress all values (initial + all update new values).
54	sort(allVals.begin(), allVals.end());
55	allVals.erase(unique(allVals.begin(), allVals.end()), allVals.end());
56	auto enc = [&](long long v) {
57	return (int)(lower_bound(allVals.begin(), allVals.end(), v) - allVals.begin());
58	};
59
60	// Build updates with (old,new) using a temporary simulation on raw values,
61	// then compress both old and new.
62	vector<long long> curRaw = Araw; // simulate to track old values
63	vector<Update> updates; updates.reserve(q);
64	vector<Query> queries; queries.reserve(q);
65
66	int tCount = 0; // number of updates seen so far while parsing ops
67	int qCount = 0; // number of queries
68
69	for (int i = 0; i < (int)ops.size(); ++i) {
70	char type = get<0>(ops[i]);
71	if (type == 'U') {
72	int p1 = get<1>(ops[i]);
73	long long x = get<2>(ops[i]);
74	int p = p1 - 1; // to 0-based
75	long long oldRaw = curRaw[p];
76	long long newRaw = x;
77	// record and apply to simulation
78	updates.push_back({p, enc(oldRaw), enc(newRaw)});
79	curRaw[p] = newRaw;
80	++tCount;
81	} else {
82	// Unpack l and r from the packed integer
83	int packed = get<1>(ops[i]);
84	int l1 = (packed >> 16);
85	int r1 = (packed & 0xFFFF);
86	int l = l1 - 1, r = r1 - 1; // to 0-based
87	queries.push_back({l, r, tCount, qCount});
88	++qCount;
89	}
90	}
91
92	// Build the initial compressed array (after compression mapping)
93	vector<int> A(n);
94	for (int i = 0; i < n; ++i) A[i] = enc(Araw[i]);
95
96	// Choose block size B ~ n^{2/3}
97	int B = max(1, (int)round(pow(max(1, n), 2.0/3.0)));
98
99	auto block = [&](int x){ return x / B; };
100
101	// Sort queries by (l-block, r-block, t), with alternating parity to improve locality
102	sort(queries.begin(), queries.end(), [&](const Query& a, const Query& b){
103	int blA = block(a.l), blB = block(b.l);
104	if (blA != blB) return blA < blB;
105	int brA = block(a.r), brB = block(b.r);
106	if (brA != brB) return (brA < brB) ^ (blA & 1); // alternate by l-block parity
107	return (a.t < b.t) ^ ( (brA & 1) ); // alternate by r-block parity
108	});
109
110	// Frequency table sized by number of distinct compressed values
111	int SIG = (int)allVals.size();
112	vector<int> freq(SIG, 0);
113
114	// Current state for Mo traversal
115	int L = 0, R = -1; // current range is empty
116	int T = 0; // number of applied updates
117	vector<int> curA = A; // working array we mutate while applying/reverting updates
118
119	long long answer = 0; // number of equal pairs in current [L..R]
120
121	auto add = [&](int pos){
122	int x = curA[pos];
123	long long f = freq[x];
124	answer += f; // C(f+1,2) - C(f,2) = f
125	freq[x] = (int)(f + 1);
126	};
127	auto removePos = [&](int pos){
128	int x = curA[pos];
129	long long f = freq[x];
130	// After removal, new frequency will be f-1; decrease pairs by (f-1)
131	freq[x] = (int)(f - 1);
132	answer -= (f - 1);
133	};
134
135	auto applyUpdate = [&](const Update& u){
136	int p = u.idx;
137	if (L <= p && p <= R) {
138	// Remove old contribution and add new
139	removePos(p);
140	curA[p] = u.newVal;
141	add(p);
142	} else {
143	curA[p] = u.newVal;
144	}
145	};
146	auto revertUpdate = [&](const Update& u){
147	int p = u.idx;
148	if (L <= p && p <= R) {
149	removePos(p);
150	curA[p] = u.oldVal;
151	add(p);
152	} else {
153	curA[p] = u.oldVal;
154	}
155	};
156
157	vector<long long> ans(qCount, 0);
158
159	size_t upSz = updates.size();
160
161	// Process queries
162	for (const auto& qu : queries) {
163	int l = qu.l, r = qu.r, t = qu.t;
164	// Move time T to t
165	while (T < t) { applyUpdate(updates[T]); ++T; }
166	while (T > t) { --T; revertUpdate(updates[T]); }
167	// Move L and R
168	while (R < r) { ++R; add(R); }
169	while (R > r) { removePos(R); --R; }
170	while (L < l) { removePos(L); ++L; }
171	while (L > l) { --L; add(L); }
172	ans[qu.id] = answer;
173	}
174
175	// Output answers in the order of queries
176	for (int i = 0; i < qCount; ++i) {
177	cout << ans[i] << '\n';
178	}
179	return 0;
180	}
181

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Same input format as the previous example (Q for query, U for update).
5	// This version maintains the number of distinct values in [l, r].
6
7	struct Update { int idx, oldVal, newVal; };
8	struct Query { int l, r, t, id; };
9
10	int main(){
11	ios::sync_with_stdio(false);
12	cin.tie(nullptr);
13
14	int n, q; if(!(cin >> n >> q)) return 0;
15	vector<long long> Araw(n);
16	for(int i=0;i<n;++i) cin >> Araw[i];
17
18	vector<tuple<char,int,long long>> ops; ops.reserve(q);
19	vector<long long> allVals; allVals.reserve(n+q);
20	for(int i=0;i<n;++i) allVals.push_back(Araw[i]);
21
22	for(int i=0;i<q;++i){
23	char type; cin >> type;
24	if(type=='Q'){
25	int l,r; cin >> l >> r;
26	ops.emplace_back(type, (l<<16)\|r, 0LL);
27	}else{
28	int p; long long x; cin >> p >> x;
29	ops.emplace_back(type, p, x);
30	allVals.push_back(x);
31	}
32	}
33
34	sort(allVals.begin(), allVals.end());
35	allVals.erase(unique(allVals.begin(), allVals.end()), allVals.end());
36	auto enc = [&](long long v){ return (int)(lower_bound(allVals.begin(), allVals.end(), v)-allVals.begin()); };
37
38	vector<long long> curRaw=Araw;
39	vector<Update> updates; updates.reserve(q);
40	vector<Query> queries; queries.reserve(q);
41	int tCount=0, qCount=0;
42	for(int i=0;i<(int)ops.size();++i){
43	char type=get<0>(ops[i]);
44	if(type=='U'){
45	int p1=get<1>(ops[i]); long long x=get<2>(ops[i]);
46	int p=p1-1; long long oldRaw=curRaw[p]; long long newRaw=x;
47	updates.push_back({p, enc(oldRaw), enc(newRaw)});
48	curRaw[p]=newRaw; ++tCount;
49	}else{
50	int packed=get<1>(ops[i]);
51	int l=(packed>>16)-1, r=(packed & 0xFFFF)-1;
52	queries.push_back({l,r,tCount,qCount}); ++qCount;
53	}
54	}
55
56	vector<int> A(n); for(int i=0;i<n;++i) A[i]=enc(Araw[i]);
57
58	int B=max(1,(int)round(pow(max(1,n),2.0/3.0)));
59	auto block=[&](int x){return x/B;};
60	sort(queries.begin(), queries.end(), [&](const Query&a,const Query&b){
61	int bla=block(a.l), blb=block(b.l);
62	if(bla!=blb) return bla<blb;
63	int bra=block(a.r), brb=block(b.r);
64	if(bra!=brb) return (bra<brb) ^ (bla&1);
65	return (a.t<b.t) ^ (bra&1);
66	});
67
68	int SIG=(int)allVals.size();
69	vector<int> freq(SIG,0);
70	vector<int> curA=A;
71	int L=0, R=-1, T=0; long long distinct=0;
72
73	auto add=[&](int pos){ int x=curA[pos]; if(freq[x]==0) ++distinct; ++freq[x]; };
74	auto removePos=[&](int pos){ int x=curA[pos]; --freq[x]; if(freq[x]==0) --distinct; };
75
76	auto applyU=[&](const Update&u){ int p=u.idx; if(L<=p && p<=R){ removePos(p); curA[p]=u.newVal; add(p);} else curA[p]=u.newVal; };
77	auto revertU=[&](const Update&u){ int p=u.idx; if(L<=p && p<=R){ removePos(p); curA[p]=u.oldVal; add(p);} else curA[p]=u.oldVal; };
78
79	vector<long long> ans(qCount);
80
81	for(const auto& qu: queries){
82	while(T<qu.t){ applyU(updates[T]); ++T; }
83	while(T>qu.t){ --T; revertU(updates[T]); }
84	while(R<qu.r){ ++R; add(R);}
85	while(R>qu.r){ removePos(R); --R;}
86	while(L<qu.l){ removePos(L); ++L;}
87	while(L>qu.l){ --L; add(L);}
88	ans[qu.id]=distinct;
89	}
90
91	for(int i=0;i<qCount;++i) cout<<ans[i]<<'\n';
92	return 0;
93	}
94

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	struct Query{ int l, r, id; };
5
6	int main(){
7	ios::sync_with_stdio(false);
8	cin.tie(nullptr);
9
10	int n, m; if(!(cin>>n>>m)) return 0;
11	vector<int> A(n); for(int i=0;i<n;++i) cin>>A[i];
12
13	// Coordinate compress for safety
14	vector<int> comp=A; sort(comp.begin(), comp.end()); comp.erase(unique(comp.begin(), comp.end()), comp.end());
15	for(int i=0;i<n;++i) A[i]=(int)(lower_bound(comp.begin(), comp.end(), A[i]) - comp.begin());
16
17	vector<Query> qs(m);
18	for(int i=0;i<m;++i){ int l,r; cin>>l>>r; qs[i]={l-1,r-1,i}; }
19
20	int B=max(1,(int)round(sqrt((double)max(1,n))));
21	auto block=[&](int x){return x/B;};
22	sort(qs.begin(), qs.end(), [&](const Query&a, const Query&b){
23	int bla=block(a.l), blb=block(b.l);
24	if(bla!=blb) return bla<blb;
25	return ( (bla&1) ? a.r>b.r : a.r<b.r );
26	});
27
28	vector<long long> ans(m);
29	vector<int> freq(comp.size(),0);
30	long long pairs=0; int L=0,R=-1;
31	auto add=[&](int pos){ int x=A[pos]; long long f=freq[x]; pairs += f; ++freq[x]; };
32	auto rem=[&](int pos){ int x=A[pos]; long long f=freq[x]; --freq[x]; pairs -= (f-1); };
33
34	for(const auto& qu: qs){
35	while(R<qu.r){ ++R; add(R);} while(R>qu.r){ rem(R); --R; }
36	while(L<qu.l){ rem(L); ++L; } while(L>qu.l){ --L; add(L); }
37	ans[qu.id]=pairs;
38	}
39
40	for(int i=0;i<m;++i) cout<<ans[i]<<'\n';
41	return 0;
42	}
43