题解 | 2023河北工业大学ACM集训队初冬选拔赛

本次比赛的题目主要为河北工业大学校内集训队选拔服务，题目出锅主要在 D 题，D 题未卡掉特别暴力的 $\Theta\left(k^2(n q)\right)$ 的做法，系出题人和验题人没有尽到责任。即便如此，来年的校选拔赛还是会有一道终极奉献 II 的题目。

本题解会给 C++ 和 Python 的题解，则是因为我校有的专业的同学不学 C 只学 Python，考虑到在正式赛中可以巧用 Python 过题，所以提供 Python 题解，希望有心者能有所获。没有 Java 的题解是因为 Java 在算法竞赛的优势没有那么显著，而且出题人也不怎么会 Java。

A 暴力优化与玄学随机化

签到题，但还有一道更签到的题目。

模拟并记录最后一次 +20 的位置即可。

C++ 代码：

#include<cstdio>
int main()
{
    int n,ans=0,rec;scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int p;scanf("%d",&p);
        if(p==20)ans++,rec=i;
    }
    printf("%d %d\n",ans,rec);
    return 0;
}

Python 代码：

input()
cnt=rec=0
l=list(map(int,input().split()))
for i in range(len(l)):
    if l[i]==20:
        cnt+=1;rec=i
print(cnt,rec+1)

B 分披萨

结论：如果 Alex 想要的两块披萨挨着那么没有方案，如果不挨着一定有一种方案。

递归论证即可，如果 Alex 想要的披萨都不挨着，一定可以找到一个披萨拿走之后，剩下的披萨组成的环上 Alex 想要的披萨都不挨着。

反证：假设 Alex 想要的披萨都不挨着，拿走任意一块想要的披萨，都会使得剩下的想要拿的披萨挨着，那么此时 Alex 想要的披萨和不想要的披萨在环上是交错出现的，总的披萨块数是 Alex 想要的披萨的 $2$ 倍，与每次拿完披萨后总的披萨块数是 Alex 想要披萨的数目的 $3$ 倍这一事实相违背，所以假设不成立。

具体的实现要用到双链表，删除元素的时候得操心。

C++ 代码：

#include<cstdio>
int lst[3003],nxt[3003];bool get[3003];
int main()
{
    int n;scanf("%d",&n);
    for(int i=1,a;i<=n;i++)scanf("%d",&a),get[a]=1;
    for(int i=1;i<=3*n;i++)lst[i]=i-1,nxt[i]=i+1;lst[1]=3*n,nxt[3*n]=1;
    for(int i=1;i<=3*n;i++)if(get[lst[i]]&&get[i])return printf("No"),0;
    printf("Yes\n");
    for(int rest=n,p=1;rest>=1;rest--)
    {
        for(;!get[p]||rest>=3&&get[lst[lst[p]]]&&get[nxt[nxt[p]]];p=nxt[p]);
        printf("%d ",p);
        lst[nxt[nxt[p]]]=lst[lst[p]];
        nxt[lst[lst[p]]]=nxt[nxt[p]];
        p=nxt[nxt[p]];
    }
    return 0;
}

Python 代码：

lst, nxt, get = [0] * 3003, [0] * 3003, [False] * 3003
n = int(input())
l = map(int,input().split())
for i in l:
    get[i] = True
for i in range(1, 3*n+1):
    lst[i], nxt[i] = i-1, i+1
lst[1], nxt[3*n] = 3*n, 1
for i in range(1, 3*n+1):
    if get[lst[i]] and get[i]:
        print("No")
        exit()
print("Yes")
rest, p = n, 1
while rest >= 1:
    while not get[p] or rest >= 3 and get[lst[lst[p]]] and get[nxt[nxt[p]]]:
        p = nxt[p]
    print(p, end=' ')
    lst[nxt[nxt[p]]], nxt[lst[lst[p]]], p = lst[lst[p]], nxt[nxt[p]], nxt[nxt[p]]
    rest -= 1

