In this HackerEarth Suffix problem solution, You have given an array A containing N integers where every integer is represented as a 23-bit binary string. You are also given the following function:

F(x,y) = Length of Longest Common Suffix of x and y

Write a program to resolve Q queries of the following types:
  1. x y : Update A[x] = y
  2. L R x : Print sum of F(A[i],x) for L <= i <= R

HackerEarth Suffix problem solution


HackerEarth Suffix problem solution.

#include <bits/stdc++.h>

const int N = 100100;
const int BITS = 23;

using namespace std;

int filter[30];
int n, tests;
int ar[N];
int tp[N], l[N], r[N], val[N], x[N];
vector<pair<int, int> > V[30];
int T[30][N * 2];

void add(int id, int i, int delta)
{
for (; i < N * 2; i = (i | (i + 1)))
{
T[id][i] += delta;
}
}

int sum(int id, int r)
{
int res = 0;
for (; r >= 0; r = (r&(r + 1)) - 1)
{
res += T[id][r];
}
return res;
}

void add_number(int val, int ps)
{
for (int bits = 1; bits <= BITS; bits++)
{
int v2 = (val&filter[bits]);
V[bits].push_back(make_pair(v2, ps));
}
}

void turn_on(int val, int ps)
{
for (int bits = 1; bits <= BITS; bits++)
{
int v2 = (val&filter[bits]);
int id = lower_bound(V[bits].begin(), V[bits].end(), make_pair(v2, ps)) - V[bits].begin();
add(bits, id, 1);
}
}

void turn_off(int val, int ps)
{
for (int bits = 1; bits <= BITS; bits++)
{
int v2 = (val&filter[bits]);
int id = lower_bound(V[bits].begin(), V[bits].end(), make_pair(v2, ps)) - V[bits].begin();
add(bits, id, -1);
}
}

int solve(int ps, int val)
{
int res = 0;
for (int bits = 1; bits <= BITS; bits++)
{
int v2 = (val&filter[bits]);
int id = upper_bound(V[bits].begin(), V[bits].end(), make_pair(v2, ps)) - V[bits].begin();
res += sum(bits, id - 1);
}
return res;
}

int main(){
ios_base::sync_with_stdio(0);
//cin.tie(0);

for (int i = 1; i <= BITS; i++)
{
filter[i] = (1 << i) - 1;
}

cin >> n >> tests;

for (int i = 1; i <= n; i++)
{
cin >> ar[i];
add_number(ar[i], i);
}

for (int i = 1; i <= tests; i++)
{
cin >> tp[i];
if (tp[i] == 1)
{
cin >> l[i] >> val[i];
add_number(val[i], l[i]);
}
else
{
cin >> l[i] >> r[i] >> x[i];
}
}

for (int i = 1; i <= BITS; i++)
{
sort(V[i].begin(), V[i].end());
}

for (int i = 1; i <= n; i++)
{
turn_on(ar[i], i);
}

for (int i = 1; i <= tests; i++)
{
if (tp[i] == 2)
{
cout << solve(r[i], x[i]) - solve(l[i] - 1, x[i]) << endl;
}
else
{


turn_off(ar[l[i]], l[i]);
ar[l[i]] = val[i];
turn_on(ar[l[i]], l[i]);
}
}

cin.get(); cin.get();
return 0;
}

Second solution

#include <bits/stdc++.h>

const int N = 100100;
const int BITS = 23;

using namespace std;

int filter[30];
int n, tests;
int ar[N];
int tp[N], l[N], r[N], val[N], x[N];
vector<pair<int, int> > V[30];
int T[30][N * 2];

void add(int id, int i, int delta)
{
for (; i < N * 2; i = (i | (i + 1)))
{
T[id][i] += delta;
}
}

int sum(int id, int r)
{
int res = 0;
for (; r >= 0; r = (r&(r + 1)) - 1)
{
res += T[id][r];
}
return res;
}

void add_number(int val, int ps)
{
for (int bits = 1; bits <= BITS; bits++)
{
int v2 = (val&filter[bits]);
V[bits].push_back(make_pair(v2, ps));
}
}

void turn_on(int val, int ps)
{
for (int bits = 1; bits <= BITS; bits++)
{
int v2 = (val&filter[bits]);
int id = lower_bound(V[bits].begin(), V[bits].end(), make_pair(v2, ps)) - V[bits].begin();
add(bits, id, 1);
}
}

void turn_off(int val, int ps)
{
for (int bits = 1; bits <= BITS; bits++)
{
int v2 = (val&filter[bits]);
int id = lower_bound(V[bits].begin(), V[bits].end(), make_pair(v2, ps)) - V[bits].begin();
add(bits, id, -1);
}
}

int solve(int ps, int val)
{
int res = 0;
for (int bits = 1; bits <= BITS; bits++)
{
int v2 = (val&filter[bits]);
int id = upper_bound(V[bits].begin(), V[bits].end(), make_pair(v2, ps)) - V[bits].begin();
res += sum(bits, id - 1);
}
return res;
}

int main(){
ios_base::sync_with_stdio(0);
//cin.tie(0);

for (int i = 1; i <= BITS; i++)
{
filter[i] = (1 << i) - 1;
}

cin >> n >> tests;

for (int i = 1; i <= n; i++)
{
cin >> ar[i];
add_number(ar[i], i);
}

for (int i = 1; i <= tests; i++)
{
cin >> tp[i];
if (tp[i] == 1)
{
cin >> l[i] >> val[i];
add_number(val[i], l[i]);
}
else
{
cin >> l[i] >> r[i] >> x[i];
}
}

for (int i = 1; i <= BITS; i++)
{
sort(V[i].begin(), V[i].end());
}

for (int i = 1; i <= n; i++)
{
turn_on(ar[i], i);
}

for (int i = 1; i <= tests; i++)
{
if (tp[i] == 2)
{
cout << solve(r[i], x[i]) - solve(l[i] - 1, x[i]) << endl;
}
else
{
turn_off(ar[l[i]], l[i]);
ar[l[i]] = val[i];
turn_on(ar[l[i]], l[i]);
}
}

cin.get(); cin.get();
return 0;
}