← 返回 openai 的题目列表Streaming Entropy with Online and Block-wise Updates
类型：online_judge
Problem: Streaming Entropy
Given a stream of discrete categorical observations, maintain the Shannon entropy of all observations seen so far, using the natural logarithm:
[ H = -\sum_i p_i \log p_i ]
where p_i = count_i / N, count_i is the number of occurrences of category i, and N is the total number of observations so far.
Implement a program that supports the following operations:
ADD x: add one observation of category x.
ADD_BLOCK m x1 c1 x2 c2 ... xm cm: add a block of observations. The block contains m distinct categories, and category xj is added cj times.
QUERY: output the current entropy.
Requirements:
After each ADD or ADD_BLOCK, you must not recompute entropy by iterating over all categories from scratch.
The implementation should be numerically stable and avoid repeatedly accumulating probabilities directly.
Print each QUERY result with 6 digits after the decimal point.
If the stream is empty, entropy is defined as 0.000000.
Input Format
The first line contains an integer q, the number of operations.
Each of the next q lines is one of the following:
ADD x
ADD_BLOCK m x1 c1 x2 c2 ... xm cm
QUERY
Where:
x, xi are category names represented as strings without spaces.
ci is a positive integer.
Constraints
1 <= q <= 2 * 10^5
Number of distinct categories is at most 2 * 10^5
Total number of added observations is at most 10^12
Categories within one ADD_BLOCK line are distinct.
Example
Input:
6
QUERY
ADD a
QUERY
ADD b
QUERY
ADD a
Output:
0.000000
0.000000
0.693147
Example
Input
6
QUERY
ADD a
QUERY
ADD b
QUERY
ADD a
Output
0.000000
0.000000
0.693147