# HackerEarth Suffix problem solution

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.

`#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;}`