第六题（NOIP2017）

#include<iostream>
using namespace std;
int n,s,a[100005],t[100005],i;
void mergesort(int l,int r){
    if(l==r)
        return;
    int mid=(l+r)/2;
    int p=l;
    int i=l;
    int j=mid+1;
    mergesort(l,mid);
    mergesort(mid+1,r);
    while(i<=mid&&j<=r){
        if(a[j]<a[i]){
            s+=mid-i+1;
            t[p]=a[j];
            p++;
            j++;
        } else {
            t[p]=a[i];
            p++;
            i++;
        }
    }
    while(i<=mid){
        t[p]=a[i];
        p++;
        i++;
    }
    while(j<=r){
        t[p]=a[j];
        p++;
        j++;
    }
    for(i=l;i<=r;i++) 
        a[i]=t[i];
}
int main(){
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>a[i];
    mergesort(1,n);
    cout<<s<<endl;
    return 0;
}

1. 【判断题】如果将第10行的mid+1改成mid，不会影响程序结果和时间复杂度。
   {{ select(1) }}

• 正确
• 错误

2. 【判断题】如果将第7行的(l+r)/2改成(l+r+1)/2，不会影响程序结果和时间复杂度。
   {{ select(2) }}

• 正确
• 错误

3. 【判断题】程序输出结果不可能是0。
   {{ select(3) }}

• 正确
• 错误

4. 【选择题】该程序的时间复杂度是（ ）。
   {{ select(4) }}

• O(n)
• O(nlogn)
• O(n√n)
• O(n²)

5. 【选择题】如果输入6 2 6 3 4 5 1，输出（ ）。
   {{ select(5) }}

• 1
• 2
• 4
• 8

6. 【选择题】该程序是求输入序列的（ ）。
   {{ select(6) }}

• 元素总和
• 逆序列
• 逆序对
• 卷积