# 数组范围查询频率与值相同的元素

2021年3月20日16:54:12 发表评论 693 次浏览

## 本文概述

``````query(start, end) = Number of times a
number x occurs exactly x times in a
subarray from start to end``````

## C ++

``````/* 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;

/* Returns the count of number x with
frequency x in the subarray from
start to end */
int solveQuery( int start, int end, int arr[])
{
// map for frequency of elements
unordered_map< int , int > frequency;

// store frequency of each element
// in arr[start; end]
for ( int i = start; i <= end; i++)
frequency[arr[i]]++;

// Count elements with same frequency
// as value
int count = 0;
for ( auto x : frequency)
if (x.first == x.second)
count++;
return count;
}

int main()
{
int A[] = { 1, 2, 2, 3, 3, 3 };
int n = sizeof (A) / sizeof (A[0]);

// 2D array of queries with 2 columns
int queries[][3] = { { 0, 1 }, { 1, 1 }, { 0, 2 }, { 1, 3 }, { 3, 5 }, { 0, 5 } };

// calculating number of queries
int q = sizeof (queries) / sizeof (queries[0]);

for ( int i = 0; i < q; i++) {
int start = queries[i][0];
int end = queries[i][1];
cout << "Answer for Query " << (i + 1)
<< " = " << solveQuery(start, end, A) << endl;
}

return 0;
}``````

## Java

``````/* Java Program to answer Q queries to
find number of times an element x
appears x times in a Query subarray */
import java.util.HashMap;
import java.util.Map;

class GFG
{

/* Returns the count of number x with
frequency x in the subarray from
start to end */
static int solveQuery( int start, int end, int arr[])
{
// map for frequency of elements
Map<Integer, Integer> mp = new HashMap<>();

// store frequency of each element
// in arr[start; end]
for ( int i = start; i <= end; i++)
mp.put(arr[i], mp.get(arr[i]) == null ? 1 :mp.get(arr[i])+ 1 );

// Count elements with same frequency
// as value
int count = 0 ;
for (Map.Entry<Integer, Integer> entry : mp.entrySet())
if (entry.getKey() == entry.getValue())
count++;
return count;
}

// Driver code
public static void main(String[] args)
{
int A[] = { 1 , 2 , 2 , 3 , 3 , 3 };
int n = A.length;

// 2D array of queries with 2 columns
int [][]queries = { { 0 , 1 }, { 1 , 1 }, { 0 , 2 }, { 1 , 3 }, { 3 , 5 }, { 0 , 5 } };

// calculating number of queries
int q = queries.length;

for ( int i = 0 ; i < q; i++)
{
int start = queries[i][ 0 ];
int end = queries[i][ 1 ];
System.out.println( "Answer for Query " + (i + 1 )
+ " = " + solveQuery(start, end, A));
}
}
}

// This code is contributed by Rajput-Ji``````

## Python3

``````# Python 3 Program to answer Q queries
# to find number of times an element x
# appears x times in a Query subarray
import math as mt

# Returns the count of number x with
# frequency x in the subarray from
# start to end
def solveQuery(start, end, arr):

# map for frequency of elements
frequency = dict ()

# store frequency of each element
# in arr[start end]
for i in range (start, end + 1 ):

if arr[i] in frequency.keys():
frequency[arr[i]] + = 1
else :
frequency[arr[i]] = 1

# Count elements with same
# frequency as value
count = 0
for x in frequency:
if x = = frequency[x]:
count + = 1
return count

# Driver code
A = [ 1 , 2 , 2 , 3 , 3 , 3 ]
n = len (A)

# 2D array of queries with 2 columns
queries = [[ 0 , 1 ], [ 1 , 1 ], [ 0 , 2 ], [ 1 , 3 ], [ 3 , 5 ], [ 0 , 5 ]]

# calculating number of queries
q = len (queries)

for i in range (q):
start = queries[i][ 0 ]
end = queries[i][ 1 ]
print ( "Answer for Query " , (i + 1 ), " = " , solveQuery(start, end, A))

# This code is contributed
# by Mohit kumar 29``````

## C#

``````// C# Program to answer Q queries to
// find number of times an element x
// appears x times in a Query subarray
using System;
using System.Collections.Generic;

class GFG
{
/* Returns the count of number x with
frequency x in the subarray from
start to end */
public static int solveQuery( int start, int end, int [] arr)
{

// map for frequency of elements
Dictionary< int , int > mp = new Dictionary< int , int >();

// store frequency of each element
// in arr[start; end]
for ( int i = start; i <= end; i++)
{
if (mp.ContainsKey(arr[i]))
mp[arr[i]]++;
else
}

// Count elements with same frequency
// as value
int count = 0;
foreach (KeyValuePair< int , int > entry in mp)
{
if (entry.Key == entry.Value)
count++;
}
return count;
}

// Driver code
public static void Main(String[] args)
{
int [] A = { 1, 2, 2, 3, 3, 3 };
int n = A.Length;

// 2D array of queries with 2 columns
int [, ] queries = {{ 0, 1 }, { 1, 1 }, { 0, 2 }, { 1, 3 }, { 3, 5 }, { 0, 5 }};

// calculating number of queries
int q = queries.Length;

for ( int i = 0; i < q; i++)
{
int start = queries[i, 0];
int end = queries[i, 1];
Console.WriteLine( "Answer for Query " + (i + 1) +
" = " + solveQuery(start, end, A));
}
}
}

// This code is contributed by
// sanjeev2552``````

``````Answer for Query 1 = 1
Answer for Query 2 = 0
Answer for Query 3 = 2
Answer for Query 4 = 1
Answer for Query 5 = 1
Answer for Query 6 = 3``````

MO的算法

.

MO_RIGHT

MO_LEFT

``````/* 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
void add( int x, int & currentAns, unordered_map< int , int >& freq)
{

// increment frequency of this element
freq[x]++;

// if this element was previously
// contributing to the currentAns, // decrement currentAns
if (freq[x] == (x + 1))
currentAns--;

// if this element has frequency
// equal to its value, increment
// currentAns
else if (freq[x] == x)
currentAns++;
}

/* Removes element (x) from current
range btw L and R and updates
void remove ( int x, int & currentAns, unordered_map< int , int >& freq)
{

// decrement frequency of this element
freq[x]--;

// if this element has frequency equal
// to its value, increment currentAns
if (freq[x] == x)
currentAns++;

// if this element was previously
// contributing to the currentAns
// decrement currentAns
else if (freq[x] == (x - 1))
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)
{

// 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 = 0;

// 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;
int index = q[i].index;

// 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], currentAns, freq);
currL++;
}

// Add Elements of current Range
while (currL > L) {
currL--;
}
while (currR <= R) {
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], currentAns, freq);
}

// Store current ans as the Query ans for
// Query number index
ans[index] = currentAns;
}
}

/* Wrapper for queryResultsUtil() and outputs the
ans array constructed by answering all queries */
void queryResults( int a[], int n, Query q[], int m)
{
// 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);

for ( int i = 0; i < m; i++) {
cout << "Answer for Query " << (i + 1)
<< " = " << ans[i] << endl;
}
}

// Driver program
int main()
{
int A[] = { 1, 2, 2, 3, 3, 3 };

int n = sizeof (A) / sizeof (A[0]);

// 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);

return 0;
}``````

``````Answer for Query 1 = 1
Answer for Query 2 = 0
Answer for Query 3 = 2
Answer for Query 4 = 1
Answer for Query 5 = 1
Answer for Query 6 = 3``````