New solution of sequence query

Topic background

The previous question "sequence query" said: A=[A0,A1,A2 ···, An] is a sequence composed of n+1 integers in the range of [0,N], which satisfies 0 = A0 < A1 < A2 < ·· < An < n. Based on sequence a, for any integer x within the range of [0,N], the query f(x) is defined as the subscript of the largest number of integers less than or equal to X in sequence a.

For A given sequence A and integer x, the query f(x) is A very classic problem, which can be easily solved within the time complexity of O(log n) using binary search. But when the IT Department discussed how to realize this function, little P put forward some new ideas.

Title Description

Input format

Read in data from standard input.

The first line of input contains two positive integers n and N separated by spaces.

The second line of input contains n integers A1,A2, ···, AN separated by spaces.

Note that A0 is fixed to 0, so A0 is not included in the input data.

Output format

Output to standard output.

Only one integer is output to represent the value of error(A).

Example 1 input

3 10
2 5 8

Sample 1 output

5

Example 1 explanation

Example 2 Input

9 10
1 2 3 4 5 6 7 8 9

Sample 2 output

0

Sample input 3

2 10
1 3

Sample 3 output

6

Sample 3 output

Subtask

Tips

It should be noted that the input data [A1,A2 ····, An] are not necessarily evenly distributed in the (0,N) interval, so the total error(A) may be very large.

code

#include <bits/stdc++.h>
using namespace std;
long long n, N;
const long long Maxn = 1e5 + 5;
long long arr[Maxn] = { 0 };
long long vi[Maxn] = { 0 };
long long r;
long long num = 0;
long long add(long long first, long long count) {//First represents the first g (x) - f (x), and count represents that the interval contains several equally divided intervals
    long long last = first + count - 1;//Last term, if the interval is in an average partition, last is equal to 2*first
    long long final;
    if (last * first >= 0)//The same symbol indicates that the starting point and the ending point are in the same partition
        return final = abs((first + last) * count / 2 * r);//That is, the sum of all absolute values from the starting point to the end is calculated, * r represents all sums in the interval
    else//Different symbols, first is a negative number, indicating that the two points are not in the same partition
        return final = (abs(first) + 1) * abs(first) / 2 * r + last * (last + 1) / 2 * r;//Calculate positive and negative numbers separately
}
int main()
{
    cin >> n >> N;
    arr[0] = 0;
    long long lea = 0;//Represents the final result
    long long co,k;
    r = N / (n + 1);
    for (long long i = 1; i <= n; i++) {
        cin >> arr[i]; 
        vi[i] = arr[i] - arr[i - 1];//Using vi array to store the length of interval
    }
    vi[n+1]= N - arr[n];//The length of the section in which the last read data is stored is greater than the last read data
    for (long long i = 1; i <= n+1; i++) {
        co = (vi[i]+ lea)/r;//Calculate how many equal intervals the current interval is equivalent to
        k = arr[i - 1] / r;//Calculate the value corresponding to g(x) of the first element at the beginning of the interval
        num += add(k - i + 1, co);//Calculate and add the error value of the interval
        if(k-i+1>=0)num += lea;//If G (x) > F (x) of the current interval, add the number of extra numbers between the average partitions
        else num -= lea;//Otherwise, the current interval subtracts the number of extra digits in the average partition
        lea = (vi[i] + lea) % r;//lea indicates the number of numbers not in the first part of the partition
    }
    k += co;
    num += abs(k - n) * lea;//Finally, add the absolute value of the difference between g(x) and f(x) multiplied by the number of remaining uncomputed numbers
    cout<<num;
    return 0;
}

thinking

The idea is to calculate the r in the topic first, and divide the section of [0,N] into N/r equally divided sections. In the corresponding section, the values of g(x) corresponding to all numbers are the same. Then, another segmentation is carried out for the section of [0,N] through the read array. This segmentation determines f(x) and divides the same number of f(x) into an interval. Then, take one segment of the second segment each time, judge whether the left and right ends of the interval belong to the same equally divided interval, then judge the positive and negative of the difference between g(x) and f(x) in the interval, then calculate the sum of the absolute values of the difference in the interval, and finally cycle calculation.