C 一起来数 HEBUT

很简单的字符串匹配问题，五个字符串统计即可（见 Python 代码），也可以看成是字符串匹配的总长度（C++ 代码）。

C++ 代码

#include<cstdio>
char c[100002];const char s[]="HEBUT";
int main()
{
    int n,ans=0;scanf("%d%s",&n,c);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<=4&&i+j<n;j++)
            if(c[i+j]!=s[j])break;
            else ans++;
    }
    printf("%d",ans);
    return 0;
}

Python 代码

input()
si=input()
print(si.count("H")+si.count('HE')+si.count('HEB')+si.count('HEBU')+si.count('HEBUT'))

D 终极奉献 I

出题的时候想是一个二维差分/前缀和，后来发现二维差分/前缀和只能是一种非常优雅的写法，实际上可以通过本题的方式实在太多了，但是出题的时候确实没有想到要卡一下 $\Theta(k^2(n q))$ 写法，导致非常简朴的暴力算法跑得还不算慢（出题人睡不着觉了），不可否认的是，这个数据范围内即便不是暴力，也可以写出来一些奇奇怪怪的做法，例如：

压位赋值、多轮一维差分/前缀和计数、线段树/树状数组、分块写法……

值得一提的是，由于访问连续内存连续，朴素暴力的速度居然不慢，甚至可以通过奇奇怪怪的卡常手段通过本题，甚至于说数据范围的设定本就有点欠缺。

总之八仙过海各显神通吧……

下面是优雅的二维差分、前缀和做法：

C++ 代码：

#include<cstdio>
int a[1003][1003];
int main()
{
    int n,k,l;scanf("%d%d%d",&n,&k,&l);
    for(int i=0,x,y;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        a[x][y]++,a[x+k][y]--,a[x][y+k]--,a[x+k][y+k]++;
    }
    for(int i=1;i<=l;i++)
        for(int j=1;j<=l;j++)
            a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
    for(int i=1;i<=l;i++)
        for(int j=1;j<=l;j++)
            a[i][j]=!!a[i][j],
            a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
    int q;scanf("%d",&q);
    for(int i=0,x,y;i<q;i++)
    {
        scanf("%d%d",&x,&y);
        int occupied=a[x+k-1][y+k-1]-a[x+k-1][y-1]-a[x-1][y+k-1]+a[x-1][y-1];
        printf("%d\n",k*k-occupied);
    }
    return 0;
}

Python 代码（提交 pypy3）：

n,k,l=map(int,input().split())
a=[[0 for j in range(l+2)]for i in range(l+2)]
for i in range(n):
    x,y=map(int,input().split())
    a[x][y]+=1
    a[x+k][y]-=1
    a[x][y+k]-=1
    a[x+k][y+k]+=1
for i in range(1,l+1):
    for j in range(1,l+1):
        a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1]
for i in range(1,l+1):
    for j in range(1,l+1):
        a[i][j]=int(bool(a[i][j]))
        a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1]
q=int(input())
for i in range(q):
    x,y=map(int,input().split())
    occupied=a[x+k-1][y+k-1]-a[x+k-1][y-1]-a[x-1][y+k-1]+a[x-1][y-1]
    print(k*k-occupied)

E 折叠

此处给出树状数组维护差分序列和差分绝对值序列的方法：

考虑到区间加法只会使得两端差分值变化，维护区间修改时只需要在差分序列和差分绝对值序列上修改两下即可。

注意绝对值差分序列修改操作两端的增减情况，修改 $[l,r]$ 区间上的值，会使得 $|a_l-a_{l-1}|$ 和 $|a_{r 1}-a_r|$ 的值改变，可以将这两个值替换成修改后的值，也可以直接加上变化量，注意变化有增有减，注意写的时候不要把自己给搞晕（yōng）了。

除此之外，也可以用线段树区间修改来维护 $a_l$ 的值。

C++ 代码：

