题目链接

解析

题意就不多阐述了，看原题就够了。个人觉得这是一道练归并排序性质的好题（虽然动规/堆维护等方法似乎也可行，但我认为最朴素的方法才是最美丽的）。

再发觉贪心不可行时，我们考虑分治维护每一轮比赛可能获胜的人。假设我们以及维护好了左区间（即上一轮比赛）哪些人可能能在上一轮获得胜利（也就是能活到当前这轮）以及右区间的这个信息，我们考虑如何合并。显然，我们发现，如果想要让左区间的某个人获胜，只需要这个人能够击败右区间尚存的最弱的那个人就可以了，右区间亦然。

这时候我们考虑如何维护区间最弱的人这个信息。在分治这个大背景下，我们容易想到归并排序——每个区间在合并时都是有序的，只需要取出第一个数就是最小的。同时我们还可以在归并排序时每次返回改区间尚存的人数，这样，我们就一次性维护好了尚存的人和区间最弱的人这两个信息。

依次合并，最后判断尚存的人中是否有 $1$ 号选手即可。代码写了一些注释。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
struct node{
    int val,id;//记录每个元素的支持人数和序号，序号用来判结果
}a[N],b[N];
int T,k,m;
inline int merge(int l,int r){//返回该轮尚存的人数
    if(l==r) return 1;
    int mid=(l+r)>>1;
    int L=merge(l,mid)+l-1;//记录左区间尚存的人的位置
    int R=merge(mid+1,r)+mid;//同上
    int i=l,j=mid+1,cnt=l-1;
    if(a[i].val<=a[j].val){//第一个数比大小，显然，第一个数大的那边的所有尚存选手都可以继续存活
        while(i<=L&&a[i].val+m<a[j].val) i++;//因为 kotori 可以定胜负，所以用 < 号。
    }
    else{
        while(j<=R&&a[j].val+m<a[i].val) j++;
    }
    while(i<=L&&j<=R){//正常归并排序，就是左右区间的上界变了而已
        if(a[i].val<a[j].val) b[++cnt]=a[i++];
        else b[++cnt]=a[j++];
    }
    while(i<=L) b[++cnt]=a[i++];
    while(j<=R) b[++cnt]=a[j++];
    for(int i=l;i<=cnt;i++){//容易发现，每次归并了之后，只有前 cnt 个人是有效的，且他们有序
        a[i]=b[i];
    }
    return cnt-l+1;//返回该轮尚存的人数
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&k,&m);
        for(int i=1;i<=(1<<k);i++){
            scanf("%d",&a[i].val);
            a[i].id=i;
        }
        int ans=merge(1,1<<k);
        bool fl=false;
        for(int i=1;i<=ans;i++){
            if(a[i].id==1){//找一找 1 号选手是否或者即可
                printf("Kotori\n");
                fl=true;break;
            }
        }
        if(!fl) printf("Yoshino\n");
    }
    return 0;
}