In this HackerEarth Min differene queries problem solution, You have a sequence a of length n and you want to answer q queries determined by 2 integers l and r. You take all numbers present in subsequence (al, al+1,...,ar, let them be b1,b2,...,bt and number of occurrences of each number in this subsequence be c1,c2,...,ct respectively. The answer for per query is equal to min|ci - cj| for 1 <= i < j <= t or 1 if t = 1.


HackerEarth Min difference queries problem solution


HackerEarth Min difference queries problem solution.

#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
int t[1 << 23];
int L[1 << 23];
int R[1 << 23];
int Root[1 << 23];
int SZ = -1;
int get(int &k)
{
    if (k == -1)
        k = ++SZ,L[SZ] = R[SZ] = -1,t[SZ] = 0;
    return k;
}
void build(int l,int r,int node)
{
    if (l == r)
        return ;
    int m = (l + r) / 2;
    build(l,m,get(L[node]));
    build(m+1,r,get(R[node]));
}
void update(int l,int r,int pos,int v,int node,int prev)
{
    if (l == r)
        t[node] = v;
    else
    {
        int m = (l + r) / 2;
        if (pos <= m)
            R[node] = R[prev];
        else
            L[node] = L[prev];
        if (pos <= m)
            update(l,m,pos,v,get(L[node]),L[prev]);
        else
            update(m+1,r,pos,v,get(R[node]),R[prev]);
        t[node] = t[get(L[node])] + t[get(R[node])];
    }
}
int query(int l,int r,int l1,int r1,int node)
{
    if (l1 <= l && r <= r1)
        return t[node];
    int m = (l + r) / 2;
    int ans = 0;
    if (l1 <= m)
        ans += query(l,m,l1,r1,L[node]);
    if (m+1<=r1)
        ans += query(m+1,r,l1,r1,R[node]);
    return ans;
}
vi ss;
void go(int l,int r,int l1,int r1,int node)
{
    if (!t[node])
        return;
    if (l == r)
        return void(ss.pb(l));
    int m = (l + r) / 2;
    if (l1 <= m)
        go(l,m,l1,r1,L[node]);
    if (m+1<=r1)
        go(m+1,r,l1,r1,R[node]);
}
const int N = (int)(1e6) + 5;
vi v[N];
int s[N];
int last[N];
int wh[N];
int n;
int get(int l,int r,int k)
{
    return lower_bound(all(v[k]),r + 1) - lower_bound(all(v[k]),l);
}
int get(int l,int r)
{
    vi w;
    int d = query(1,n,l,r,Root[r]);
    if (d > wh[r - l + 1])
        return 0;
    if (d == 1)
        return -1;
    ss.clear();
    go(1,n,l,r,Root[r]);
    for (auto &it : ss)
        it = s[it];
    for (auto it : ss)
        w.pb(get(l,r,it));
    sort(all(w));
    int ans = 1e9;
    for (int i = 0;i + 1 < d;++i)
        smin(ans,w[i + 1] - w[i]);
    return ans;
}
int main(void)
{
    int q;
    scanf("%d%d",&n,&q);
    vi w;
    wh[1] = 1;
    for (int i = 2;i <= n;++i)
    {
        wh[i] = wh[i - 1];
        if (1ll * wh[i] * (wh[i] + 1) / 2 <= i)
            ++wh[i];
    }
    for (int i = 1;i <= n;++i)
        scanf("%d",&s[i]);
    for (int i = 1;i <= n;++i)
        w.pb(s[i]);
    sort(all(w));
    w.resize(unique(all(w)) - w.begin());
    const int SZ = w.size();
    for (int i = 1;i <= SZ;++i)
        v[i].pb(0);
    for (int i = 1;i <= n;++i)
        v[s[i] = lower_bound(all(w),s[i]) - w.begin() + 1].pb(i);
    for (int i = 1;i <= SZ;++i)
        v[i].pb(n + 1);
    Root[0] = -1;
    build(1,n,get(Root[0]));
    for (int i = 1;i <= n;++i)
    {
        int prev = Root[i - 1];
        Root[i] = -1;
        if (last[s[i]])
            update(1,n,last[s[i]],0,get(Root[i]),prev),prev = Root[i],Root[i] = -1;
        update(1,n,i,1,get(Root[i]),prev);
        last[s[i]] = i;
    }
    int ans = 0;
    while (q --)
    {
        int a,b;
        scanf("%d%d",&a,&b);

        int l = (a + ans) % n + 1;
        int r = (b + ans) % n + 1;
        ans = get(l,r);
        printf("%d\n",ans);
    }
    return 0;
}

Second solution

#include "bits/stdc++.h"
using namespace std;
 
#define MAX 100002
 
int n;
int q;
 
vector<int> v;
 
#define MAGIC 333
#define MM 500
int u[MAGIC][MM];
 
int sz[MAGIC];
 
 
bool ex[MAX];
 
vector<int> vv;
 
vector<int> idx[MAX];
 
set<int> s;
 
 
int main() {
    cin >> n >> q;
    assert(1<=n&&n<=100000);
    assert(1<=q&&q<=100000);
    for (int i = 0; i < n; i++) {
        int a;
        scanf("%d", &a);
        assert(1<=a);
        assert(a<=1000000000);
        v.push_back(a);
        vv.push_back(a);
    }
    sort(vv.begin(), vv.end());
    for (int i = 0; i < v.size(); i++) {
        v[i] = lower_bound(vv.begin(), vv.end(), v[i]) - vv.begin();
        idx[v[i]].push_back(i);
    }
    for (int i = 0; i < n; i+=MAGIC) {
        memset(ex, false, sizeof(ex));
        for (int j = i; j < n; j++) {
            if (ex[v[j]])continue;
            ex[v[j]] = true;
            u[i / MAGIC][sz[i / MAGIC]] = v[j];
            sz[i / MAGIC]++;
            if(sz[i/MAGIC]==MM)break;
        }
    }
    int las = 0;
    while (q--) {
        int a,b;
        scanf("%d%d", &a, &b);
        assert(1<=a&&a<=n&&1<=b&&b<=n);
        int l = (a + las) % n + 1;
        int r = (b + las) % n + 1;
        l--;
        r--;
        assert(0<=l&&0<=r);
        int belong = l / MAGIC;
        s.clear();
        bool en = false;
        for (int i = 0; i < sz[belong]; i++) {  
            int val = u[belong][i];
            int lef = lower_bound(idx[val].begin(), idx[val].end(), l) - idx[val].begin();
            int rig = upper_bound(idx[val].begin(), idx[val].end(), r) - idx[val].begin();
            int oc = rig - lef;
            if (oc == 0)continue;
            if (s.count(oc)) {
                en = true;
                break;
            }
            s.insert(oc);
        }
        if (en) {
            puts("0");
            las = 0;
            continue;
        }
        if (s.size() == 1) {
            puts("-1");
            las = -1;
            continue;
        }
        int ans = INT_MAX;
        int pr = -1;
        for (auto el : s) {
            if (pr != -1) {
                ans = min(ans, el - pr);
            }
            pr = el;
        }
        printf("%d\n", ans);
        las = ans;
    }
    return 0;
}