#include<cstdio>
#include<cmath>
struct BIT//Binary_Indexed_Tree
{
    void set_n(int n_){n=n_;}
    void add(int x,int c){while(x<=n)a[x]+=c,x+=x&-x;}
    int sum(int x){int s=0;while(x>0)s+=a[x],x-=x&-x;return s;}
    int sum(int x,int y){if(x>y)return 0;return sum(y)-sum(x-1);}
    int n,a[200001];
};
BIT diffa,absdiffa;
int oria[200001];
int main()
{
    int n,q;scanf("%d%d",&n,&q);
    diffa.set_n(n),absdiffa.set_n(n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",oria+i);
        diffa.add(i,oria[i]-oria[i-1]);
        absdiffa.add(i,abs(oria[i]-oria[i-1]));
    }
    for(int i=1;i<=q;i++)
    {
        int opt,l,r;scanf("%d%d%d",&opt,&l,&r);
        if(opt==1)printf("%d\n",diffa.sum(l)+absdiffa.sum(l+1,r));
        else if(opt==2)
        {
            int all=diffa.sum(l-1),al=diffa.sum(l);
            int ar=diffa.sum(r),arr=diffa.sum(r+1);
            if(all<=al)absdiffa.add(l,1);else absdiffa.add(l,-1);
            if(ar<arr)absdiffa.add(r+1,-1);else absdiffa.add(r+1,1);
            diffa.add(l,1),diffa.add(r+1,-1);
        }
    }
    return 0;
}

Python 代码（PyPy3 提交）：

class BIT:
    def __init__(self,n):
        self.a=[0 for i in range(n+1)]
    def add(self,x,c):
        while x<=n:
            self.a[x]+=c
            x+=x&-x
    def sum(self,x):
        s=0
        while x>0:
            s+=self.a[x]
            x-=x&-x
        return s
    def sum_range(self,x,y):
        if x>y:return 0
        return self.sum(y)-self.sum(x-1)

n,q=map(int,input().split())
diffa=BIT(n)
absdiffa=BIT(n)
oria=[0]+list(map(int,input().split()))

for i in range(1,n+1):
    diffa.add(i,oria[i]-oria[i-1])
    absdiffa.add(i,abs(oria[i]-oria[i-1]))

for i in range(q):
    opt,l,r=map(int,input().split())
    if opt==1:
        print(diffa.sum(l)+absdiffa.sum_range(l+1,r))
    else:  # opt == 2
        al1=diffa.sum(l-1)
        al=diffa.sum(l)
        ar=diffa.sum(r)
        ar1=diffa.sum(r+1)
        if al1<=al:absdiffa.add(l,1)
        else:absdiffa.add(l,-1)
        if ar<ar1:absdiffa.add(r+1,-1)
        else:absdiffa.add(r+1,1)
        diffa.add(l,1)
        diffa.add(r+1,-1)

F 半夜起来写高数会不会做噩梦？

推式子题，出题人大发慈悲地把推式子的公式给你了。你只需再额外掌握等差数列求和公式即可。

$\sum\limits_{i=1}^n4iH(i)$

$=4\left(\sum\limits_{i=1}^ni\right)H(n)-4\sum\limits_{i=1}^{n-1}\left(\sum\limits_{j=1}^ij\right)\dfrac{1}{i}$

$=4\dfrac{n(n 1)}{2}H(n)-4\sum\limits_{i=1}^{n-1}\dfrac{i(i 1)}{2}\dfrac{1}{i 1}$

$=2n(n 1)H(n)-2\sum\limits_{i=1}^{n-1}i$

$=2n(n 1)H(n)-n(n-1)$

最后注意模法不要用错，注意乘法不要溢出。

注：只当 $n=998244353-1$ 时， $H(n)=0$ ，此时 C/C++ 等需要考虑 $mod$ 保证结果不会得出负数。另外，Python 可以直接使用 %mod 的写法，这是因为 Python 取模的结果和模数同号而不是和被模数同号。

