Mo's Algorithm with extra backtracking Problem

#	User	Rating
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

I was trying to solve this problem on CodeChef, 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, 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.

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();
}

Comments (3)

Write comment?

WeakestTopology

3 years ago, # |

← Rev. 2 →

I think a struct like the one below is really convenient for these types of problems.

template<typename T>
struct CtrlZ {
    stack<pair<T&, T>> snapshots;
    stack<int> cnt;
    int cntlast = 0;
    void save(T& x) {
        snapshots.emplace(x, x);
        ++cntlast;
    }
    void make_checkpoint() {
        cnt.push(cntlast);
        cntlast = 0;
    }
    void rollback() {
        for (int i = 0; i < cntlast; ++i) {
            snapshots.top().first = snapshots.top().second;
            snapshots.pop();
        }
        cntlast = cnt.top();
        cnt.pop();
    }
};

The usage is basically:

If you know that you will want to get back to the current state some time in the future, make a checkpoint.
Do whatever you want (maybe other checkpoints?), but call save on every variable of relevance before you change it (only once after every checkpoint is really necessary).
Call rollback to revert to the previous state (to the way things were when you last made a checkpoint).

→ Reply

Bungmint

3 years ago, # ^ |

Wow, that is pretty nice. I think I did something similar to what the struct does, but my implementation is nowhere near as structured as that. I will try to implement the structure and hope my issue resolves.

Auto comment: topic has been updated by Bungmint (previous revision, new revision, compare).

Bungmint's blog