题解写到博客园了，懒得复制过来了了，放个链接
https://www.cnblogs.com/yxcblogs/p/18243276
推广一下自己记录的算法编程竞赛模板仓库
GitHub - yxc-s/programming-template: This repository contains C++ programming templates optimized for competitive coding challenges. It includes various algorithms, data structures, and utility functions to help streamline the coding process during competitions.