C++ 代码：

#include<cstdio>
const int mod=998244353;
int main()
{
    int n,H;scanf("%d%d",&n,&H);
    printf("%lld",(2ll*n*(n+1)%mod*H%mod+mod-1ll*n*(n-1)%mod)%mod);
    return 0;
}

Python 代码：

n,H=map(int,input().split())
mod=998244353
print((2*n*(n+1)*H-n*(n-1))%mod)

G 漂流瓶（简单版）

容易想到直接用并查集就可以维护本题，本题解不再赘述。不会并查集的同学百度一下。

观察题目中，所有人组团的关系图是一个有向多环图，可以使用递归算法 dfs/bfs 等跑一遍记录最大环长。本题解也不赘述具体做法，不会 dfs/bfs 的同学也百度一下。

本题解使用迭代求解。

C++ 代码：

#include<cstdio>
#include<vector>
int main()
{
    int n;scanf("%d",&n);int ans=0;
    std::vector<int> a(n+1);std::vector<bool> vis(n+1);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)if(!vis[i])
    {
        vis[i]=1;int cnt=1;
        for(int now=i;!vis[a[now]];now=a[now])
            vis[a[now]]=1,cnt++;
        if(cnt>ans)ans=cnt;
    }
    printf("%d",ans);
    return 0;
}

Python 代码：

n = int(input())
ans = 0
a = [0] * (n+1)
vis = [False] * (n+1)
a=[None]+list(map(int,input().split()))
for i in range(1, n+1):
    if not vis[i]:
        vis[i] = True
        cnt = 1
        now = a[i]
        while not vis[now]:
            vis[now] = True
            cnt += 1
            now = a[now]
        if cnt > ans:
            ans = cnt
print(ans)

H 漂流瓶（困难版）

这是一道错排计数+期望 dp 的题目，也可以用排列计数解决。

首先考虑错排数目 $\mathrm{cnt}$ 。假设已知 $\mathrm{cnt}_{i-2},\mathrm{cnt}_{i-1}$ ，那么可以在已有的错排情况中插入一个新的结点（同学），有两种情况，一种是不创建新的环（小组），另一种则是创建新的环（小组）。在已有环中插入一个新的结点的情况数为 $(i-1)\mathrm{cnt}_{i-1}$ ，即把这个结点加入 $i-1$ 个结点后面都形成了一个新的情况；新建一个环的情况数为 $(i-1)\mathrm{cnt}_{i-2}$ ，即假设 $i-2$ 个结点都在环内，有 $1$ 个结点游离在外（游离结点有 $i-1$ 种选择），让新的结点和这个游离的结点组队。

得到错排方案数目公式： $\mathrm{cnt}_i=(i-1)(\mathrm{cnt}_{i-1} \mathrm{cnt}_{i-2})$ ，且 $\mathrm{cnt}_1=0,\mathrm{cnt}_2=1$ （事实上还不妨认为 $\mathrm{cnt}_0=1$ ）。

其次，我们继续考察得到错排公式的过程，进行期望 dp。容易发现对于所有结点来说，其所在的期望环长都是一样的，设每个结点所在环的期望环长为 $\mathrm{dp}$ 。假设已知 $\mathrm{dp}_{i-1},\mathrm{dp}_{i-2}$ ，仍然考虑两种情况，不建新环和建新环。如果不建新环，那么相当于插入一个结点后面，可以继承这个结点所在环的期望环长，贡献是 $\dfrac{(i-1)\mathrm{cnt}_{i-1}(\mathrm{dp}_{i-1} 1)}{\mathrm{cnt}_i},$ 如果考虑建新环的话，一定会得到一个长度为 $2$ 的环，显然贡献是 $\dfrac{(i-1)\mathrm{cnt}_{i-2}\times 2}{\mathrm{cnt}_i}.$

