/* C++ Program to answer Q queries to
find number of times an element x
appears x times in a Query subarray */
#include <bits/stdc++.h>
using namespace std;
// Variable to represent block size.
// This is made global so compare()
// of sort can use it.
int block;
// Structure to represent a query range
struct Query {
int L, R, index;
};
/* Function used to sort all queries
so that all queries of same block
are arranged together and within
a block, queries are sorted in
increasing order of R values. */
bool compare(Query x, Query y)
{
// Different blocks, sort by block.
if (x.L / block != y.L / block)
return x.L / block < y.L / block;
// Same block, sort by R value
return x.R < y.R;
}
/* Inserts element (x) into current range
and updates current answer */
void add(int x,
unordered_map<int, int>& freq)
{
// increment frequency of this element
freq[x]++;
// if this element was previously
// contributing to the currentAns,
}
/* Removes element (x) from current
range btw L and R and updates
current Answer */
void remove(int x,
unordered_map<int, int>& freq)
{
// decrement frequency of this element
freq[x]--;
// if this element has frequency equal
// to its value, increment currentAns
}
/* Utility Function to answer all queries
and build the ans array in the original
order of queries */
void queryResultsUtil(int a[], Query q[],
int ans[], int m,int b[],int len_b)
{
// map to store freq of each element
unordered_map<int, int> freq;
// Initialize current L, current R
// and current sum
int currL = 0, currR = 0;
int currentAns = 1;
// Traverse through all queries
for (int i = 0; i < m; i++) {
// L and R values of current range
int L = q[i].L, R = q[i].R;
L--;
R--;
int index = q[i].index;
ans[index] = 1;
// Remove extra elements of previous
// range. For example if previous
// range is [0, 3] and current range
// is [2, 5], then a[0] and a[1] are
// removed
while (currL < L) {
remove(a[currL], freq);
currL++;
}
// Add Elements of current Range
while (currL > L) {
currL--;
add(a[currL], freq);
}
while (currR <= R) {
add(a[currR], freq);
currR++;
}
// Remove elements of previous range. For example
// when previous range is [0, 10] and current range
// is [3, 8], then a[9] and a[10] are Removed
while (currR > R + 1) {
currR--;
remove(a[currR], freq);
}
//cout<<L<<R<<"\n";
for(int j=1;j<=len_b;j++)
{
//cout<<freq[j]<<" "<<j<<"\n";
if(freq[j]>0 && freq[j]!=b[j-1])
{
ans[index]=0;
//cout<<;
break;
}
}
// Store current ans as the Query ans for
// Query number index
//cout<<"\n";
}
}
/* Wrapper for queryResultsUtil() and outputs the
ans array constructed by answering all queries */
void queryResults(int a[], int n, Query q[], int m,int b[],int len_b)
{
// Find block size
block = (int)sqrt(n);
// Sort all queries so that queries of same blocks
// are arranged together.
sort(q, q + m, compare);
int* ans = new int[m];
queryResultsUtil(a, q, ans, m, b, len_b);
for (int i = 0; i < m; i++) {
cout << ans[i] << endl;
}
}
// Driver program
int main()
{ int n,m;
cin>>n>>m;
int A[n],b[m];
for(int i=0;i<n;i++)
cin>>A[i];
for(int i=0;i<m;i++)
cin>>b[i];
int q;
cin>>q;
Query queries[q];
for(int i=0;i<q;i++)
{cin>>queries[i].L>>queries[i].R;
queries[i].index=i;
}
/* // 2D array of queries with 2 columns
Query queries[] = { { 0, 1, 0 },
{ 1, 1, 1 },
{ 0, 2, 2 },
{ 1, 3, 3 },
{ 3, 5, 4 },
{ 0, 5, 5 } };
// calculating number of queries
int q = sizeof(queries) / sizeof(queries[0]);
*/
// Print result for each Query
queryResults(A, n, queries, q, b, m);
return 0;
} Write, Run & Share C++ code online using OneCompiler's C++ online compiler for free. It's one of the robust, feature-rich online compilers for C++ language, running on the latest version 17. Getting started with the OneCompiler's C++ compiler is simple and pretty fast. The editor shows sample boilerplate code when you choose language as C++ and start coding!
OneCompiler's C++ online compiler supports stdin and users can give inputs to programs using the STDIN textbox under the I/O tab. Following is a sample program which takes name as input and print your name with hello.
#include <iostream>
#include <string>
using namespace std;
int main()
{
string name;
cout << "Enter name:";
getline (cin, name);
cout << "Hello " << name;
return 0;
}
C++ is a widely used middle-level programming language.
When ever you want to perform a set of operations based on a condition If-Else is used.
if(conditional-expression) {
//code
}
else {
//code
}
You can also use if-else for nested Ifs and If-Else-If ladder when multiple conditions are to be performed on a single variable.
Switch is an alternative to If-Else-If ladder.
switch(conditional-expression){
case value1:
// code
break; // optional
case value2:
// code
break; // optional
......
default:
code to be executed when all the above cases are not matched;
}
For loop is used to iterate a set of statements based on a condition.
for(Initialization; Condition; Increment/decrement){
//code
}
While is also used to iterate a set of statements based on a condition. Usually while is preferred when number of iterations are not known in advance.
while (condition) {
// code
}
Do-while is also used to iterate a set of statements based on a condition. It is mostly used when you need to execute the statements atleast once.
do {
// code
} while (condition);
Function is a sub-routine which contains set of statements. Usually functions are written when multiple calls are required to same set of statements which increases re-usuability and modularity. Function gets run only when it is called.
return_type function_name(parameters);
function_name (parameters)
return_type function_name(parameters) {
// code
}