注意到

本题两种做法

题意： 每个数得分 = 它左边比它小的数的数量，找到最大得分，≥k 输出 Yes，否则 No。

1：树状数组

从左逐个遍历数组；

查询 1~a[i]-1 已有多少数 → 当前得分；

把 a [i] 加入树状数组；

全程记录最大得分，最后判断。

复杂度：O (nlogn)

2：归并分治

（上机培训让你求了逆序对个数，这次其实是正序对)

数组不断分成左右两段，左段全都在右段左边；

合并有序数组时，统计左小于右的数量，累加进得分；

递归算出所有得分，取最大值判断。

复杂度：O (nlogn)

证明如下

1. 暴力算法不可行证明 总统计次数：T = 0+1+2+...+(n-1) = n*(n-1)/2，时间复杂度 O (n²)

代入 n=5*10 的 5 次方，运算总量约 1.25 乘 10 的 11 次方次。

电脑一秒最多运行 10 的 8 次方次运算，计算耗时远大于题目 1~2 秒时限，暴力超时不能用。

2. 树状数组解法

cnt [x]=1 代表数字 x 之前出现过

每个元素得分 = 1 到 a [i]-1 所有已出现数字总数 = 查询 (a [i]-1)

顺序遍历：先查得分，再把当前数字标记存入，计算逻辑和题目定义完全一致。

复杂度 单次查询、修改耗时 log n，n 个数字总复杂度 O (n log n)

3. 归并排序解法

区间分成左 [l,mid]、右 [mid+1,r]，左边所有数在原数组都排在右边数前面。

合并有序数组时统计左边小于右边的数字个数，递归结束得到全部得分。

复杂度 递归层数 log n，每层一共遍历 n 个数据，总复杂度 O (n log n)

C++树状数组解法

const int N=5e5+5;
int tr[N];
void add(int x)
{
	for(;x<N;x+=x&-x)
	tr[x]++;
}

int qry(int x)
{
	int s=0;
	for(;x;x-=x&-x)
	s+=tr[x];
	return s;
}
int main()
{
    AC;
    int n,k;
	cin>>n>>k;
	int ok=0;
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		int s=qry(x-1);
		if(s>=k)
		ok=1;
		add(x);
	}
	cout<<(ok?"Yes":"No");
    return 0;
}

Python 树状数组解法

import sys
def main():
    data=sys.stdin.read().split()
    n=int(data[0])
    k=int(data[1])
    size=500005
    tree=[0]*size
    def add(x):
        while x<size:
            tree[x]+=1
            x+=x&-x
    def query(x):
        sum=0
        while x>0:
            sum+=tree[x]
            x-=x&-x
        return sum
    ok=0
    idx=2
    for _ in range(n):
        x=int(data[idx])
        idx+=1
        res=query(x-1)
        if res>=k:
            ok=1
        add(x)
    print("Yes"if ok else"No")
main()

C++ 归并排序解法

const int N=500005;
pair<int,int> arr[N];
int cnt[N];
int n,k;
bool merge_sort(int l,int r)
{
    if(l>=r) return false;
    int mid=(l+r)/2;
    if(merge_sort(l,mid)) return true;
    if(merge_sort(mid+1,r))  return true;
    int i=l;
    for(int j=mid+1;j<=r;j++)
    {
        while(i<=mid && arr[i].first<arr[j].first)  i++;
        cnt[arr[j].second]+=i-l;
        if(cnt[arr[j].second]>=k)  return true;
    }
    vector<pair<int,int>> tmp;
    i=l;
    int j=mid+1;
    while(i<=mid && j<=r)
    {
        if(arr[i].first<=arr[j].first)
        {
            tmp.push_back(arr[i]);
            i++;
        }
        else
        {
            tmp.push_back(arr[j]);
            j++;
        }
    }
    while(i<=mid)
    {
        tmp.push_back(arr[i]);
        i++;
    }
    while(j<=r)
    {
        tmp.push_back(arr[j]);
        j++;
    }
    for(int p=l;p<=r;p++) arr[p]=tmp[p-l];
    return false;
}
int main()
{
    AC;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>arr[i].first;
        arr[i].second=i;
    }
    if(merge_sort(1,n)) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

Python 归并排序解法

import sys
def main():
    data=sys.stdin.read().split()
    n=int(data[0])
    k=int(data[1])
    a=list(map(int,data[2:2+n]))
    arr=[(a[i],i) for i in range(n)]
    cnt=[0]*n
    def merge_sort(l,r):
        if l>=r:
            return False
        mid=(l+r)//2
        if merge_sort(l,mid):
            return True
        if merge_sort(mid+1,r):
            return True
        i=l
        for j in range(mid+1,r+1):
            while i<=mid and arr[i][0]<arr[j][0]:
                i+=1
            cnt[arr[j][1]]+=i-l
            if cnt[arr[j][1]]>=k:
                return True
        temp=[]
        i=l
        j=mid+1
        while i<=mid and j<=r:
            if arr[i][0]<=arr[j][0]:
                temp.append(arr[i])
                i+=1
            else:
                temp.append(arr[j])
                j+=1
        temp+=arr[i:mid+1]
        temp+=arr[j:r+1]
        arr[l:r+1]=temp
        return False
    print("Yes"if merge_sort(0,n-1)else"No")
main()