最后得到期望 dp 的转移方程为 $\mathrm{dp}_i=\dfrac{(i-1)\left[\mathrm{cnt}_{i-1}(\mathrm{dp}_{i-1} 1) \mathrm{cnt}_{i-2}\times 2\right]}{\mathrm{cnt}_i},$ 初始情况 $\mathrm{dp}_1=0,\mathrm{dp}_2=2$ 。

也可以考虑解出来所有情况下 $1$ 号结点所在环长的总和，然后再除以总的错排方案数即可。

枚举 1 号结点所在的环长为 $i(i\geqslant 2)$ ，考虑构造方案，先从其他 $n-1$ 个结点中挑出 $i-1$ 个结点的排列接到 $1$ 号结点后面，然后首尾相连组成环，方案数为 $A_{n-1}^{i-1}=\dfrac{(n-1)!}{(n-i)!}$ ，再剩下的结点错排即可，方案数为 $\mathrm{cnt}_{n-i}$ ，记得再乘上环长 $i$ 。

这样结果就是 $ans=\dfrac{\sum\limits_{i=2}^n\dfrac{(n-1)!}{(n-i)!}\mathrm{cnt}_{n-i}\times i}{\mathrm{cnt}_n}$

可以预处理阶乘，也可以直接递推。如果你闲得 $\color{grey}\tiny{\overline{\text{构建文明网络}}}$ 疼的话，也可以用 NTT 把上面的式子给卷起来。

C++ 期望 dp 代码：

#include<cstdio>
#include<vector>
using ll=long long;
const ll mod=998244353;
ll fp(ll a,ll b)
{
    ll ans=1;a%=mod;
    while(b)
    {
        if(b&1)ans=a*ans%mod;
        a=a*a%mod;b>>=1;
    }
    return ans;
}
#define inv(xx) fp(xx,mod-2)
int main()
{
    int n;scanf("%d",&n);
    std::vector<ll> cnt(n+1),dp(n+1);
    cnt[1]=0,cnt[2]=1;dp[1]=0,dp[2]=2;
    for(int i=3;i<=n;i++)
    {
        cnt[i]=(i-1)*(cnt[i-1]+cnt[i-2])%mod;
        dp[i]=(i-1)*(cnt[i-1]*(dp[i-1]+1)%mod+cnt[i-2]*2)%mod*inv(cnt[i])%mod;
    }
    printf("%d",dp[n]);
    return 0;
}

C++ 排列计数代码：

#include<cstdio>
#include<vector>
using ll=long long;
const ll mod=998244353;
ll fp(ll a,ll b)
{
    ll ans=1;a%=mod;
    while(b)
    {
        if(b&1)ans=a*ans%mod;
        a=a*a%mod;b>>=1;
    }
    return ans;
}
#define inv(xx) fp(xx,mod-2)
int main()
{
    int n;scanf("%d",&n);
    std::vector<ll> cnt(n+1);
    cnt[0]=1,cnt[1]=0;
    ll factn_1=1;
    for(int i=2;i<=n;i++)
    {
        cnt[i]=(i-1)*(cnt[i-1]+cnt[i-2])%mod;
        factn_1=factn_1*(i-1)%mod;
    }
    ll ans=0,invfactn_i=inv(factn_1);
    for(int i=2;i<=n;i++)
    {
        invfactn_i=invfactn_i*(n-i+1)%mod;
        ans=(ans+cnt[n-i]*invfactn_i%mod*i)%mod;
    }
    printf("%lld",factn_1*ans%mod*inv(cnt[n])%mod);
    return 0;
}

Python 期望 dp 代码（提交 pypy3）：

n=int(input())
cnt=[0 for i in range(n+1)]
dp=[0 for i in range(n+1)]
cnt[2]=1;dp[2]=2;
mod=998244353
for i in range(3,n+1):
    cnt[i]=(i-1)*(cnt[i-1]+cnt[i-2])%mod
    dp[i]=(i-1)*(cnt[i-1]*(dp[i-1]+1)+cnt[i-2]*2)*pow(cnt[i],mod-2,mod)%mod
