محدودیت زمان: ۲ ثانیه محدودیت حافظه: ۲۵۶ مگابایت اگر دنبالهای از اعداد داشته باشید به…
- User
محدودیت زمان: ۲ ثانیه محدودیت حافظه: ۲۵۶ مگابایت اگر دنبالهای از اعداد داشته باشید به اولین عدد طبیعیای که در آن ظاهر نشده Mex آن دنباله میگوییم. برای مثال Mex دنباله ( 1 , 2 , 5 , 9 ) (1,2,5,9) برابر 3 3 و Mex دنباله ( 2 , 5 ) (2,5) برابر 1 1 است.
دنباله a 1 , a 2 , a 3 , . . . , a n
a 1 ,a 2 ,a 3 ,...,a n به شما داده شده است و باید جمع Mex تمام زیربازههای آن را به دست بیاورید. (در مجموع n ( n + 1 ) 2 2 n(n+1) زیربازه داریم.)
در واقع اگر
M e x i , j Mex i,j را برابر Mex زیر دنباله ( a i , a i + 1 , . . . , a j )
(a i ,a i+1 ,...,a j ) تعریف کنیم، شما باید مقدار زیر را چاپ کنید. ∑ i
1 n
∑ j
i n M e x i , j i=1 ∑ n
j=i ∑ n Mex i,j
ورودی در سطر اول ورودی عدد n n و در سطر دوم n n عدد به شما داده میشود که عدد i i-ام برابر عضو i i ام دنباله است.
1 ≤ n , a i ≤ 100
000 1≤n,a i ≤100 000
خروجی در تنها خط خروجی مقدار خواسته شده را نمایش دهید.
مثال ورودی نمونه ۱ 5 1 2 3 4 5 Plain text خروجی نمونه ۱ 30 Plain text توضیح:
M e x 1 , 1
2 Mex 1,1 =2 M e x 1 , 2
3 Mex 1,2 =3 M e x 1 , 3
4 Mex 1,3 =4 M e x 1 , 4
5 Mex 1,4 =5 M e x 1 , 5
6 Mex 1,5 =6
و Mex زیربازههایی که ۱ را ندارند برابر ۱ است.
ورودی نمونه ۲ 8 2 1 4 2 1 3 2 1 Plain text خروجی نمونه ۲ 113 write code in java17
- Assistant
To solve the problem of calculating the sum of the Mex of all possible subarrays of a given array efficiently, we need to carefully consider both the constraints and the steps involved.
Problem Analysis
Given a sequence of numbers, the Mex of any subarray is defined as the smallest positive integer that does not appear in that subarray. The task is to compute the sum of Mex values for all possible subarrays.
Given the constraints:
- n can be as large as 100,000
- Each element of the array can be as large as 100,000
Direct computation for every subarray is infeasible due to the high computational complexity. Therefore, we need a more optimized approach.
Optimized Approach
The key observation is recognizing that for each possible Mex value ( k ), we can count the number of subarrays where the Mex is exactly ( k ). Once we have this count, we can multiply it by ( k ) and accumulate the result to get the final sum.
Step-by-Step Strategy:
-
Identify Subarrays for Each Mex ( k ):
- For a given ( k ), count the number of subarrays that contain all integers from 1 to ( k-1 ) but do not contain ( k ).
- This number is denoted as ( f(k) ).
-
Use Two-Pointers to Efficiently Count Subarrays:
- Iterate through each possible ( k ) and use the two-pointer technique to calculate ( f(k) ).
- For each segment of the array that does not contain ( k ), calculate how many subarrays contain all integers from 1 to ( k-1 ).
- By maintaining frequency counts and ensuring that all required integers are present, we can efficiently compute the number of valid subarrays.
-
Optimize to Handle Large Constraints:
- Precompute positions of each integer in the array to quickly split the array into segments that do not contain ( k ).
- This allows us to handle each ( k ) without repeatedly traversing the entire array, significantly reducing the number of operations.
-
Accumulate the Result:
- For each ( k ), compute the product of ( k ) and ( f(k) ), then add it to the total sum.
Implementation
Below is the Java code implementation of the above approach:
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; public class SumOfMex { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // Read n int n = Integer.parseInt(br.readLine()); // Read array String[] parts = br.readLine().split(" "); int[] a = new int[n]; int max_a = 0; for(int i=0;i<n;i++) { a[i] = Integer.parseInt(parts[i]); if(a[i]>max_a) max_a = a[i]; } // Initialize list of positions for each k // Using max_a+2 to include k = max_a+1 ArrayList<Integer>[] lists = new ArrayList[max_a + 2]; for(int k=1;k<=max_a+1;k++) { lists[k] = new ArrayList<>(); } // Fill the lists for(int i=0;i<n;i++) { if(a[i] <= max_a+1) { lists[a[i]].add(i); } } long totalSum =0; // Precompute for k=1 separately // For k=1, f(k) is number of subarrays not containing1 // Which are segments between positions where a[i]==1 ArrayList<Integer> list1 = lists[1]; ArrayList<int[]> segments1 = new ArrayList<>(); int prev = -1; for(int pos : list1) { if(prev +1 <= pos -1){ segments1.add(new int[]{prev+1, pos-1}); } prev = pos; } if(prev +1 <= n-1){ segments1.add(new int[]{prev+1, n-1}); } // Count number of subarrays in these segments long cnt1=0; for(int[] seg : segments1){ int len = seg[1]-seg[0]+1; cnt1 += ((long)len * (len +1))/2; } totalSum += 1L * cnt1; // Now handle k from2 to max_a+1 // To keep track of the last positions of 1 to k-1 // To optimize, we can maintain an array of last seen positions // and find the minimum left boundary for each window // But in this implementation, we use sliding window per segment // To optimize, we can limit k up to some value where f(k) >0 // Practically, f(k) =0 when {1..k-1} not present in any segment // So we proceed up to max_a+1 // Precompute all lists up to max_a+1 // To speed up, avoid processing k where k-1 > max_a for(int k=2; k<=max_a+1; k++) { ArrayList<Integer> currentList = lists[k]; ArrayList<int[]> segments = new ArrayList<>(); prev = -1; for(int pos : currentList) { if(prev +1 <= pos -1){ segments.add(new int[]{prev+1, pos-1}); } prev = pos; } if(prev +1 <= n-1){ segments.add(new int[]{prev+1, n-1}); } // For each segment, count number of subarrays containing all {1,..,k-1} long cnt =0; for(int[] seg : segments){ int left = seg[0]; int right = seg[1]; if(k-1 > max_a){ // Impossible to have all {1..k-1} continue; } // Check if k-1 <= max_a, otherwise skip if(k-1 >=1 && k-1 <= max_a){ // Implement sliding window to count subarrays containing all {1,..,k-1} // Initialize frequency array int need = k-1; int have =0; int[] freq = new int[k]; // 1 to k-1 int l = left; for(int r=left; r<=right; r++){ if(a[r] >=1 && a[r] <=k-1){ freq[a[r]]++; if(freq[a[r]] ==1){ have++; } } while(have == need){ // All {1..k-1} are present cnt += (right - r +1); if(a[l] >=1 && a[l] <=k-1){ freq[a[l]]--; if(freq[a[l]] ==0){ have--; } } l++; } } } } // Add k * cnt to totalSum totalSum += (long)k * cnt; } System.out.println(totalSum); } }Explanation of the Code:
-
Input Handling:
- The code starts by reading the number of elements,
n, and the array itself. - It then determines the maximum value in the array to set the bounds for processing each possible Mex ( k ).
- The code starts by reading the number of elements,
-
Preprocessing:
- We create an array of lists
listswherelists[k]contains all positions in the array where the value ( k ) appears. - This helps in easily identifying segments of the array that do not contain a particular ( k ).
- We create an array of lists
-
Handling Mex = 1:
- For ( k = 1 ), the Mex is 1 for any subarray that doesn't contain the value 1.
- We identify all such segments and calculate the number of valid subarrays within these segments.
-
Handling Mex > 1:
- For each ( k ) from 2 to
max_a + 1, we identify segments of the array that do not contain ( k ). - Within each of these segments, we use the two-pointer technique to count how many subarrays contain all integers from 1 to ( k-1 ).
- The count is then multiplied by ( k ) and added to the total sum.
- For each ( k ) from 2 to
-
Output:
- Finally, after processing all possible ( k ), the total sum is printed as the result.
Performance Considerations:
- The algorithm avoids direct ( O(n^2) ) computations by intelligently splitting the array into manageable segments and applying a sliding window approach.
- The use of precomputed lists for each ( k ) significantly reduces the computational overhead, making it feasible to handle large inputs within practical time limits.
Conclusion
This optimized approach efficiently calculates the sum of Mex values for all subarrays of a given array, even under large constraints. By leveraging the properties of Mex and using strategic preprocessing and sliding window techniques, the problem becomes manageable within the required time and space limits.