Logarithmic calculation in reverse order, logarithmic calculation in sequence -- merge sort

/ If this number of the second sequence ( First number not compared ,
  // Because the sequence is already ordered , This number must be the smallest number in the second sequence that has not been compared ,)
 // Smaller than any number in the first sequence that has not been compared , Then all the numbers of the first sequence that have not been compared can be compared with
 // This number of the second segment of the sequence forms an inverse pair

void my_merge(int *a,int l1,int r1,int l2,int r2)// Two ordered sequences , Merge into an ordered sequence
{
    int temp[r2-l1+1],index=0,i=l1,j=l2;
    while(i<=r1&&j<=r2)
    {
        if(a[i]<=a[j])
            temp[index++]=a[i++];
        else
        {
            temp[index++]=a[j++];
            res+=r1-i+1;    // If this number of the second sequence ( First number not compared ,
                   // Because the sequence is already ordered , This number must be the smallest number in the second sequence that has not been compared ,)
                       // Smaller than any number in the first sequence that has not been compared , Then all the numbers of the first sequence that have not been compared can be compared with
                           // This number of the second segment of the sequence forms an inverse pair
        }
    }

    while(i<=r1)
        temp[index++]=a[i++];
    while(j<=r2)
        temp[index++]=a[j++];
    for(i=0;i<index;++i)
        a[l1+i]=temp[i];
}

  Complete code ：

/**
     Find the reverse logarithm with merge sort 
*/

/**
     Merge sort 
    tow point ： Combine two ordered sequences into one ,O(n)
*/

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
using namespace std;
int res=0;
void my_merge(int *a,int l1,int r1,int l2,int r2)// Two ordered sequences , Merge into an ordered sequence 
{
    int temp[r2-l1+1],index=0,i=l1,j=l2;
    while(i<=r1&&j<=r2)
    {
        if(a[i]<=a[j])
            temp[index++]=a[i++];
        else
        {
            temp[index++]=a[j++];
            res+=r1-i+1;
        }
    }

    while(i<=r1)
        temp[index++]=a[i++];
    while(j<=r2)
        temp[index++]=a[j++];
    for(i=0;i<index;++i)
        a[l1+i]=temp[i];
}

void mergesort(int *a,int l,int r)
{
    if(l>=r)
        return;
    else
    {
        int mid=l+(r-l)/2;
        mergesort(a,l,mid);
        mergesort(a,mid+1,r);
        my_merge(a,l,mid,mid+1,r);
    }
}

int main()
{
    int n;
    cin >> n;
    int a[n];
    for(int i=0;i<n;++i)
        cin >> a[i];

    int sum=0;
    for(int i=0;i<n;++i)
        for(int j=i+1;j<n;++j)
            if(a[i]>a[j])// Enumeration algorithm 
                ++sum;
    printf("sum: %d\n",sum );
    mergesort(a,0,n);
    for(auto b: a)
        cout << b << ' ';
    cout << endl;
    printf("%d\n",res);
    cout << "Hello world!" << endl;
    return 0;
}

  Now that the reverse order pairs have been calculated , So the order is different , Sequence pair definition ：dp[i] < dp[j] (i<j);

Here is a topic ： In reverse order , Calculate each one in sequence ：

1.5.3 A series of questions

Description

Given a number string , The length of the string is nnn , Now define the sum of each number of a substring as the sum of the numbers of the substring , Please find out how many substrings in the string are positive .

Input

Number one on the first line nnn , Indicates the length of the string . The second line is a total of nnn Number , It means that each number in the string outputs one number , The sum of the strings indicating the number of substrings in the string is a positive number .

Output

A positive number is the answer .

Sample Input 1

3
8 -9 2

Sample Output 1

3

Hint

100% nnn ≤ 100000 The sum of all numbers is int Within limits

analysis ： The problem of finding a string of numbers in reverse order , Find the suffix sum of the sequence , To get a positive sum of substrings , namely
    dp[i]>dp[j](i<j), That is, find the logarithm of the reverse pair in a sequence

/**
     The problem of finding a string of numbers in reverse order , Find the suffix sum of the sequence , To get a positive sum of substrings , namely 
    dp[i]>dp[j](i<j), That is, find the logarithm of the reverse pair in a sequence 
*/

/**
#include <iostream>

using namespace std;
long long res=0;  // here res Yes, it needs to be defined as long long, Otherwise, the answer will be wrong 
void my_merge(int *a,int l1,int r1,int l2,int r2)// Two ordered sequences , Merge into an ordered sequence 
{
    int temp[r2-l1+1],index=0,i=l1,j=l2;
    while(i<=r1&&j<=r2)
    {
        if(a[i]<=a[j])
            temp[index++]=a[i++];
        else
        {
            temp[index++]=a[j++];
            res+=r1-i+1;    // If this number of the second sequence ( First number not compared ,
                           // Because the sequence is already ordered , This number must be the smallest number in the second sequence that has not been compared ,)
                           // Smaller than any number in the first sequence that has not been compared , Then all the numbers of the first sequence that have not been compared can be compared with 
                           // This number of the second segment of the sequence forms an inverse pair 
        }
    }

    while(i<=r1)
        temp[index++]=a[i++];
    while(j<=r2)
        temp[index++]=a[j++];
    for(i=0;i<index;++i)
        a[l1+i]=temp[i];
}

void mergesort(int *a,int l,int r)
{
    if(l>=r)
        return;
    else
    {
        int mid=l+(r-l)/2;
        mergesort(a,l,mid);
        mergesort(a,mid+1,r);
        my_merge(a,l,mid,mid+1,r);
    }
}

int main()
{
    int n;
    scanf("%d",&n);
    int a[n+1],dp[n+2],val;
    dp[n+1]=0;
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
    }

    for(int i=n;i>0;--i)
        dp[i]=dp[i+1]+a[i]; //dp Denotes suffixes and 


    mergesort(dp,1,n+1);// The parameter here is n+1, because dp[n]-dp[n+1] It means a[i] The value of this number ,
                        // But the parameters you pass are n Words , The last number is removed 
    printf("%lld\n",res);
    return 0;
}
*/

  So can we use the prefix sum to calculate ？
    Prefix and calculation i.e dp[i] < dp[j] (i<j), That is, find the number of sequence pairs in a sequence ,
    Also use recursive sorting to find

/**
     So can we use the prefix sum to calculate ？
     Prefix and calculation i.e dp[i] < dp[j] (i<j), That is, find the number of sequence pairs in a sequence ,
     Also use recursive sorting to find 
*/

#include <iostream>

using namespace std;
long long res=0;  // here res Yes, it needs to be defined as long long, Otherwise, the answer will be wrong 
void my_merge(int *a,int l1,int r1,int l2,int r2)// Two ordered sequences , Merge into an ordered sequence 
{
    int temp[r2-l1+1],index=0,i=l1,j=l2;
    while(i<=r1&&j<=r2)
    {
        if(a[i]<a[j])
        {
            temp[index++]=a[i++];
            res+=r2-j+1;   // If this number of the first sequence ( First number not compared ,
                           // Because the sequence is already ordered , This number must be the smallest number in the first sequence that has not been compared ,)
                           // Smaller than any number of the second sequence that has not been compared , Then all the numbers of the second sequence that have not been compared can be compared with 
        }                  // This number of the first sequence forms a sequence pair 
        else
            temp[index++]=a[j++];
    }

    while(i<=r1)
        temp[index++]=a[i++];
    while(j<=r2)
        temp[index++]=a[j++];
    for(i=0;i<index;++i)
        a[l1+i]=temp[i];
}

void mergesort(int *a,int l,int r)
{
    if(l>=r)
        return;
    else
    {
        int mid=l+(r-l)/2;
        mergesort(a,l,mid);
        mergesort(a,mid+1,r);
        my_merge(a,l,mid,mid+1,r);
    }
}

int main()
{
    int n;
    scanf("%d",&n);
    int dp[n+1],val;
    dp[0]=0;
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&val);
        dp[i]=dp[i-1]+val;  //dp Represents the prefix and of a sequence of numbers 
    }

    mergesort(dp,0,n);/** The second parameter here is 0, because dp[1]-dp[0] It means a[1] The value of this number ,
                         But the parameters you pass are 1 Words , The first number is removed */
    printf("%lld\n",res);
    return 0;
}