print(dp[n])

I 逆序对数

时间卡得不紧，数据量较小，一些复杂度不是非常优秀的算法也能过。这道题实则出得不好，就不放标准程序了。

J 小黑屋的故事

看输出格式，输出 I'm an eye-opener for it.，如果你还在看故事的话你已经落后了，不会打比赛的扔出去。

这一个字符串有三个标点符号，如果手打请打对。能准确地复制粘贴是一种能力。

语言选择 PHP，直接把代码粘贴进框子里，点一下提交就过了。比赛的时候一度 A 题比 J 题过的人还多，实则不应该，学会看榜和快速看题也是一种能力。

题面来源：https://www.luogu.com.cn/discuss/673596

PHP 提交代码：

I'm an eye-opener for it.

K 集天地之灵气，吸日月之精华

故事背景参考《西游记》。

数论题，有一个结论 $k_1d_1 k_2d_2=y$ ，其中 $k_1,k_2\in\mathbb Z,d_1,d_2\in\mathbb N$ ，则 $y$ 的所有可能得取值可以表示成 $y=k\gcd(d_1,d_2),k\in\mathbb Z$ 。具体来源可搜索“裴蜀定理/贝祖定理”。

然后需要求出 $\min|x-y|=\min|x-k\gcd(d_1,d_2)|$ ，显然取最小值时的 $y$ 不是小于等于 $x$ 的最大值，就是大于 $x$ 的最小值。

如何求出小于等于 $x$ 的最大的 $y$ 值呢？

考虑到这时 $k$ 要取到 $\left\lfloor\dfrac{x}{\gcd(d_1,d_2)}\right\rfloor$ ，所以 $y_{\tiny{\leqslant x}}=\gcd(d_1,d_2)\left\lfloor\dfrac{x}{\gcd(d_1,d_2)}\right\rfloor$

显然大于 $x$ 的最小的 $y$ 值是 $y_{\tiny{> x}}=\gcd(d_1,d_2)\left[1 \left\lfloor\dfrac{x}{\gcd(d_1,d_2)}\right\rfloor\right]$ 。

找到这两个解取最小值即可。

C++ 代码：

#include<cmath>
#include<cstdio>
#include<algorithm>
int mindis(int a,int b,int x)
{
    return abs(a-x)<=abs(b-x)?a:b;
}
int main()
{
    int d1,d2,x;scanf("%d%d%d",&d1,&d2,&x);
    int g=std::__gcd(d1,d2);//或者使用 C++20 numeric 库的 std::gcd
    printf("%d",mindis(x/g*g,(x/g+1)*g,x));
    return 0;
}

Python 代码：

import math  
def mindis(a, b, x):
    return a if abs(a - x) <= abs(b - x) else b
