Mo's Algorithm
もーもー
Code
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define rev(i,s,e) for(i64 (i) = (e); (i)-- > (s);)
#define all(x) x.begin(),x.end()
struct Mo {
vector<i64> left, right, order;
vector<bool> v;
const i64 width;
i64 nl, nr, ptr;
vector<i64> a;
vector<i64> cnt;
i64 ans;
Mo(i64 n, vector<i64> a) : v(n), width((i64)sqrt(n)), nl(0), nr(0), ptr(0), a(a), cnt(1010101), ans(0) {}
void add_query(i64 l, i64 r) {
left.push_back(l);
right.push_back(r);
}
void build() {
order.resize(left.size());
for(i64 i = 0;i < left.size();i++) order[i] = i;
sort(begin(order), end(order), [&](i64 a, i64 b) {
if(left[a] / width != left[b] / width) return left[a] < left[b];
else return right[a] < right[b];
});
}
void add(i64 idx) {
if(cnt[a[idx]]++ == 0) ans++;
}
void del(i64 idx) {
if(--cnt[a[idx]] == 0) ans--;
}
inline void distribute(i64 idx) {
v[idx].flip();
if(v[idx]) add(idx);
else del(idx);
}
i64 process() {
if(ptr == order.size()) return -1;
const auto id = order[ptr];
while(nl > left[id]) distribute(--nl);
while(nr < right[id]) distribute(nr++);
while(nl < left[id]) distribute(nl++);
while(nr > right[id]) distribute(--nr);
return order[ptr++];
}
};