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.
#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;
}
0 Comments