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