I was trying to solve this problem on CodeChef, [QCHEF](https://www.codechef.com/problems/QCHEF), using Mo's algorithm and realized it is not so simple to come up with a data structure that can save previous results, so that you can simply obtain the result after deletion. I looked up how to maintain previous results, and found this nice comment, [link](https://codeforces.com/blog/entry/7383?#comment-161520), where it describes this abstract notion on how one could have one function, snapshot(), for saving the current results, and another function, rollback() to go back to the previous state. I tried to implement this, code below, but it failed miserably. Any help would be appreciated. ↵
↵
UPD: Apparently I had a typo in one of the add functions, and fixing that immediately solved the problem lol. ↵
↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#pragma GCC optimize("O3")↵
#pragma GCC target("sse4")↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
using ll = long long;↵
using vi = vector<int>;↵
using pi = pair<int, int>;↵
using vpi = vector<pair<int, int>>;↵
using pl = pair<ll, ll>;↵
using vl = vector<ll>;↵
using vpl = vector<pl>;↵
using ld = long double;↵
↵
#define all(v) (v).begin(), (v).end()↵
#define ar array↵
#define pb push_back↵
#define sz(x) (int)(x).size()↵
#define fi first↵
#define se second↵
#define lb lower_bound↵
↵
template <typename T>↵
using pqg = priority_queue<T, vector<T>, greater<T>>;↵
template <typename A, typename B>↵
ostream &operator<<(ostream &os, const pair<A, B> &p)↵
{↵
return os << '(' << p.first << ", " << p.second << ')';↵
}↵
template <typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type>↵
ostream &operator<<(ostream &os, const T_container &v)↵
{↵
os << '{';↵
string sep;↵
for (const T &x : v)↵
os << sep << x, sep = ", ";↵
return os << '}';↵
}↵
void dbg_out()↵
{↵
cerr << endl;↵
}↵
template <typename Head, typename... Tail>↵
void dbg_out(Head H, Tail... T)↵
{↵
cerr << ' ' << H;↵
dbg_out(T...);↵
}↵
#ifdef LOCAL↵
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)↵
#else↵
#define dbg(...)↵
#endif↵
↵
struct custom_hash↵
{↵
static uint64_t splitmix64(uint64_t x)↵
{↵
x += 0x9e3779b97f4a7c15;↵
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;↵
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;↵
return x ^ (x >> 31);↵
}↵
↵
size_t operator()(uint64_t x) const↵
{↵
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();↵
return splitmix64(x + FIXED_RANDOM);↵
}↵
};↵
↵
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());↵
↵
const int INF = 1e9;↵
const ll LINF = 1e18;↵
const int MOD = 1e9 + 7; //998244353;↵
const int N = 1<<20;↵
int a[N], res=0, previous=0;↵
int mi[N], mx[N];↵
int leftmost[N], n, m, k;↵
vector<pair<int,pi>> mem;↵
↵
↵
↵
void addleft(int idx){↵
mem.pb({0, {a[idx], mi[a[idx]]}});↵
mem.pb({1, {a[idx], mx[a[idx]]}});↵
mi[a[idx]] = idx;↵
if (mx[a[idx]]<0) mx[a[idx]] = idx;↵
res = max(res, mx[a[idx]]-mi[a[idx]]);↵
} ↵
↵
void addright(int idx){↵
mx[a[idx]] = idx;↵
if (mi[a[idx]]>n) mx[a[idx]] = idx;↵
res = max(res, mx[a[idx]]-mi[a[idx]]);↵
}↵
↵
void snapshot(){↵
previous = res;↵
}↵
↵
void rollback(){↵
while(sz(mem)){↵
pair<int,pi> p = mem.back();↵
if (p.fi==0){↵
mi[p.se.fi] = p.se.se;↵
}else{↵
mx[p.se.fi] = p.se.se;↵
}↵
mem.pop_back();↵
}↵
res = previous;↵
}↵
↵
void init(){↵
for (int i=1;i<=m;++i) mi[i] = INF, mx[i] = -INF;↵
res = 0;↵
}↵
↵
const int block=320; //Dont forget to set↵
↵
struct Query {↵
int l, r, idx;↵
inline pair<int, int> toPair() const {↵
return make_pair(l / block, r);↵
}↵
};↵
inline bool operator<(const Query &a, const Query &b) {↵
return a.toPair() < b.toPair();↵
}↵
↵
using vq = vector<Query>;↵
↵
↵
vi mo(vq queries) {↵
vi answers(queries.size());↵
sort(queries.begin(), queries.end());↵
/*↵
Light Queries↵
*/↵
for (Query q: queries){↵
if (q.r-q.l+1<=block){↵
int ans = 0;↵
for (int j=q.l;j<=q.r;++j){↵
leftmost[a[j]] = INF;↵
}↵
for (int j=q.l;j<=q.r;++j){↵
ans = max(ans, j-leftmost[a[j]]);↵
if(leftmost[a[j]]>=n) leftmost[a[j]] = j;↵
}↵
answers[q.idx] = ans;↵
}↵
}↵
/*↵
Heavy Queries↵
*/↵
int l, r;↵
int last_bucket = -1;↵
for (Query q : queries) {↵
if (q.r-q.l+1<=block) continue;↵
int bucket = q.l/block;↵
if (bucket!=last_bucket){↵
init();↵
l = (bucket+1)*block;↵
if (l>=n) l = n;↵
r = q.r;↵
for (int j=l;j<=r;++j){↵
addright(j);↵
}↵
}↵
last_bucket = bucket;↵
while(r<q.r){↵
addright(++r);↵
}↵
snapshot();↵
for (int j=l-1;j>=q.l;--j){↵
addleft(j);↵
}↵
answers[q.idx] = res;↵
rollback();↵
}↵
return answers;↵
}↵
↵
void solve()↵
{↵
cin >> n >> m>>k;↵
for (int i=0;i<n;++i) cin >> a[i];↵
vq q(k);↵
for (int i=0;i<k;++i){↵
int l,r;↵
cin >> l >> r;↵
l--;r--;↵
q[i] = {l,r,i};↵
}↵
vi ans = mo(q);↵
for (int x:ans) cout << x <<"\n";↵
}↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(0);↵
cin.tie(0), cout.tie(0);↵
solve();↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
UPD: Apparently I had a typo in one of the add functions, and fixing that immediately solved the problem lol. ↵
↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#pragma GCC optimize("O3")↵
#pragma GCC target("sse4")↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
using ll = long long;↵
using vi = vector<int>;↵
using pi = pair<int, int>;↵
using vpi = vector<pair<int, int>>;↵
using pl = pair<ll, ll>;↵
using vl = vector<ll>;↵
using vpl = vector<pl>;↵
using ld = long double;↵
↵
#define all(v) (v).begin(), (v).end()↵
#define ar array↵
#define pb push_back↵
#define sz(x) (int)(x).size()↵
#define fi first↵
#define se second↵
#define lb lower_bound↵
↵
template <typename T>↵
using pqg = priority_queue<T, vector<T>, greater<T>>;↵
template <typename A, typename B>↵
ostream &operator<<(ostream &os, const pair<A, B> &p)↵
{↵
return os << '(' << p.first << ", " << p.second << ')';↵
}↵
template <typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type>↵
ostream &operator<<(ostream &os, const T_container &v)↵
{↵
os << '{';↵
string sep;↵
for (const T &x : v)↵
os << sep << x, sep = ", ";↵
return os << '}';↵
}↵
void dbg_out()↵
{↵
cerr << endl;↵
}↵
template <typename Head, typename... Tail>↵
void dbg_out(Head H, Tail... T)↵
{↵
cerr << ' ' << H;↵
dbg_out(T...);↵
}↵
#ifdef LOCAL↵
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)↵
#else↵
#define dbg(...)↵
#endif↵
↵
struct custom_hash↵
{↵
static uint64_t splitmix64(uint64_t x)↵
{↵
x += 0x9e3779b97f4a7c15;↵
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;↵
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;↵
return x ^ (x >> 31);↵
}↵
↵
size_t operator()(uint64_t x) const↵
{↵
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();↵
return splitmix64(x + FIXED_RANDOM);↵
}↵
};↵
↵
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());↵
↵
const int INF = 1e9;↵
const ll LINF = 1e18;↵
const int MOD = 1e9 + 7; //998244353;↵
const int N = 1<<20;↵
int a[N], res=0, previous=0;↵
int mi[N], mx[N];↵
int leftmost[N], n, m, k;↵
vector<pair<int,pi>> mem;↵
↵
↵
↵
void addleft(int idx){↵
mem.pb({0, {a[idx], mi[a[idx]]}});↵
mem.pb({1, {a[idx], mx[a[idx]]}});↵
mi[a[idx]] = idx;↵
if (mx[a[idx]]<0) mx[a[idx]] = idx;↵
res = max(res, mx[a[idx]]-mi[a[idx]]);↵
} ↵
↵
void addright(int idx){↵
mx[a[idx]] = idx;↵
if (mi[a[idx]]>n) mx[a[idx]] = idx;↵
res = max(res, mx[a[idx]]-mi[a[idx]]);↵
}↵
↵
void snapshot(){↵
previous = res;↵
}↵
↵
void rollback(){↵
while(sz(mem)){↵
pair<int,pi> p = mem.back();↵
if (p.fi==0){↵
mi[p.se.fi] = p.se.se;↵
}else{↵
mx[p.se.fi] = p.se.se;↵
}↵
mem.pop_back();↵
}↵
res = previous;↵
}↵
↵
void init(){↵
for (int i=1;i<=m;++i) mi[i] = INF, mx[i] = -INF;↵
res = 0;↵
}↵
↵
const int block=320; //Dont forget to set↵
↵
struct Query {↵
int l, r, idx;↵
inline pair<int, int> toPair() const {↵
return make_pair(l / block, r);↵
}↵
};↵
inline bool operator<(const Query &a, const Query &b) {↵
return a.toPair() < b.toPair();↵
}↵
↵
using vq = vector<Query>;↵
↵
↵
vi mo(vq queries) {↵
vi answers(queries.size());↵
sort(queries.begin(), queries.end());↵
/*↵
Light Queries↵
*/↵
for (Query q: queries){↵
if (q.r-q.l+1<=block){↵
int ans = 0;↵
for (int j=q.l;j<=q.r;++j){↵
leftmost[a[j]] = INF;↵
}↵
for (int j=q.l;j<=q.r;++j){↵
ans = max(ans, j-leftmost[a[j]]);↵
if(leftmost[a[j]]>=n) leftmost[a[j]] = j;↵
}↵
answers[q.idx] = ans;↵
}↵
}↵
/*↵
Heavy Queries↵
*/↵
int l, r;↵
int last_bucket = -1;↵
for (Query q : queries) {↵
if (q.r-q.l+1<=block) continue;↵
int bucket = q.l/block;↵
if (bucket!=last_bucket){↵
init();↵
l = (bucket+1)*block;↵
if (l>=n) l = n;↵
r = q.r;↵
for (int j=l;j<=r;++j){↵
addright(j);↵
}↵
}↵
last_bucket = bucket;↵
while(r<q.r){↵
addright(++r);↵
}↵
snapshot();↵
for (int j=l-1;j>=q.l;--j){↵
addleft(j);↵
}↵
answers[q.idx] = res;↵
rollback();↵
}↵
return answers;↵
}↵
↵
void solve()↵
{↵
cin >> n >> m>>k;↵
for (int i=0;i<n;++i) cin >> a[i];↵
vq q(k);↵
for (int i=0;i<k;++i){↵
int l,r;↵
cin >> l >> r;↵
l--;r--;↵
q[i] = {l,r,i};↵
}↵
vi ans = mo(q);↵
for (int x:ans) cout << x <<"\n";↵
}↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(0);↵
cin.tie(0), cout.tie(0);↵
solve();↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