d1, d2, x = map(int, input().split())
g = math.gcd(d1, d2)
print(mindis(x // g * g, (x // g + 1) * g, x))

L 滑动验证

本题考察计算几何的一些概念，以及断环为链的技巧。似乎是因为题目要求不太寻常，所以没人写吗？

将原图碎片和阴影碎片一一比对，只要它们顶点一一对应且都相差同一个距离，那么就能匹配上。考虑枚举阴影碎片上的一个点作为起点，让它和原图碎片上的起点开始匹配，如果从任何点开始和原图碎片上的点序列比较都有差距的话，就是匹配不上。

C++ 代码：

#include<cstdio>
#include<utility>
#define x first
#define y second
int main()
{
    int n,k1;scanf("%d%d",&n,&k1);
    std::pair<int,int> P1[11],Pt[20];
    for(int i=1;i<=k1;i++)scanf("%d%d",&P1[i].x,&P1[i].y);
    for(int i=1;i<=n;i++)
    {
        int kt;scanf("%d",&kt);
        for(int j=1;j<=kt;j++)scanf("%d%d",&Pt[j].x,&Pt[j].y);
        if(kt!=k1)continue;
        for(int j=kt+1;j<2*kt;j++)Pt[j]=Pt[j-kt];
        for(int b=1;b<=kt;b++)//枚举阴影起点
        {
            bool flag=true;//true 匹配，否则不匹配
            int d=Pt[b].x-P1[1].x;
            for(int j1=1,jt=b;j1<=k1;j1++,jt++)
            {
                if(P1[j1].x+d!=Pt[jt].x||P1[j1].y!=Pt[jt].y)
                {
                    flag=false;
                    break;
                }
            }
            if(flag)return printf("%d",d),0;
        }
    }
    return 0;
}

Python 代码：

n=int(input())
_P1=list(map(int,input().split()))
k1=_P1[0]
P1=[(_P1[2*i+1],_P1[2*i+2])for i in range(k1)]
for _ in range(n):
    _Pt=list(map(int,input().split()))
    kt=_Pt[0]
    if k1!=kt:continue
    Pt=[(_Pt[2*i+1],_Pt[2*i+2])for i in range(kt)]
    Pt+=Pt
    for b in range(kt):
        flag=True
        d=Pt[b][0]-P1[0][0]
        for i,j in zip(range(k1),range(b,b+k1)):
            if Pt[j][0]-P1[i][0]!=d or Pt[j][1]!=P1[i][1]:
                flag=False
        if flag:
            print(d)
            exit(0)

M CF == 穿越火线

可以用结构体排序（类）的方式进行排序比较。当然也可以将点对 $(K,M)$ 映射到数轴上，使得点对之间的大小关系可以通过对应的数轴上的值的大小来判断，例如一个合理的映射是 $2001K M$ 。

结构体（类）排序的方式比较模板化，背住即可。事实上，本题要求是结构体（类）双关键字排序，而且比较顺序是字典序，所以可以使用 std::pair 代替。注意排序的时候用现成的排序函数即可，最好不要手写，特别是不要写冒泡、插入等 $O(n^2)$ 的排序算法。

C++ std::pair 为基础的代码：

#include<cstdio>
#include<utility>
#include<algorithm>
#include<functional>
std::pair<int,int>x[100001];
int main()
{
    int n;scanf("%d",&n);n--;
    for(int i=0;i<n;i++)scanf("%d%d",&x[i].first,&x[i].second);
    std::sort(x,x+n,std::greater<std::pair<int,int>>());
    int q;scanf("%d",&q);
    for(int i=0;i<q;i++)
    {
        int k,m,r;scanf("%d%d%d",&k,&m,&r);r--;
        if(std::make_pair(k,m)>=x[r])puts("YES");
        else puts("NO");
    }
    return 0;
}

C++ 结构体（类）排序：

#include<cstdio>
#include<algorithm>
struct player
{
    int k,m;
    void input(){scanf("%d%d",&k,&m);}
    bool operator<(const player&o)const
    {return k==o.k?m>o.m:k>o.k;}
    bool operator<=(const player&o)const
    {return k==o.k&&m==o.m?true:*this<o;}
}x[100001];
int main()
{
    int n;scanf("%d",&n);n--;
    for(int i=0;i<n;i++)x[i].input();std::sort(x,x+n);
    int q;scanf("%d",&q);
    for(int i=0;i<q;i++)
    {
        int k,m,r;scanf("%d%d%d",&k,&m,&r);r--;
        if(player({k,m})<=x[r])puts("YES");
        else puts("NO");
    }
    return 0;
}

Python 代码：

n=int(input())-1
l=[tuple(map(int,input().split()))for i in range(n)]+[(0,0)]
#+[(0,0)] 是考虑到会出现 X == N 的情况，这时候数组会越界
l.sort(reverse=True)
q=int(input())
for _ in range(q):
    k,m,x=map(int,input().split())
    print("YES" if (k,m)>=l[x-1] else "NO")