Mo's Algorithm with extra backtracking Problem

#	User	Rating
1	tourist	3690
2	jiangly	3647
3	Benq	3581
4	orzdevinwang	3570
5	Geothermal	3569
5	cnnfls_csy	3569
7	Radewoosh	3509
8	ecnerwala	3486
9	jqdai0815	3474
10	gyh20	3447

#	User	Contrib.
1	maomao90	174
2	awoo	165
3	adamant	161
4	TheScrasse	160
5	nor	158
6	maroonrk	156
7	-is-this-fft-	152
8	orz	146
9	SecondThread	145
9	pajenegod	145

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