Toph: Horrible Queries

Problem link: Horrible Queries

Solution:

In this problem, we will be given some integers from 1 to 50. And also integer L,R,K. We need to find how many unique values have at least K occurence in the subarray between L & R, where L<= R.
As numbers can only be between 1 to 50, we can implement this simply without the use of segment tree. What we need to do is that, we will create 50 array of size N (each for 1 to 50 integers) to compute the occurence of every integers in a cumulative way. Then for each query, we will simply check for every integers if cumulative sum (occurence of that integer) of that integer in given range is at least K or not. Then we will simply increase the counter to get our answer. Try to implement it any way you like keeping in mind about the cumulative frequency of occurance. Then you can check my code below.

	#include <bits/stdc++.h>
	#include <ext/pb_ds/assoc_container.hpp>
	using namespace std;
	using namespace __gnu_pbds;
	#define ll long long
	#define Max(a,b) ((a>=b)? a : b)
	#define Min(a,b) ((a<=b)? a : b)
	#define pb push_back
	#define MOD 1000000007
	#define MP make_pair
	#define vi vector<int>
	#define vll vector<ll>
	#define MAX 3000010
	//typedef __int128 bigll;
	int store[51][100010];
	void init(int n)
	{
	for(int i=1;i<=50;i++)
	for(int j=1;j<=n;j++)store[i][j]=0;
	}
	int main()
	{
	//ios_base::sync_with_stdio(false);
	//cin.tie(NULL);
	//FILE*f=freopen("input.txt","r",stdin);
	//FILE*o=freopen("output.txt","w",stdout);
	int n,l,r,k,x,q;
	scanf("%d",&n);
	init(n); // pre_process the array
	for(int i=1;i<=n;i++)
	{
	scanf("%d",&x);
	store[x][i]=store[x][i-1]+1; // occurence increase
	for(int j=1;j<=50;j++) // update cumulative occurence for all the integers
	if(j!=x)
	store[j][i]=store[j][i-1];
	}
	scanf("%d",&q);
	while(q--)
	{
	scanf("%d %d %d",&l,&r,&k);
	int c=0;
	for(int i=1;i<=50;i++)
	if(store[i][r]-store[i][l-1]>=k)c++; // check if at least K occurence found
	printf("%d\n",c);
	}
	//fclose(f);
	//fclose(o);
	return 0;
	}

view raw toph_horrible_queries.cpp hosted with ❤ by GitHub