This is the link to my solution for the problem STRSUB.

The solution in the link is having time complexity of O(N + QlogN). And I am trying to solve in O(N + Q) so that each query can be solved in O(1) time. For that I am replacing the binary search in each query with preprocessed array.

Binary Search

```
Line 147: int pos= binarySearch(far, x, y, y);
private static int binarySearch(int[] far, int s, int e, int L){
int mid;
while(s<=e){
mid= (s+e) >> 1;
if(far[mid] > L){
e= mid-1;
}
else if(far[mid] <= L){
s= mid+1;
}
}
return s-1;
}
```

with pre array

```
int pos= pre[y];
if(pos < x) pos= x-1;
```

This pre array is calculated through following code

```
int[] pre= new int[N];
pre[0]= -1;
for(int i=0; i<N; i++){
pre[far[i]]= i;
}
for(int i=1; i<N; i++){
if(pre[i] == 0){
pre[i]= pre[i-1];
}
}
```

The purpose of binary search was to find the position between ‘x’ and ‘y’ such that `far[x] <= y`

so is the pre storing for each of number between ‘0 to N-1’.

But there is still something missing in `pre`

which I am unable to find out which binary Search is having

and `pre`

not.

Most of the test cases have passed. If some one could figure out some thing would be a great help.