QUESTION
Today is Kriti’s birthday but I forgot to bring a gift for her. She is very angry with me. I have an idea for a gift. She likes coding very much. Why not give her a problem to solve as her gift?\n\nI know a problem but I am not sure whether its solvable or not.\n\nThe problem initially has N strings numbered 1 to N. The program has to answer Q queries. Each query is of the form l r S. For each query, the program has to print the number of times the string S appears in the range [l,r].Help me by solving the problem!!\n\n\nInput\n\nInput will begin with an integer N denoting the number of strings.\nN lines follows each having a string. \nThe next line contains Q denoting the number of queries.\nEach of the next Q lines contain a query of the form l r S.\n\nOutput\nFor each query of type l r S, print the answer to that query. Each answer must be in a new line.
“TESTCASE_1”: “3\nabc\ndef\nabc\n3\n1 2 abc\n1 3 abc\n1 2 hgj\n###—###SEPERATOR—###—\n1\n2\n0”, “TESTCASE_2”: “5\nefdfgcfe\nfggbfgdg\nfggbfgdg\nceggcb\nfggbfgdg\n3\n1 3 dbacgbgfc\n1 2 ccbbf\n1 3 gcdfeecdb\n###—###SEPERATOR—###—\n0\n0\n0”, “TESTCASE_3”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0
ANSWER
#include<stdio.h>
#include<string.h>
typedef struct node{
int index;
char string[15];
}Node;
void merge(Node arr[], int l, int m, int r)
{
Node arr1[m-l+1], arr2[r-m];
int i, j, k;
for(i = 0; i < m-l+1; i++)
arr1[i] = arr[l+i];
for(j = 0; j < r-m; j++)
arr2[j] = arr[j+m+1];
i = 0;
j = 0;
k = l;
while((i< m-l+1) && (j < r-m))
{
if(strcmp(arr1[i].string, arr2[j].string) < 0)
{
arr[k++] = arr1[i++];
}
else if(strcmp(arr1[i].string, arr2[j].string) == 0)
{
if(arr1[i].index < arr2[j].index)
{
arr[k++] = arr1[i++];
}
else
{
arr[k++] = arr2[j++];
}
}
else
{
arr[k++] = arr2[j++];
}
}
while(i < m-l+1)
{
arr[k++] = arr1[i++];
}
while(j < r - m)
{
arr[k++] = arr2[j++];
}
}
void mergesort(Node arr[], int l, int r)
{
if(l < r){
int m = l + (r - l)/2;
mergesort(arr, l , m);
mergesort(arr, m+1, r);
merge(arr, l, m, r);
}
}
int main()
{
int n, q, i, j, l, r, l1, r1, lf, rf, m;
char s[15];
Node arr[100001];
scanf("%d", &n);
for(i = 0; i < n; i++)
{
scanf("%s", arr[i].string);
arr[i].index = i;
}
mergesort(arr, 0, n-1);
scanf("%d", &q);
for(i = 0; i < q; i++)
{
scanf("%d %d %s", &l, &r, s);
l--;
r--;
l1 = 0;
r1 = n-1;
lf = -1;
rf = -1;
while(l1 <= r1)
{
m = l1 + (r1-l1)/2;
if(strcmp(arr[m].string, s) == 0)
{
if(l <= arr[m].index && arr[m].index <= r)
{
if((m-1 < 0) || (strcmp(arr[m-1].string, s) == 0 && l > arr[m-1].index) || (strcmp(arr[m-1].string, s) != 0))
{
lf = m;
break;
}
else
{
r1 = m-1;
}
}
else if(l > arr[m].index)
l1 = m+1;
else if(r < arr[m].index)
r1 = m-1;
}
else if(strcmp(arr[m].string, s) < 0)
{
l1 = m+1;
}
else if(strcmp(arr[m].string, s) > 0)
{
r1 = m-1;
}
}
if(lf != -1)
{
l1 = 0;
r1 = n-1;
while(l1 <= r1)
{
m = l1 + (r1-l1)/2;
if(strcmp(arr[m].string, s) == 0)
{
if(l <= arr[m].index && arr[m].index <= r)
{
if((m+1 >= n) || (strcmp(arr[m+1].string, s) == 0 && r < arr[m+1].index) || (strcmp(arr[m+1].string, s) != 0))
{
rf = m;
break;
}
else
{
l1 = m+1;
}
}
else if(l > arr[m].index)
l1 = m+1;
else if(r < arr[m].index)
r1 = m-1;
}
else if(strcmp(arr[m].string, s) < 0)
{
l1 = m+1;
}
else if(strcmp(arr[m].string, s) > 0)
{
r1 = m-1;
}
}
printf("%d\n", rf - lf + 1);
}
else
printf("0\n");
}
return 0;
}