在高并发网络编程中，如何高效地处理大量连接是一个核心问题。Linux 提供的 epoll 机制，正是解决这一问题的利器。本文将深入剖析 epoll 的设计原理、核心 API 以及触发模式的区别，帮助你理解为什么 epoll 能够支撑起万级并发，也就是著名的 C10K 问题。一、为什么需要 epoll？—— select/poll 的性能瓶颈在 epoll 出现之前，Linux 主要使用 select 和 poll 来实现 I/O 多路复用。然而，当需要处理大量（$N$ 个）连接时，它们存在两个致命的性能瓶颈：$O(N)$ 的遍历开销每次调用 select 或 poll 时，内核都必须遍历检查所有 $N$ 个文件描述符（FD），以找出哪些是就绪的（可读/可写）。即使只有 1 个连接有数据到达，内核也要检查全部 $N$ 个 FD，这是极大的性能浪费。$O(N)$ 的拷贝开销每次调用都需要将完整的 $N$ 个 FD 列表从用户空间拷贝到内核空间。当连接数达到数万时，这种频繁的内存拷贝会成为严重的性能负担。二、epoll 的解决方案：持久化管理与高效数据结构epoll 的设计理念很简单但很高明：既然 FD 列表变化不频繁，为什么每次都要重新传递呢？于是，epoll 针对这两个问题分别设计了解决方案：解决拷贝开销：持久化注册核心思想：程序只需在内核中注册一次感兴趣的 FD 列表，之后调用 epoll_wait 时不需要再传递整个列表。epoll 通过 epoll_create 在内核中创建一个持久化的实例，所有被监听的 FD 都存储在这个实例中。应用程序通过 epoll_ctl 增删改 FD，而不是每次调用时都传递完整列表。这种"注册一次，长期有效"的设计，彻底消除了 $O(N)$ 的拷贝开销。解决遍历开销：红黑树 + 就绪列表遍历开销体现在两个地方，epoll 分别用两种数据结构来解决：红黑树：高效管理 FD当调用 epoll_ctl 增删改 FD 时，需要快速定位目标 FD。epoll 使用红黑树来存储所有被监听的 FD，使得每次操作的时间复杂度稳定在 $O(\log N)$，可能你会好奇为什么不用哈希表。固然，从纯粹的算法时间复杂度来看，哈希表的查找/插入/删除平均复杂度是 $O(1)$，确实要比红黑树的 $O(\log N)$ 要快。但在内核场景下，理论最快并不等于工程最优，就好像贪心得到的是局部最优解一般。下面从几个维度告诉你为什么会选择红黑树动态扩容成本哈希表的动态扩容的成本是它在内核场景下最大的劣势，哈希表一般基于数组（Bucket），我们假设连接数从 10K 增加至 100K 甚至 1000K 时，哈希表就不可避免地需要扩容 (Rehash)。哈希表的扩容需要申请一块更大的内存，然后把旧表里的所有数据重新计算 Hash 并移动过去，这是一个 $O(N)$ 的操作。在内核态中，这种瞬间的大量计算和内存操作会造成剧烈的系统抖动 (Jitter)，导致那一瞬间的 epoll_ctl 的响应时间急剧增加，这是不可接受的。而红黑树则是动态生长的，每插入一个节点，只需要少量的指针操作，它没有扩容的概念，性能曲线非常平滑，而不会像哈希表在某个时刻突然 Rehash 造成卡顿。内存利用率epoll 需要适应各种规模的场景（从监听几个 FD 到监听几万个 FD）。哈希表为了减少哈希冲突以尽可能维持 $O(1)$ 的性能，通常会预分配比实际数据量大的内存。这就会产生一些问题：如果预分配得太大，对于只有几个连接的情况会造成巨大的内存浪费。如果预分配太小，又会频繁触发扩容。内核无法预测用户会创建多少个连接，因此很难预分配一个完美的初始大小。而红黑树则是用多少拿多少，它不需要预分配连续的内存，因此对内存的利用率可以说是100%的。确定性内核开发非常看重可预测性 (Predictability)。哈希表的时间复杂度虽然平均是 $O(1)$，但在最坏情况下会退化成链表 $O(N)$，虽然可以通过良好的 Hash 函数缓解，但风险依然存在。而红黑树的时间复杂度有着严谨的数学证明，无论数据如何分布，查找、插入、删除永远都稳定在 $O(\log N)$。对于内核而言，“稳定的慢”往往比“不稳定的快”要优。💡 小知识 $O(\log N)$ 其实并不慢，假设数据量为 100 万，$\log_2(10^6) \approx 20$，单次操作也仅仅需要进行约 20 次比对。总结特性哈希表 (Hash Table)红黑树 (RB-Tree)Epoll 的选择平均查找速度$O(1)$$O(\log N)$红黑树够用了最坏查找速度$O(N)$（冲突时）$O(\log N)$红黑树胜内存开销高 (预分配 bucket，存在内存空洞)低 (按需分配)红黑树胜扩容成本极高 (Rehash 抖动)无 (平滑增长)红黑树胜数据量适应性低 (需预估大小)高 (自适应)红黑树胜虽然哈希表在理想时间优于红黑树，但红黑树在省内存、无扩容抖动、性能稳定这三点上更符合操作系统内核对资源管理的需求。就绪列表：$O(K)$ 获取就绪事件红黑树解决了 FD 管理的效率问题，但还有一个问题：当调用 epoll_wait 时，如何快速找出哪些 FD 已经就绪？epoll_wait 的高性能秘密就在于就绪列表。epoll 实例在内核中除了用红黑树来存储所有注册的 FD 外，还有一个链表（或链队），专门用来存放已就绪的 FD。我们称之为就绪列表。当内核发现一个被监听的 FD 上有 I/O 事件发生时（比如数据到达），它不会等到应用程序调用 epoll_wait，而是会通过红黑树定位该 FD，并将其事件信息追加到就绪列表。所以，当应用程序调用 epoll_wait 时，它要做的全部工作就是：检查并取出就绪列表中的元素。效率对比select/poll: 必须遍历全部（$N$ 个）FD 才能找到 K 个就绪的，所以它的时间复杂度是 $O(N)$。epoll: 直接从就绪列表就能取出 K 个就绪的，所以它的时间复杂度是 $O(K)$（其中 $K \ll N$）。这就是 epoll 能实现万级并发，将时间复杂度从线性 $O(N)$ 降到与就绪事件数成正比的 $O(K)$（$K \ll N$，低就绪率时近似常数）的关键。三、epoll 的三大核心 API了解了设计原理和数据结构后，接下来我们来看看 epoll 提供的三个核心 API，它们是应用程序与内核交互的桥梁。epoll_create：创建 epoll 实例epoll_create 是实现持久化的第一步，也是最关键的一步int epoll_create1(int flags) // 新接口，传入 flags，用于在创建时设置文件描述符的属性。 int epoll_create(int size); // 旧接口，size 在现代内核中已被忽略，但必须大于 0epoll_create 的作用，是在 Linux 内核中创建一个 epoll 实例（即持久化的 红黑树 和 就绪列表），并返回一个特殊的 epfd (epoll 文件描述符)。这个 epfd 就是应用程序和内核中的这个 epoll 实例交流的唯一凭证。现在，实例已经创建好了，我们该如何让内核知道我们想要监听的客户端 FD 呢？epoll_ctl：管理监听的 FD有了 epoll 实例后，我们需要告诉内核：我们想监听哪些 FD，以及关心它们的什么事件。这就是 epoll_ctl 的职责。int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);epoll_ctl 提供三种操作来管理 FD 集合：操作常量说明增EPOLL_CTL_ADD将一个新的 FD 添加到红黑树中进行监听删EPOLL_CTL_DEL从红黑树中移除不再需要监听的 FD改EPOLL_CTL_MOD修改某个 FD 监听的事件类型（如从只监听可读改为同时监听可读和可写）由于 FD 存储在红黑树中，每次增删改操作的时间复杂度都是 $O(\log N)$，非常高效。epoll_wait：等待事件发生int epoll_wait(int epfd, struct epoll_event *events, int maxevents, int timeout);epoll_wait 负责等待事件发生，当有 FD 就绪时，它会从就绪列表中取出事件信息，填充到 events 数组中，并返回就绪的 FD 数量。参数说明：epfd：epoll 实例的文件描述符events：用于接收就绪事件的数组maxevents：数组的最大容量。💡 提示：如果就绪的 FD 数量超过 maxevents，epoll_wait 会分批返回。未返回的 FD 会保留在就绪列表中，在下一次调用 epoll_wait 时继续返回。这一点 LT 和 ET 模式是一样的。区别在于：LT：如果你处理了 FD 但没读完数据，下次还会返回。ET：如果你处理了 FD 但没读完数据，下次不会返回（除非有新数据到达）。至此，epoll 的基础知识已经讲完了，现在进入触发模式的区别四、触发模式：LT vs ETepoll 提供了两种事件通知模式：Level-Triggered (LT)：水平触发Edge-Triggered (ET)：边缘触发我们可以将它类比为数字电路中的触发方式：LT 就像高电平触发，只要 FD 处于就绪状态 (高电平)，epoll_wait 就会持续地通知。ET 就像上升沿触发，只有 FD 的状态从非就绪变为就绪那一刻 (事件的发生，上升沿) 才会通知一次。LT 的编程通常相对更简单更安全，如果程序在这次只读了部分数据，在下一次调用 epoll_wait 时仍会继续通知你，直到把所有的数据读完。而 ET 的编程虽然更复杂，但效率更高。因为它只会通知你一次，你需要确保在这次通知中把所有的数据都读完。如果还有数据没处理，epoll 也不会再通知你，直到下一个事件 (上升沿) 再次发生。效率上，由于 ET 模式减少了重复通知带来的系统调用次数，因此更适合进行高性能的开发。这里提供一个更形象的流程：我们假设一个客户端连接一次性发来了 2000 字节数据，但你的接收缓冲区只有 1000 字节。模式第一次 epoll_wait 返回应用程序操作第二次 epoll_wait 返回LT (水平触发)✅ 通知 FD 可读读取 1000 字节，还剩 1000 字节。✅继续通知（FD 仍处于“可读”状态）ET (边缘触发)✅ 通知 FD 可读读取 1000 字节，还剩 1000 字节。❌不会通知，因为 FD 状态没有再次从“非就绪”变为“就绪”。你需要自己循环读取直到返回 EAGAIN/EWOULDBLOCK (缓冲区空了)。⚠️ 注意：使用 ET 模式时，通常需要将 FD 设置为非阻塞模式，并在循环中读取直到返回 EAGAIN。否则剩余数据虽然仍在内核缓冲区，但不会再次触发事件，导致应用可能误以为“没有数据”。五、最小LT和ET实现为了更直观地理解这两种模式的区别，下面提供了最小化的代码实现示例。LT 模式LT 模式是默认模式，代码编写相对简单。即使一次没有读完所有数据，内核也会在下一次 epoll_wait 时继续通知。阻塞 I/O 下 read 不会返回 EAGAIN；但如果你把连接也设成非阻塞，记得在出错分支里特殊判断 EAGAIN/EWOULDBLOCK，避免重复打印错误。#include <sys/epoll.h> #include <sys/socket.h> #include <netinet/in.h> #include <unistd.h> #include <fcntl.h> #include <stdio.h> #include <arpa/inet.h> // inet_ntoa #define MAX_EVENTS 10 // 每次 epoll_wait 最多返回的事件数 // 设置文件描述符为非阻塞 void setnonblocking(int sock) { int opts = fcntl(sock, F_GETFL); fcntl(sock, F_SETFL, opts | O_NONBLOCK); } int main() { struct epoll_event ev, events[MAX_EVENTS]; // 创建监听 Socket (TCP, IPv4) int listen_sock = socket(AF_INET, SOCK_STREAM, 0); if (listen_sock == -1) { perror("socket"); return 1; } // 配置监听 struct sockaddr_in addr; addr.sin_family = AF_INET; // IPv4 addr.sin_addr.s_addr = INADDR_ANY; // 监听所有网卡的 IP addr.sin_port = htons(8080); // 监听端口 (htons: 主机字节序转网络字节序) if (bind(listen_sock, (struct sockaddr*)&addr, sizeof(addr)) == -1) { perror("bind"); return 1; } if (listen(listen_sock, SOMAXCONN) == -1) { perror("listen"); return 1; } int epfd = epoll_create1(0); if (epfd == -1) { perror("epoll_create1"); return 1; } // 添加监听，默认是 LT 模式 ev.events = EPOLLIN; ev.data.fd = listen_sock; if (epoll_ctl(epfd, EPOLL_CTL_ADD, listen_sock, &ev) == -1) { perror("epoll_ctl: listen_sock"); return 1; } while (1) { int nfds = epoll_wait(epfd, events, MAX_EVENTS, -1); if (nfds == -1) { perror("epoll_wait"); return 1; } for (int i = 0; i < nfds; ++i) { if (events[i].data.fd == listen_sock) { // 有新连接 struct sockaddr_in addr; socklen_t addrlen = sizeof(addr); int conn_sock = accept(listen_sock, (struct sockaddr *) &addr, &addrlen); if (conn_sock == -1) { perror("accept"); continue; } printf("New connection from %s:%d\n", inet_ntoa(addr.sin_addr), ntohs(addr.sin_port)); // 设置非阻塞 (虽然 LT 模式下阻塞 I/O 也可以，但推荐非阻塞) setnonblocking(conn_sock); ev.events = EPOLLIN; ev.data.fd = conn_sock; // 把新连接添加进 epoll 监听事件 if (epoll_ctl(epfd, EPOLL_CTL_ADD, conn_sock, &ev) == -1) { perror("epoll_ctl: conn_sock"); close(conn_sock); } } else { // 处理数据 char buf[1024]; // LT 模式下，这里可以只读一次。 // 如果缓冲区还有数据，下一次 epoll_wait 依然会返回该 FD int n = read(events[i].data.fd, buf, sizeof(buf)); if (n > 0) { // 处理 buf... } else if (n == 0) { close(events[i].data.fd); } else { if (errno == EAGAIN || errno == EWOULDBLOCK) { // 非阻塞且本次已无数据，等待下一次通知 continue; } perror("read"); } } } } return 0; }ET 模式ET 模式需要显式指定 EPOLLET，并且必须配合非阻塞 I/O (Non-blocking I/O) 使用。在收到通知后，必须循环读取直到缓冲区为空（返回 EAGAIN）。#include <sys/epoll.h> #include <sys/socket.h> #include <netinet/in.h> #include <unistd.h> #include <fcntl.h> #include <stdio.h> #include <errno.h> #include <arpa/inet.h> // inet_ntoa #define MAX_EVENTS 10 // 每次 epoll_wait 最多返回的事件数 // 设置文件描述符为非阻塞 void setnonblocking(int sock) { int opts = fcntl(sock, F_GETFL); fcntl(sock, F_SETFL, opts | O_NONBLOCK); } int main() { struct epoll_event ev, events[MAX_EVENTS]; // 创建监听 Socket (TCP, IPv4) int listen_sock = socket(AF_INET, SOCK_STREAM, 0); if (listen_sock == -1) { perror("socket"); return 1; } // 配置监听 struct sockaddr_in addr; addr.sin_family = AF_INET; // IPv4 addr.sin_addr.s_addr = INADDR_ANY; // 监听所有网卡的 IP addr.sin_port = htons(8080); // 监听端口 (htons: 主机字节序转网络字节序) if (bind(listen_sock, (struct sockaddr*)&addr, sizeof(addr)) == -1) { perror("bind"); return 1; } if (listen(listen_sock, SOMAXCONN) == -1) { perror("listen"); return 1; } // ET 模式下，listen_sock 设置为非阻塞 setnonblocking(listen_sock); int epfd = epoll_create1(0); if (epfd == -1) { perror("epoll_create1"); return 1; } // 添加监听，显式指定 EPOLLET ev.events = EPOLLIN | EPOLLET; ev.data.fd = listen_sock; if (epoll_ctl(epfd, EPOLL_CTL_ADD, listen_sock, &ev) == -1) { perror("epoll_ctl: listen_sock"); return 1; } while (true) { int nfds = epoll_wait(epfd, events, MAX_EVENTS, -1); if (nfds == -1) { perror("epoll_wait"); return 1; } for (int i = 0; i < nfds; ++i) { if (events[i].data.fd == listen_sock) { // 有新连接 while (true) { // ET 模式下处理新连接，必须循环 accept 直到 EAGAIN // 因为可能同时有多个连接到达，但只触发一次事件 struct sockaddr_in addr; socklen_t addrlen = sizeof(addr); int conn_sock = accept(listen_sock, (struct sockaddr *) &addr, &addrlen); if (conn_sock == -1) { if (errno == EAGAIN || errno == EWOULDBLOCK) { // 所有新连接处理完了 break; } else { // 真出错了 perror("accept"); break; } } printf("New connection from %s:%d\n", inet_ntoa(addr.sin_addr), ntohs(addr.sin_port)); // 设置非阻塞 setnonblocking(conn_sock); ev.events = EPOLLIN | EPOLLET; //监听可读 + 边缘触发 ev.data.fd = conn_sock; // 把新连接添加进 epoll 监听事件 if (epoll_ctl(epfd, EPOLL_CTL_ADD, conn_sock, &ev) == -1) { perror("epoll_ctl: conn_sock"); close(conn_sock); } } } else { // ET 模式下，必须循环读取直到 EAGAIN while (true) { char buf[1024]; int n = read(events[i].data.fd, buf, sizeof(buf)); if (n > 0) { // 处理数据... } else if (n == 0) { close(events[i].data.fd); break; } else { if (errno == EAGAIN || errno == EWOULDBLOCK) { // 数据读取完了 break; } else { // 出错了 perror("read"); break; } } } } } } return 0; }总结LT (Level Triggered): 编程简单，不易出错，支持阻塞和非阻塞 I/O。ET (Edge Triggered): 编程复杂，必须使用非阻塞 I/O 并一次性读到 EAGAIN；在高并发场景能有效减少系统调用，更适合高性能开发。
模板只有DS和一点点数学，因为DP和数学感觉没必要写在模板里(其实主要是懒OωO)点击查看/下载: GuWolf的模板.pdfPS: SAM(后缀自动机)是AI写的,要比赛了来不及~杂项快读普通快读inline int read() { int x = 0, f = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * f; }优化快读char *p1, *p2, buf[100000]; #define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++) int read() { int x = 0, f = 1; char ch = nc(); while (ch < 48 || ch > 57) { if (ch == '-') f = -1; ch = nc(); } while (ch >= 48 && ch <= 57) x = x * 10 + ch - 48, ch = nc(); return x * f; }快写void write(int x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); }超级快读写(待测试)namespace __Coel_FastIO { const int SIZE = 1 << 20; static char buf_r[SIZE], *p1 = buf_r, *p2 = buf_r; static char buf_w[SIZE], *p3 = buf_w, *p4 = buf_w + SIZE; static std::streambuf *inbuf = std::cin.rdbuf(), *outbuf = std::cout.rdbuf(); //流初始化 inline static void gc(char &ch) { //这里三目运算符的效率略高一些 ch = p1 == p2 && (p2 = (p1 = buf_r) + inbuf->sgetn(buf_r, SIZE), p1 == p2) ? EOF : *p1++; /*逻辑：先判断有没有读完一个缓存，如果缓存空了就继续往下读， 否则用 sgetn 读入一个缓存，如果还是空的就返回 EOF*/ } inline static void pc(char c) { p3 == p4 ? outbuf->sputn(p3 = buf_w, SIZE), *p3++ = c : *p3++ = c; /*逻辑差不多，如果写完整个缓存就全部输出，否则写入缓存*/ } inline static int Flush() { return outbuf->sputn(buf_w, p3 - buf_w), 0; } //清空数组 struct IOdesu { template<typename T> IOdesu& operator >>(T &x) { x = 0; int f = 1; char ch; gc(ch); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; gc(ch); } while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', gc(ch); return x *= f, *this; } template<typename T> IOdesu& operator <<(T x) { if (x < 0) x = -x, pc('-'); static int buf[35]; int top = 0; do { buf[top++] = x % 10; x /= 10; } while (x); while (top) pc(buf[--top] + '0'); return *this; } IOdesu& operator <<(char ch) { return pc(ch), *this; } } qwq; } /* 使用教程 qwq >> x; qwq << x; */卡时有一个 clock() 函数，返回程序运行时间。while ((double)clock()/CLOCKS_PER_SEC < MAX_TIME) action();这样子就会一直跑action，直到用时即将超过时间限制MAX_TIME 是一个自定义的略小于时限的数（秒）O1快速乘long double实现 (弃用，在支持__int128的场景应使用int128)inline LL qmul(LL x, LL y, LL p) { LL z = (LD) x / p * y; LL res = (ULL) x * y - (ull) z * p; return (res + p) % p; }随机数生成器static mt19937 gen(time(nullptr)); //static mt19937 gen(chrono::steady_clock::now().time_since_epoch().count()); //更高精度的时间戳增加随机性 inline int randInt(int l, int r) { // 支持负数, 范围[l, r] uniform_int_distribution<int> d(l, r); // 确保分布均匀 return d(gen); } inline double randDouble(double l, double r) { // 支持负数, 范围[l, r) uniform_real_distribution<double> d(l, r); // 确保分布均匀 return d(gen); }any_hash (用于 unordered_map, unordered_set等防止哈希冲突，以及使其支持PII)struct any_hash { static size_t get_seed() { static const size_t sd = []() { mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); return static_cast<size_t>(rng()); }(); return sd; } template<typename T> size_t operator()(const T &x) const { return hash<T>{}(x) ^ (get_seed() + 0x9e3779b9 + (x << 6) + (x >> 2)); } template<typename T1, typename T2> size_t operator()(const pair<T1, T2> &p) const { size_t hash1 = (*this)(p.first); size_t hash2 = (*this)(p.second); return hash1 ^ (hash2 + get_seed() + 0x9e3779b9 + (hash1 << 6) + (hash1 >> 2)); } };离散化insert 之后请务必先 build 再 getstruct Discretizer { vector<int> a; inline void insert(int x) { a.push_back(x); } void build() { sort(a.begin(), a.end()); a.resize(unique(a.begin(), a.end()) - a.begin()); } inline int get(int x) { return lower_bound(a.begin(), a.end(), x) - a.begin() + 1; } };数学分数运算struct Frac { LL num, den; constexpr Frac(LL n = 0, LL d = 1) : num(n), den(d) { norm(); } constexpr explicit Frac(LL n) : num(n), den(1) {} constexpr explicit Frac() : num(0), den(1) {} void norm() { if (num == 0) return; if (den < 0) num = -num, den = -den; LL g = std::gcd(num, den); if (g) num /= g, den /= g; } Frac &operator+=(const Frac &rhs) { num = num * rhs.den + rhs.num * den; den *= rhs.den; norm(); return *this; } Frac &operator-=(const Frac &rhs) { num = num * rhs.den - rhs.num * den; den *= rhs.den; norm(); return *this; } Frac &operator*=(const Frac &rhs) { num *= rhs.num; den *= rhs.den; norm(); return *this; } Frac &operator/=(const Frac &rhs) { num *= rhs.den; den *= rhs.num; norm(); return *this; } friend Frac operator+(Frac lhs, const Frac &rhs) { return lhs += rhs; } friend Frac operator-(Frac lhs, const Frac &rhs) { return lhs -= rhs; } friend Frac operator*(Frac lhs, const Frac &rhs) { return lhs *= rhs; } friend Frac operator/(Frac lhs, const Frac &rhs) { return lhs /= rhs; } Frac operator-() const { return Frac(-num, den); } friend bool operator<(const Frac &a, const Frac &b) { return (__int128) a.num * b.den < (__int128) b.num * a.den; } friend bool operator>(const Frac &a, const Frac &b) { return b < a; } friend bool operator<=(const Frac &a, const Frac &b) { return !(b < a); } friend bool operator>=(const Frac &a, const Frac &b) { return !(a < b); } friend bool operator==(const Frac &a, const Frac &b) { return a.num == b.num && a.den == b.den; } friend bool operator!=(const Frac &a, const Frac &b) { return !(a == b); } };线筛(附一种快速分解质因数的思路)以下代码和普通线筛的区别就是把用于标记是否为合数的bool数组改为存储当前数的最小质因数，每次我们只需要对当前数字的最小质因数的数字进行整除到不能再整除，继续用得到的新数字除到mnz为0，所得的数即为最后一个质因数(最大质因数)struct prime { vector<int> zs, mnz; prime(int x) { mnz.resize(x + 1); zs.reserve(static_cast<int>(x / log(x)) + (x / 100) + 100); for (int i = 2; i <= x; ++i) { if (!mnz[i]) zs.push_back(i), mnz[i] = i; for (int j : zs) { if (i * j > x) break; mnz[i * j] = j; if (j == mnz[i]) break; } } } };快速分解质因数代码vector<PII> factorize(int n, const Prime& S) { vector<PII> res; while (n > 1) { int p = S.mnz[n], cnt = 0; do { n /= p; ++cnt; } while (n % p == 0); res.emplace_back(p, cnt); } return res; }数据结构单调队列deque<int> q; for (int i = 1; i <= n; i++) { while (!q.empty() && a[q.back()] >= a[i]) q.pop_back(); q.push_back(i); if (i - q.front() >= k) q.pop_front(); if (i >= k) cout << a[q.front()] << " "; }单调栈维护当前大于等于某个值的最靠近当前位置的下标for (int i = 0; i < n; ++i) { if (A[i] == B[i]) ans += (i + 1ll) * (n - i); else { auto it = st.rend(); if (!st.empty()) it = lower_bound(st.rbegin(), st.rend(), PII{max(A[i], B[i]), 0}); ans += it != st.rend() ? (it->second + 1ll) * (n - i) : 0ll; } while (!st.empty() && st.back().first <= A[i]) st.pop_back(); st.emplace_back(A[i], i); }动态求中位数 (红黑树顶红黑树)struct Med { multiset<int, greater<>> L; // 左半（含中位数） multiset<int> R; // 右半 long long sL = 0, sR = 0; // 和 void clear() { L.clear(); R.clear(); sL = sR = 0; } int med() const { return *L.begin(); } //Lmed int cntL() const { return (int)L.size() - 1; } int cntR() const { return (int)R.size(); } long long sumL() const { return sL - *L.begin(); } long long sumR() const { return sR; } void bal() { if (L.size() < R.size()) { auto it = R.begin(); int x = *it; R.erase(it); sR -= x; L.insert(x); sL += x; } else if (L.size() > R.size() + 1) { auto it = L.begin(); int x = *it; L.erase(it); sL -= x; R.insert(x); sR += x; } } void add(int x) { if (L.empty() || x <= *L.begin()) L.insert(x), sL += x; else R.insert(x), sR += x; bal(); } void del(int x) { auto it = L.find(x); if (it != L.end()) { L.erase(it); sL -= x; } else { it = R.find(x); if (it != R.end()) { R.erase(it); sR -= x; } } bal(); } };莫队基础莫队(极限数据量 $5 \times 10^5$/s)vector<int> pos(50005), ans(50005), cnt(50005), a(50005); struct XX { int L, R, p; } q[200005]; bool cmp(XX A, XX B) { if (pos[A.L] != pos[B.L])return pos[A.L] < pos[B.L]; if (pos[A.L] & 1) return A.R > B.R; else return A.R < B.R; } int A = 0; inline void add(int x) { A -= cnt[a[x]] * cnt[a[x]]; ++cnt[a[x]]; A += cnt[a[x]] * cnt[a[x]]; } inline void del(int x) { A -= cnt[a[x]] * cnt[a[x]]; --cnt[a[x]]; A += cnt[a[x]] * cnt[a[x]]; } void solve() { int n, m, k; cin >> n >> m >> k; int block = sqrt(n); //块长 for (int i = 0; i < n; ++i) { cin >> a[i]; pos[i] = i / (block + 1); //索引所属块 } for (int i = 0; i < m; ++i) { cin >> q[i].L >> q[i].R; q[i].p = i; --q[i].L, --q[i].R; } sort(q, q + m, cmp); int zl = 0, zr = -1; for (int i = 0; i < m; ++i) { //该处放"暴力求解"代码 while (zl < q[i].L) del(zl++); while (zr > q[i].R) del(zr--); while (zl > q[i].L) add(--zl); while (zr < q[i].R) add(++zr); ans[q[i].p] = A; } for (int i = 0; i < m; ++i) { cout << ans[i] << endl; } }莫队+分块求区间MEX(离线)const int N = 2e5 + 10, NN = 500; vector<int> cnt(200005), a(200005), pos(200005), ans(200005), b(502); struct XX { int L, R, id; } q[200005]; bool cmp(XX A, XX B) { if (pos[A.L] != pos[B.L]) return A.L < B.L; else { if (pos[A.L] & 1) return A.R > B.R; else return A.R < B.R; } } inline void add(int p) { if (++cnt[a[p]] == 1) ++b[a[p] / NN]; } inline void del(int p) { if (--cnt[a[p]] == 0) --b[a[p] / NN]; } inline int check() { for (int i = 0; i < 501; ++i) { if (b[i] != NN) { for (int j = NN * i; j < 200005; ++j) { if (!cnt[j]) return j; } } } } void solve() { int n, m; cin >> n >> m; int block = static_cast<int>(sqrt(n)); for (int i = 1; i <= n; ++i) { cin >> a[i]; pos[i + 1] = i / (block + 1); } for (int i = 0; i < m; ++i) { cin >> q[i].L >> q[i].R; q[i].id = i; } sort(q, q + m, cmp); int L = 1, R = 0; for (int i = 0; i < n; ++i) { while(L < q[i].L) del(L++); while(L > q[i].L) add(--L); while(R < q[i].R) add(++R); while(R > q[i].R) del(R--); ans[q[i].id] = check(); } for (int i = 0; i < m; ++i) { cout << ans[i] << endl; } }带修莫队vector<int> pos(150000), a(150000), ans; struct XX { int L, R, T, p; } q[150000]; struct FIX { int x, v; //位置，值 }; bool cmp(XX A, XX B) { if (pos[A.L] != pos[B.L])return pos[A.L] < pos[B.L]; else if (pos[A.R] != pos[B.R]) { if (pos[A.L] & 1) return A.R > B.R; else return A.R < B.R; } else return A.T < B.T; } int A = 0; vector<int> cnt(1000001); inline void add(int x) { if (++cnt[x] == 1) ++A; } inline void del(int x) { if (--cnt[x] == 0) --A; } vector<FIX> r(133335); //下标为时间戳，什么时候修改了什么值 void solve() { //ans.reserve(150000); 预分配空间，防止push_back() 产生内存移动 int n, m, T = 0; cin >> n >> m; int block = pow(n, 2.0 / 3.0); for (int i = 1; i <= n; ++i) { cin >> a[i]; pos[i] = i / block; } for (int i = 0; i < m; ++i) { char op; cin >> op; if (op == 'Q') { cin >> q[i].L >> q[i].R; q[i].T = T; q[i].p = static_cast<int>(ans.size()); ans.push_back(0); } else { ++T; cin >> r[T].x >> r[T].v; } } sort(q, q + m, cmp); int zl = 1, zr = 0; T = 0; for (int i = 0; i < m; ++i) { while (zl < q[i].L) del(a[zl++]); while (zr > q[i].R) del(a[zr--]); while (zl > q[i].L) add(a[--zl]); while (zr < q[i].R) add(a[++zr]); while (T < q[i].T) { ++T; if (zl <= r[T].x && r[T].x <= zr) { add(r[T].v); del(a[r[T].x]); } swap(a[r[T].x], r[T].v); } while (T > q[i].T) { if (zl <= r[T].x && r[T].x <= zr) { add(r[T].v); del(a[r[T].x]); } swap(a[r[T].x], r[T].v); --T; } ans[q[i].p] = A; } for (long long i: ans) cout << i << endl; }Trie普通Trietemplate <int MAXN, int ALPHA_SIZE, char BASE_CHAR> struct Trie { int tr[MAXN][ALPHA_SIZE]; int cnt[MAXN]; int pass_cnt[MAXN]; //如不需要删除或者start_with可以不开该数组节省空间 int node_cnt; void init() { memset(tr[0], 0, ALPHA_SIZE * sizeof(int)); memset(cnt, 0, sizeof(cnt)); memset(pass_cnt, 0, sizeof(pass_cnt)); node_cnt = 1; } void insert(const string &s) { int p = 0; for (int i = 0; i < s.size(); ++i) { int c = s[i] - BASE_CHAR; if (!tr[p][c]) { memset(tr[node_cnt], 0, ALPHA_SIZE * sizeof(int)); tr[p][c] = node_cnt++; } p = tr[p][c]; pass_cnt[p]++; } cnt[p]++; } void erase(const string &s) { int p = 0; for (int i = 0; i < s.size(); ++i) { p = tr[p][s[i] - BASE_CHAR]; if (!p) return; pass_cnt[p]--; } if (cnt[p] > 0) cnt[p]--; } int search(const string &s) { int p = 0; for (int i = 0; i < s.size(); ++i) { p = tr[p][s[i] - BASE_CHAR]; if (!p) break; } return p ? cnt[p] : 0; } bool starts_with(const string &s) { int p = 0; for (int i = 0; i < s.size(); ++i) { p = tr[p][s[i] - BASE_CHAR]; if (!p || pass_cnt[p] == 0) return false; } return true; } }; /* 注意:内开需要把静态改为vector 初始化<节点容量, 字符数, 起始字符> 使用示例： // 小写字母 trie（1e5 节点容量） Trie<100000, 26, 'a'> lower_trie; // 数字 trie（1e4 节点容量） Trie<10000, 10, 0> num_trie; // 01 trie （1e4节点容量） Trie<10000, 2, 0> num_trie; // 大写字母 trie（带自定义容量） Trie<50000, 26, 'A'> upper_trie; // 初始化 lower_trie.init(); //一定要记得 lower_trie.insert("algorithm"); lower_trie.search("algo"); // 返回 0 lower_trie.search("algorithm"); // 返回 1 lower_trie.starts_with("algo"); // 返回 true */01 Trie 求最大异或值template <int MAX_BIT = 31, typename T = int> // 默认处理 31位int整数（符号位除外） struct BTrie { static const int SIZE = MAX_BIT * 5e5 + 10; // 根据问题规模调整 int tr[SIZE][2]; int cnt[SIZE]; // 经过该节点的数字数量 int node_cnt; inline void init() { node_cnt = cnt[0] = tr[0][0] = tr[0][1] = 0; } // 插入数字（二进制从高位到低位存储） void insert(T num) { int p = 0; for (int i = MAX_BIT-1; i >= 0; --i) { int b = (num >> i) & 1; if (!tr[p][b]) { tr[p][b] = ++node_cnt; cnt[node_cnt] = tr[node_cnt][0] = tr[node_cnt][1] = 0; } p = tr[p][b]; cnt[p]++; } } // 删除数字（需保证数字存在） void erase(T num) { int p = 0; for (int i = MAX_BIT-1; i >= 0; --i) { int b = (num >> i) & 1; p = tr[p][b]; cnt[p]--; } } // 查询与 num 异或后的最大值 T max_xor(T num) { if (!node_cnt) return 0; // 空 Trie T res = 0; int p = 0; for (int i = MAX_BIT-1; i >= 0; --i) { int best = ((num >> i) & 1) ^ 1; // 优先选相反的位 if (tr[p][best] && cnt[tr[p][best]] > 0) { res |= ((T)1 << i); p = tr[p][best]; } else { p = tr[p][best ^ 1]; } } return res; } }; /* 使用示例： BTrie<31> trie; // 处理 31 位非负整数 BTrie <32, unsigned int> trie; // 处理 32位 */ //可用于处理 (最大/最小 AND/OR/XOR) 区间最大XOR和(配合前缀XOR数组)可持久化Trietemplate <int MAX_BIT = 31, typename T = int> struct PersistentBTrie { struct Node { int ch[2] = {0, 0}; int cnt = 0; }; std::vector<Node> nodes; std::vector<int> roots; // 各版本根节点索引 PersistentBTrie() { nodes.emplace_back(); // 初始化空节点（版本0） roots.push_back(0); // 初始版本0 } // 插入新数字并生成新版本，prev_version为基准版本号 int insert(T num, int prev_version) { int new_root = nodes.size(); nodes.push_back(nodes[roots[prev_version]]); // 克隆旧根节点 nodes[new_root].cnt++; // 当前路径计数+1 roots.push_back(new_root); // 记录新版本根节点 int curr = new_root; for (int i = MAX_BIT-1; i >= 0; --i) { int b = (num >> i) & 1; int next = nodes[curr].ch[b]; int new_node = nodes.size(); nodes.push_back(nodes[next]); // 克隆子节点 nodes[new_node].cnt++; // 更新当前路径计数 nodes[curr].ch[b] = new_node; // 链接新节点 curr = new_node; } return roots.size() - 1; // 返回新版本号 } // 查询区间 [l_ver, r_ver] 内与num异或的最大值 T max_xor(int l_ver, int r_ver, T num) { int l_root = roots[l_ver], r_root = roots[r_ver]; T res = 0; for (int i = MAX_BIT-1; i >= 0; --i) { int b = (num >> i) & 1; int target = b ^ 1; // 期望的bit int r_ch = nodes[r_root].ch[target]; int l_ch = nodes[l_root].ch[target]; int diff = nodes[r_ch].cnt - nodes[l_ch].cnt; if (diff > 0) { // 存在该路径 res |= T(1) << i; r_root = r_ch; l_root = l_ch; } else { // 路径不存在，选择另一边 r_root = nodes[r_root].ch[target ^ 1]; l_root = nodes[l_root].ch[target ^ 1]; } } return res; } }; 树状数组普通树状数组(单点修改, 区间查询)template<typename T> struct Fenwick { vector<T> tree; int n; static inline int lowbit(int x) { return x & (-x); } explicit Fenwick(int size) : n(size), tree(size + 1, 0) {} void add(int x, T v) { while (x <= n) { tree[x] += v; x += lowbit(x); } } T query(int x) const { T res = 0; while (x) { res += tree[x]; x -= lowbit(x); } return res; } // 查询区间和 [l, r] T query(int l, int r) { return query(r) - query(l - 1); } T operator[](int x) const { return query(x) - query(x - 1); } };普通树状数组区间修改template<typename T> struct FenwickRange { vector<T> tree1, tree2; // 两个差分树 int n; static inline int lowbit(int x) { return x & (-x); } explicit FenwickRange(int size) : n(size), tree1(size + 2, 0), tree2(size + 2, 0) {} void _add(vector<T>& tree, int x, T v) { // 同时更新两个树 while (x <= n) { tree[x] += v; x += lowbit(x); } } void add(int l, int r, T v) { // 区间 [l, r] 增加 v _add(tree1, l, v); _add(tree1, r + 1, -v); _add(tree2, l, v * l); _add(tree2, r + 1, -v * (r + 1)); } T query(int x) { // 查询前缀和 [1, x] T res1 = 0, res2 = 0; int t = x; while (x > 0) { res1 += tree1[x]; res2 += tree2[x]; x -= lowbit(x); } return (t + 1) * res1 - res2; } // 查询区间和 [l, r] T query(int l, int r) { return query(r) - query(l - 1); } T operator[](int x) const { return query(x, x); } };二维树状数组template<typename T> struct Fenwick2D { vector<vector<T>> tree; int rows, cols; static int lowbit(int x) { return x & (-x); } explicit Fenwick2D(int r, int c) : rows(r), cols(c), tree(r + 1, vector<T>(c + 1, 0)) {} void add(int x, int y, T v) { // 在位置 (x,y) 处增加值 v（1-based） for (int i = x; i <= rows; i += lowbit(i)) { for (int j = y; j <= cols; j += lowbit(j)) { tree[i][j] += v; } } } T query(int x, int y) const { // 查询(1,1) 到 (x,y) 的矩形和 T res = 0; for (int i = x; i > 0; i -= lowbit(i)) { for (int j = y; j > 0; j -= lowbit(j)) { res += tree[i][j]; } } return res; } T query(int x1, int y1, int x2, int y2) const { // 矩形区域 [x1,y1] 到 [x2,y2] 的和（闭区间） return query(x2, y2) - query(x1 - 1, y2) - query(x2, y1 - 1) + query(x1 - 1, y1 - 1); } };二维树状数组区间修改 template<typename T> struct Fenwick2DRange { struct { vector<vector<T>> tree; int rows{}, cols{}; void init(int r, int c) { rows = r; cols = c; tree.assign(r + 2, vector<T>(c + 2, 0)); } void add(int x, int y, T v) { for (int i = x; i <= rows; i += lowbit(i)) for (int j = y; j <= cols; j += lowbit(j)) tree[i][j] += v; } T query(int x, int y) { T res = 0; for (int i = x; i > 0; i -= lowbit(i)) for (int j = y; j > 0; j -= lowbit(j)) res += tree[i][j]; return res; } } D, Dx, Dy, Dxy; int rows, cols; static int lowbit(int x) { return x & (-x); } explicit Fenwick2DRange(int r, int c) : rows(r), cols(c) { D.init(r, c); Dx.init(r, c); Dy.init(r, c); Dxy.init(r, c); } void range_add(int x1, int y1, int x2, int y2, T v) { D.add(x1, y1, v); D.add(x1, y2+1, -v); D.add(x2+1, y1, -v); D.add(x2+1, y2+1, v); Dx.add(x1, y1, v * (x1-1)); Dx.add(x1, y2+1, -v * (x1-1)); Dx.add(x2+1, y1, -v * x2); Dx.add(x2+1, y2+1, v * x2); Dy.add(x1, y1, v * (y1-1)); Dy.add(x1, y2+1, -v * y2); Dy.add(x2+1, y1, -v * (y1-1)); Dy.add(x2+1, y2+1, v * y2); Dxy.add(x1, y1, v * (x1-1) * (y1-1)); Dxy.add(x1, y2+1, -v * (x1-1) * y2); Dxy.add(x2+1, y1, -v * x2 * (y1-1)); Dxy.add(x2+1, y2+1, v * x2 * y2); } T query(int x, int y) { return x * y * D.query(x, y) - y * Dx.query(x, y) - x * Dy.query(x, y) + Dxy.query(x, y); } T query(int x1, int y1, int x2, int y2) { return query(x2, y2) - query(x1-1, y2) - query(x2, y1-1) + query(x1-1, y1-1); } T get(int x, int y) { return query(x, y, x, y); } /* Fenwick2DRange<int> fr(100, 100); // 创建 100x100 的二维区间树 (行, 列) // 在 [3,5] 到 [10,20] 的矩形区域加 5 fr.range_add(3, 5, 10, 20, 5); // 查询 [1,1] 到 [50,50] 的和 fr.query(1, 1, 50, 50); // 单点查询 (7,8) fr.get(7, 8); */ }; 线段树线段树区间加减乘template<int MAX_N> struct LazySegmentTree { private: static constexpr int MAX_TREE_SIZE = 4 * MAX_N; ll tree[MAX_TREE_SIZE]; struct LazyTag { ll mul, add; } lazy[MAX_TREE_SIZE]; ll mod; int n; vector<ll> a; // 辅助函数：处理负数的取模 inline ll mod_val(ll x) const { if (mod == 0) return x; return (x % mod + mod) % mod; } void push_down(int L, int M, int R, int p) { if ((lazy[p].mul != 1 || lazy[p].add != 0) && L != R) { int lc = p<<1, rc = p<<1|1; // 更新左子树 tree[lc] = mod_val(tree[lc] * lazy[p].mul + lazy[p].add * (M-L+1)); // 更新右子树 tree[rc] = mod_val(tree[rc] * lazy[p].mul + lazy[p].add * (R-M)); // 合并标记到左子树 lazy[lc].add = mod_val(lazy[lc].add * lazy[p].mul + lazy[p].add); lazy[lc].mul = mod_val(lazy[lc].mul * lazy[p].mul); // 合并标记到右子树 lazy[rc].add = mod_val(lazy[rc].add * lazy[p].mul + lazy[p].add); lazy[rc].mul = mod_val(lazy[rc].mul * lazy[p].mul); // 重置当前标记 lazy[p].mul = 1; lazy[p].add = 0; } } void push_up(int p) { tree[p] = mod_val(tree[p<<1] + tree[p<<1|1]); } void build(int L, int R, int p) { lazy[p] = {1, 0}; if (L == R) { tree[p] = mod_val(a[L]); return; } int M = (L+R) >> 1; build(L, M, p<<1); build(M+1, R, p<<1|1); push_up(p); } void _update_add(int L, int R, int p, int l, int r, ll v) { if (l <= L && R <= r) { tree[p] = mod_val(tree[p] + v * (R-L+1)); lazy[p].add = mod_val(lazy[p].add + v); return; } int M = (L+R) >> 1; push_down(L, M, R, p); if (l <= M) _update_add(L, M, p<<1, l, r, v); if (r > M) _update_add(M+1, R, p<<1|1, l, r, v); push_up(p); } void _update_mul(int L, int R, int p, int l, int r, ll v) { if (l <= L && R <= r) { tree[p] = mod_val(tree[p] * v); lazy[p].add = mod_val(lazy[p].add * v); lazy[p].mul = mod_val(lazy[p].mul * v); return; } int M = (L+R) >> 1; push_down(L, M, R, p); if (l <= M) _update_mul(L, M, p<<1, l, r, v); if (r > M) _update_mul(M+1, R, p<<1|1, l, r, v); push_up(p); } ll _query(int L, int R, int p, int l, int r) { if (l <= L && R <= r) return tree[p]; int M = (L+R) >> 1; push_down(L, M, R, p); ll res = 0; if (l <= M) res += _query(L, M, p<<1, l, r); if (r > M) res += _query(M+1, R, p<<1|1, l, r); return mod_val(res); } public: // 初始化：传入原始数组（1-based）和模数（0表示不取模） LazySegmentTree(const vector<ll>& arr, ll m = 0) : mod(m), n(arr.size()-1), a(arr) { assert(arr.size() > 1 && "Array should be 1-based"); build(1, n, 1); } // 区间加 [l, r] 闭区间 void range_add(int l, int r, ll v) { _update_add(1, n, 1, l, r, v); } // 区间乘 [l, r] 闭区间 void range_mul(int l, int r, ll v) { _update_mul(1, n, 1, l, r, v); } // 区间查询 [l, r] 闭区间 ll range_query(int l, int r) { return _query(1, n, 1, l, r); } }; // 使用示例： // vector<ll> arr(n+1); // 1-based // LazySegmentTree<100000> st(arr, mod); // st.range_add(l, r, v); // st.range_mul(l, r, v); // ll sum = st.range_query(l, r);动态开点constexpr int N = 2e5 + 10; struct node { int l, r, lazy, v; } tr[N * 30]; int cnt = 0; inline int new_node() { tr[++cnt] = {}; return cnt; } inline void pushup(int p) { tr[p].v = (tr[p].l ? tr[tr[p].l].v : 0) + (tr[p].r ? tr[tr[p].r].v : 0); } void pushdown(int l, int m, int r, int p) { if (l != r && tr[p].lazy) { if (!tr[p].l) tr[p].l = new_node(); if (!tr[p].r) tr[p].r = new_node(); tr[tr[p].l].lazy += tr[p].lazy, tr[tr[p].l].v += tr[p].lazy * (m - l + 1); tr[tr[p].r].lazy += tr[p].lazy, tr[tr[p].r].v += tr[p].lazy * (r - m); tr[p].lazy = 0; } } void update(int l, int r, int p, int ql, int qr, int v) { if (ql <= l && r <= qr) { tr[p].lazy += v; tr[p].v += v * (r - l + 1); return; } int m = (l + r) >> 1; pushdown(l, m, r, p); if (ql <= m) { if (!tr[p].l) tr[p].l = new_node(); update(l, m, tr[p].l, ql, qr, v); } if (qr > m) { if (!tr[p].r) tr[p].r = new_node(); update(m + 1, r, tr[p].r, ql, qr, v); } pushup(p); } int query(int l, int r, int p, int ql, int qr) { if (ql <= l && r <= qr) return tr[p].v; int m = (l + r) >> 1, sum = 0; pushdown(l, m, r, p); if (ql <= m && tr[p].l) sum = query(l, m, tr[p].l, ql, qr); if (qr > m && tr[p].r) sum += query(m + 1, r, tr[p].r, ql, qr); return sum; }主席树(可持久化线段树)主席树求区间MEX(在线)constexpr int N = 2e5 + 10; struct node { int l, r, v; } tr[N * 30]; int cnt = 0, root[N]; inline void pushup(int x) { tr[x].v = min(tr[tr[x].l].v, tr[tr[x].r].v); } int update(int x, int v, int l, int r, int p) { if (l == r) { tr[++cnt].v = v; return cnt; } int nex = ++cnt, mid = (l + r) >> 1; tr[nex] = tr[p]; if (x <= mid) tr[nex].l = update(x, v, l, mid, tr[p].l); else tr[nex].r = update(x, v, mid + 1, r, tr[p].r); pushup(nex); return nex; } int query(int ql, int l, int r, int p) { if (l == r) return l; int mid = (l + r) >> 1; if (tr[tr[p].l].v < ql) return query(ql, l, mid, tr[p].l); return query(ql, mid + 1, r, tr[p].r); } void solve() { int n, q, tmp; cin >> n >> q; for (int i = 1; i <= n; i++) { cin >> tmp; root[i] = update(tmp + 1, i, 1, 2e5+1, root[i - 1]); } while(q--) { int l, r; cin >> l >> r; cout << query(l, 1, 2e5+1, root[r]) - 1 << endl; } }链式前向星const int MAXN = 5e5 + 5; // 最大节点数 const int MAXM = 1e6 + 5; // 最大边数（无向图*2） struct Edge { int to, nex; } e[MAXM]; int head[MAXN], cnt_edge; inline void clear_edge(int n) { for (int i = 0; i <= n; ++i) head[i] = -1; cnt_edge = 0; } inline void add_edge(int u, int v) { e[++cnt_edge].to = v; e[cnt_edge].nex = head[u]; head[u] = cnt_edge; } 倍增LCAconstexpr int MAXN = 5e5 + 10; constexpr int MAX_LOG = 20; // 需满足2^MAX_LOG > 最大深度 struct { int to, nex; } e[MAXN << 1]; int head[MAXN << 1], cnt = 0; inline void add(int x, int y) { e[++cnt].to = y; e[cnt].nex = head[x]; head[x] = cnt; } void init(int n) { for (int i = 0; i <= n; ++i) head[i] = e[i].nex = -1; cnt = 0; } int depth[MAXN]; // 节点深度 int fa[MAXN][MAX_LOG]; // 倍增父亲数组 void dfs_lca(int u, int father) { depth[u] = depth[father] + 1; fa[u][0] = father; for (int i = 1; i < MAX_LOG; ++i) fa[u][i] = fa[fa[u][i - 1]][i - 1]; for (int i = head[u]; i != -1; i = e[i].nex) { int v = e[i].to; if (v != father) dfs_lca(v, u); } } /* //非递归预处理 void dfs_lca(int root, int father) { stack<pair<int, int>> s; s.push({root, father}); while (!s.empty()) { auto [u, f] = s.top(); s.pop(); depth[u] = depth[f] + 1; fa[u][0] = f; for (int i = 1; i < MAX_LOG; ++i) fa[u][i] = fa[fa[u][i-1]][i-1]; for (int i = head[u]; i != -1; i = e[i].nex) { int v = e[i].to; if (v != f) s.push({v, u}); // 子节点入栈 } } } */ inline void init_lca(int root) { // 初始化LCA depth[0] = -1; dfs_lca(root, 0); } int get_lca(int x, int y) { if (depth[x] < depth[y]) swap(x, y); /*-------- 先跳到同一层 --------*/ for (int i = MAX_LOG - 1; i >= 0; --i) if (depth[x] - (1 << i) >= depth[y]) x = fa[x][i]; if (x == y) return x; /*--------- 同时往上跳 --------*/ for (int i = MAX_LOG - 1; i >= 0; --i) if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i]; return fa[x][0]; } int get_dist(int x, int y) { int lca = get_lca(x, y); return depth[x] + depth[y] - 2 * depth[lca]; } int lca_with_root(int u, int v, int r) { int a = get_lca(u, v), b = get_lca(u, r), c = get_lca(v, r); if (a == b) return c; if (a == c) return b; return a; } ST表template<typename T, T (*op)(T, T)> struct ST { vector<vector<T> > st; vector<int> log_table; int n{}; void init(const vector<T> &v) { n = v.size(); log_table.resize(n + 1); log_table[1] = 0; for (int i = 2; i <= n; i++) log_table[i] = log_table[i >> 1] + 1; int k = log_table[n] + 1; st.assign(n, vector<T>(k)); for (int i = 0; i < n; i++) st[i][0] = v[i]; for (int j = 1; j < k; j++) { for (int i = 0; i + (1 << j) <= n; i++) { st[i][j] = op(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]); } } } T query(int l, int r) { int j = log_table[r - l + 1]; return op(st[l][j], st[r - (1 << j) + 1][j]); } }; int max(int a, int b) { return a > b ? a : b; } /* 用法 ST<LL, max> st; ST<int, __gcd> st; */树链剖分struct Edge { int to, nex; } edge[200010]; int cnt = 0, head[200010], n; void init() { for (int i = 0; i < 200010; ++i) { edge[i].to = edge[i].nex = head[i] = -1; } } void add(int x, int y) { edge[++cnt].to = y; edge[cnt].nex = head[x]; head[x] = cnt; } int tree[400020], lazy[400020]; inline void pu(int p) { tree[p] = tree[p << 1] + tree[p << 1 | 1]; } inline void pd(int L, int M, int R, int p) { if (lazy[p] && L != R) { if (lazy[p] == INT_MIN) { tree[p << 1] = tree[p << 1 | 1] = 0; lazy[p << 1] = lazy[p << 1 | 1] = INT_MIN; lazy[p] = 0; return; } tree[p << 1] = lazy[p] * (1 + M - L), tree[p << 1 | 1] = lazy[p] * (R - M); lazy[p << 1] = lazy[p], lazy[p << 1 | 1] = lazy[p]; lazy[p] = 0; } } void update(int L, int R, int p, int l, int r) { if (l <= L && R <= r) { tree[p] = R - L + 1; lazy[p] = 1; return; } int M = L + ((R - L) >> 1); pd(L, M, R, p); if (l <= M) update(L, M, p << 1, l, r); if (r > M) update(M + 1, R, p << 1 | 1, l, r); pu(p); } void resett(int L, int R, int p, int l, int r) { if (l <= L && R <= r) { tree[p] = 0; lazy[p] = INT_MIN; return; } int M = L + ((R - L) >> 1); pd(L, M, R, p); if (l <= M) resett(L, M, p << 1, l, r); if (r > M) resett(M + 1, R, p << 1 | 1, l, r); pu(p); } int query(int L, int R, int p, int l, int r) { int M = L + ((R - L) >> 1), sum = 0; pd(L, M, R, p); if (L >= l && R <= r) { return tree[p]; } if (l <= M) sum = query(L, M, p << 1, l, r); if (r > M) sum += query(M + 1, R, p << 1 | 1, l, r); return sum; } int son[100005], id[100005], fa[100005], deep[100005], siz[100005], top[100005]; void dfs1(int x, int father) { deep[x] = deep[father] + 1; fa[x] = father; siz[x] = 1; for (int i = head[x]; ~i; i = edge[i].nex) { int s = edge[i].to; if (s != father) { fa[s] = x; dfs1(s, x); siz[x] += siz[s]; if (!son[x] || siz[son[x]] < siz[s]) son[x] = s; } } } int num = 0; void dfs2(int x, int topx) { id[x] = ++num; top[x] = topx; if (!son[x]) return; dfs2(son[x], topx); for (int i = head[x]; ~i; i = edge[i].nex) { int y = edge[i].to; if (y != fa[x] && y != son[x]) dfs2(y, y); } } int query_range(int x, int y) { //查询树上路径 x 到 y 的和 int ans = 0; while (top[x] != top[y]) { if (deep[top[x]] < deep[top[y]]) swap(x, y); ans += query(1, n, 1, id[top[x]], id[x]); x = fa[top[x]]; } if (deep[x] > deep[y]) swap(x, y); ans += query(1, n, 1, id[x], id[y]); return ans; } void update_range(int x, int y) { //将路径 x 到 y 的所有节点设为 1。 while (top[x] != top[y]) { if (deep[top[x]] < deep[top[y]]) swap(x, y); update(1, n, 1, id[top[x]], id[x]); x = fa[top[x]]; } if (deep[x] > deep[y]) swap(x, y); update(1, n, 1, id[x], id[y]); } void update_tree(int x) { //将子树 x 的所有节点设为 1。 update(1, n, 1, id[x], id[x] + siz[x] - 1); } void reset_tree(int x) { //将子树 x 的所有节点设为 0。 resett(1, n, 1, id[x], id[x] + siz[x] - 1); } int query_tree(int x) { //查询子树的和 return query(1, n, 1, id[x], id[x] + siz[x] - 1); } 并查集新版本-单数组+路径折半 (常数小)// 1-base struct DSU { vector<int> p; int cnt; DSU(int n = 0) { init(n); } void init(int n) { p.assign(n + 1, -1); cnt = n; } int find(int x) { while (p[x] >= 0) { int px = p[x]; if (p[px] >= 0) p[x] = p[px]; x = px; } return x; } bool unite(int a, int b) { a = find(a), b = find(b); if (a == b) return false; if (p[a] > p[b]) swap(a, b); p[a] += p[b]; p[b] = a; --cnt; return true; } int siz(int x) { return -p[find(x)]; } int comps() const { return cnt; } };老版本-完全路径压缩版struct DSU { vector<int> p, sz; DSU(int n = 0) { init(n); } void init(int n) { p.resize(n + 1); iota(p.begin(), p.end(), 0); sz.assign(n + 1, 1); } int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); } bool unite(int a,int b) { a = find(a), b = find(b); if (a == b) return false; if (sz[a] < sz[b]) swap(a, b); p[b] = a, sz[a] += sz[b]; return true; } };带权并查集int find(int x) { if (a[x] != x) { int root = find(a[x]); w[x] += w[a[x]]; a[x] = root; } return a[x]; } void unite(int x, int y, int d) { int fx = find(x), fy = find(y); if (fx != fy) { a[fx] = fy; w[fx] = d + w[y] - w[x]; } } //x合并至y字符串KMPvoid getNext(const string &p, vector<int> &lps) { int m = p.size(); lps.assign(m, 0); for (int i = 1, j = 0; i < m; ++i) { while (j > 0 && p[i] != p[j]) j = lps[j - 1]; if (p[i] == p[j]) ++j; lps[i] = j; } } vector<int> kmp(const string &s, const string &p) { vector<int> res; int n = s.size(), m = p.size(); if (m == 0) return res; // 视题意处理空模式 vector<int> lps; getNext(p, lps); for (int i = 0, j = 0; i < n; ++i) { while (j > 0 && s[i] != p[j]) j = lps[j - 1]; if (s[i] == p[j]) ++j; if (j == m) { res.push_back(i - m + 1); // 0-based 起始位置；若要 1-based 用 i - m + 2 j = lps[j - 1]; } } return res; }Z函数（拓展KMP）vector<int> Z(string s) { int n = s.size(); std::vector<int> z(n + 1); z[0] = n; for (int i = 1, j = 1; i < n; i++) { z[i] = max(0, min(j + z[j] - i, z[i - j])); while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++; if (i + z[i] > j + z[j]) j = i; } return z; }AC自动机以求模式串出现次数为示例的AC自动机模板constexpr int N = 1000005; constexpr LL mod = 998'244'353; int cnt[N], endpos[N]; struct AC { int zz = 0; queue<int> q; struct node { int ch[26], fail, ans; } trie[N]; int insert(const string& s) { int u = 0; for (char c : s) { int v = c - 'a'; if (!trie[u].ch[v]) trie[u].ch[v] = ++zz; u = trie[u].ch[v]; } return u; } void build() { for (int c = 0; c < 26; ++c) { int v = trie[0].ch[c]; if (v) q.push(v); } while (!q.empty()) { int u = q.front();q.pop(); for (int i = 0; i < 26; ++i) { int v = trie[u].ch[i], fail = trie[u].fail; if (!v) trie[u].ch[i] = trie[fail].ch[i]; else { trie[v].fail = trie[fail].ch[i]; ++cnt[trie[v].fail]; q.push(v); } } } //----- 建fail树 ---- // for (int v = 1; v <= zz; ++v) { // int f = trie[v].fail; // tree[f].push_back(v); // } } void query(const string& s) { int u = 0; for (char i : s) { int v = i - 'a'; u = trie[u].ch[v]; ++trie[u].ans; } } void get_ans() { for (int i = 0; i <= zz; ++i) if (!cnt[i]) q.push(i); while (!q.empty()) { int u = q.front();q.pop(); trie[trie[u].fail].ans += trie[u].ans; if (--cnt[trie[u].fail] == 0) q.push(trie[u].fail); } } } ac; string str[N]; void solve() { int n; cin >> n; for (int i = 1; i <= n; ++i) { cin >> str[i]; endpos[i] = ac.insert(str[i]); } ac.build(); cin >> str[0]; ac.query(str[0]); ac.get_ans(); for (int i = 1; i <= n; ++i) cout << ac.trie[endpos[i]].ans << endl; }HASH常用模数 $13331$，$131$hash二分求回文子串数量#define hash_t unsigned __int128 #define hash_tt unsigned long long hash_t pre[100005], suf[100005], p[100005], base = 13333333111; hash_tt pre1[100005], suf1[100005], p1[100005], base1 = 13331; int a[100005], v[100005]; void init(int n) { p[0] = p1[0] = 1; for (int i = 1; i <= n; i++) { pre[i] = pre[i-1] * base + a[i]; pre1[i] = pre1[i-1] * base1 + a[i]; p[i] = p[i-1] * base; p1[i] = p1[i-1] * base1; } for (int i = n; i >= 1; i--) { suf[i] = suf[i+1] * base + a[i]; suf1[i] = suf1[i+1] * base1 + a[i]; } } inline bool check(int l, int r) { if (suf[l] - suf[r+1] * p[r-l+1] == pre[r] - pre[l-1] * p[r-l+1] && suf1[l] - suf1[r+1] * p1[r-l+1] == pre1[r] - pre1[l-1] * p1[r-l+1]) return true; return false; } int count_huiwen(int n) { int count = 0; for (int i = 1; i <= n; ++i) { int l = 0, r = min(i - 1, n - i), ans = -1; while (l <= r) { int mid = (l + r) >> 1; if (check(i - mid, i + mid)) ans = mid, l = mid + 1; else r = mid - 1; } count += ans + 1; } for (int i = 1; i <= n - 1; ++i) { int l = 1, r = min(i, n - i), ans = 0; while (l <= r) { int mid = (l + r) >> 1; if (i - mid + 1 < 1 || i + mid > n || i - mid + 1 > i + mid) { r = mid - 1; continue; } if (check(i - mid + 1, i + mid)) ans = mid, l = mid + 1; else r = mid - 1; } count += ans; } return count; } HASH求双回文子串长度(可求对应位置的前后回文长度)（代替马拉车）参考题目，洛谷P4555，求字符串中双回文子串的最大长度。#include <bits/stdc++.h> #define PII pair<int,int> #define LL long long #define LD long double #define ULL unsigned int #define endl '\n' using namespace std; ULL base = 131; vector<ULL> h1(100005), h2(100005), p(100005); int mx_pre[100005], mx_suf[100005]; inline ULL pre_hash(int l, int r) { return h1[r] - h1[l - 1] * p[r - l + 1]; } inline ULL suf_hash(int l, int r) { return h2[l] - h2[r+1] * p[r - l + 1]; } void solve() { string str; int mx = 0; cin >> str; p[0] = mx_pre[1] = mx_suf[str.size()] = 1;; for (int i = 1; i < 100005; ++i) p[i] = p[i-1] * base; for (int i = 0; i < str.size(); ++i) h1[i+1] = h1[i] * base + static_cast<ULL>(str[i] - 'a' + 1); for (int i = str.size() - 1; i >= 0; --i) h2[i + 1] = h2[i + 2] * base + static_cast<ULL>(str[i] - 'a' + 1); for (int i = 2; i <= str.size(); ++i) { int tmp = min(i, mx_pre[i - 1] + 2); while(pre_hash(i - tmp + 1,i) != suf_hash(i - tmp + 1, i)) --tmp; mx_pre[i] = tmp; } for (int i = str.size() - 1; i ; --i) { int tmp = min((int)str.size() - i + 1, mx_suf[i + 1] + 2); while(pre_hash(i,i + tmp - 1) != suf_hash(i, i + tmp - 1)) --tmp; mx_suf[i] = tmp; mx = max(mx, mx_suf[i + 1] + mx_pre[i]); } cout << mx << endl; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T = 1; // cin >> T; while (T--) { solve(); } return 0; }矩阵哈希参考洛谷P10474#include <bits/stdc++.h> #define LL long long #define int long long #define ULL unsigned long long #define PII pair<LL,LL> #define PCL pair<char,LL> #define endl '\n' using namespace std; ULL base = 131, base2 = 113, h[1002][1002], p1[1005], p2[1005]; void init() { } set<ULL> st; void solve() { int n, m, a, b; char ch; cin >> n >> m >> a >> b; p1[0] = p2[0] = 1; for (int i = 1; i < 1005; ++i) { p1[i] = p1[i - 1] * base; p2[i] = p2[i - 1] * base2; } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { cin >> ch; h[i][j] = h[i][j - 1] * base + (ULL) (ch - '0' + 1); } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; ++j) { h[i][j] = h[i - 1][j] * base2 + h[i][j]; } } for (int i = a; i <= n; i++) { for (int j = a; j <= m; ++j) { st.insert(h[i][j] - h[i - a][j] * p2[a] - h[i][j - b] * p1[b] + h[i - a][j - b] * p1[b] * p2[a]); } } cin >> n; while (n--) { for (int i = 1; i <= a; ++i) { for (int j = 1; j <= b; ++j) { cin >> ch; h[i][j] = h[i][j - 1] * base + (ULL) (ch - '0' + 1); } } for (int i = 1; i <= a; i++) h[i][b] = h[i - 1][b] * base2 + h[i][b]; cout << st.count(h[a][b]) << endl; } } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); init(); int T = 1; // cin >> T; while (T--) { solve(); } return 0; }SAMstruct SAM { /* ========= 常量定义 ========= */ static constexpr int MAXN = 100'000; // 原串最大长度 static constexpr int SIGMA = 26; // 字符集大小 struct Node { //int ch[SIGMA]{}; // 初始化为 0 map<int, int> ch; int fa = 0; int len = 0; int sz = 0; }; /* ========= 成员 ========= */ Node st[MAXN * 2 + 5]; long long dp[MAXN * 2 + 5]; // 用于 get_rank int bucket[MAXN + 5]; // 基数排序桶 int topo[MAXN * 2 + 5]; // 拓扑序 int last = 1, tot = 1; // root = 1 int n = 0; // 原串长度 long long distinct_substr = 0; /* ========= 基础操作 ========= */ void clear() { // 多 case 使用 last = tot = 1; st[1] = Node(); // 重新置 0 } void extend(int c) { // 插入字符编号 c int p = last; int np = last = ++tot; st[np].sz = 1; st[np].len = st[p].len + 1; while (p && !st[p].ch.count(c)) { st[p].ch[c] = np; p = st[p].fa; } if (!p) { st[np].fa = 1; } else { int q = st[p].ch[c]; if (st[q].len == st[p].len + 1) { st[np].fa = q; } else { // case 3 (clone) int nq = ++tot; st[nq] = st[q]; // 拷贝所有信息 st[nq].len = st[p].len + 1; st[nq].sz = 0; // clone 节点不对应 endpos st[q].fa = st[np].fa = nq; while (p && st[p].ch[c] == q) { st[p].ch[c] = nq; p = st[p].fa; } } } distinct_substr += st[np].len - st[st[np].fa].len; } /* ========= 输入 / 预处理 ========= */ void build_from_string(const string& s) { clear(); n = (int)s.size(); for (char ch: s) extend(ch - 'a'); radix_sort(); // 获得 topo 序 calc_sz(); // 统计 sz //calc_distinct_substr(); } /* ========= 基数排序 (按 len) ========= */ void radix_sort() { fill(bucket, bucket + n + 1, 0); for (int i = 1; i <= tot; ++i) ++bucket[st[i].len]; for (int i = 1; i <= n; ++i) bucket[i] += bucket[i - 1]; for (int i = tot; i >= 1; --i) topo[bucket[st[i].len]--] = i; } /* ========= 求 sz ========= */ void calc_sz() { for (int i = tot; i >= 1; --i) { int u = topo[i]; int fa = st[u].fa; if (fa) st[fa].sz += st[u].sz; } } /* ========= 本质不同子串数量 ========= */ // void calc_distinct_substr() { // distinct_substr = 0; // for (int i = 2; i <= tot; ++i) // 从 2 开始可省一次访问 root // distinct_substr += st[i].len - st[st[i].fa].len; // } /* ========= 常用查询 ========= */ int count_occurrence(const string& t) { int u = 1; for (char ch : t) { int idx = ch - 'a'; if (!st[u].ch[idx]) return 0; u = st[u].ch[idx]; } return st[u].sz; } int longest_repeated_substring() const { int ans = 0; for (int i = 2; i <= tot; ++i) if (st[i].sz >= 2) ans = max(ans, st[i].len); return ans; } long long substring_rank(const string& t) { // 若不存在返回 -1 /* 先在 topo 序中自底向上做一次 dp，不需要 memset */ for (int i = 1; i <= tot; ++i) dp[i] = 1; // 自身空串 for (int i = tot; i >= 1; --i) { int u = topo[i]; for (int k = 0; k < SIGMA; ++k) if (int v = st[u].ch[k]) dp[u] += dp[v]; } long long ans = 0; int u = 1; for (char ch : t) { int idx = ch - 'a'; for (int k = 0; k < idx; ++k) if (int v = st[u].ch[k]) ans += dp[v]; if (!st[u].ch[idx]) return -1; u = st[u].ch[idx]; } return ans + 1; } /* ========= DEMO ========= */ void demo_solve() { ios::sync_with_stdio(false); cin.tie(nullptr); string s; if (!(cin >> s)) return; build_from_string(s); long long best = 0; for (int i = 2; i <= tot; ++i) // i=1 为根 best = max(best, 1LL * st[i].sz * st[i].len); cout << best << '\n'; } };Update date: 2025-10-21 Author: GuWolf
什么是二分查找二分查找也叫折半搜索，是用来在一个有序数组中查找某一元素的算法。相较于线性查找,二分查找利用了数组的有序性质,通过调整边界快速缩减查找范围,大大提高了查找效率。线性查找时间复杂度:时间复杂度(最好) O(1)时间复杂度(最坏) O(n)二分查找时间复杂度:时间复杂度(最好) O(1)时间复杂度(最坏) O(logn)1. 整数二分的代码实现以升序数组为例int binarySearch(int arr[], int left, int right, int target) { while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) return mid; if (target > arr[mid]) left = mid + 1; else right = mid - 1; } return -1; } STL库里的二分C++ STL库里有两个查找函数std::lower_bound实现了查找首个不小于给定值的元素std::upper_bound实现了查找首个大于给定值的元素二者均采用二分查找，所以使用前应确保数组有序。传入参数first, last -要搜索部分范围的迭代器value -要与元素比较的值返回值指向范围首个符合条件的元素的迭代器，在找不到这种元素时返回last要得到符合条件的元素的下标只需要使用返回迭代器减去first即可比如--- int a[5] = {1,3,5,7,9}; int loc = lower_bound(a, a+5, 3) - a; // loc = 1 int loc = upper_bound(a, a+5, 3) - a; // loc = 2 ---
PS:页面右边有该文章的目录，可快捷跳转到对应位置目前该篇只介绍了三种排序算法:冒泡排序、插入排序、快速排序(极度推荐)。以及C++ STL里快排函数sort()的使用。1.冒泡排序1.1 算法介绍时间复杂度(平均) O(n²)时间复杂度(最好) O(n)时间复杂度(最坏) O(n²)空间复杂度 O(1)这应该是世界上知名度最广的一个排序算法了吧(也是时间复杂度最高的算法) ::twemoji:tilted::1.2 代码实现void bubbleSort(int arr[], int n) { for (int i = 0; i < n - 1; ++i) { for (int j = 1; j < n - i; ++j) { if (arr[j-1] > arr[j]) swap(arr[j-1], arr[j]); } } } 1.3 GIF原理图2.插入排序2.1 算法介绍时间复杂度(平均) O(n²)时间复杂度(最好) O(n)时间复杂度(最坏) O(n²)空间复杂度 O(1)2.2 代码实现void insertionSort(int arr[], int n) { for (int i = 1; i < n; ++i) { int key = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; --j; } arr[j + 1] = key; } }2.3 GIF原理图3.快速排序3.1 算法介绍时间复杂度(平均) O(nlogn)时间复杂度(最好) O(nlogn)时间复杂度(最坏) O(n²)空间复杂度 O(nlogn)快速排序采用了分治策略,通过一个pivot(基准值)将数组分成两部分,一部分小于pivot,一部分大于pivot。然后递归对两部分继续排序,直到数组有序。复杂度分析: 最坏情况下,每次pivot都位于边界,会导致递归树退化为链表,时间复杂度为O(n^2)平均情况下,递归树深度为O(logn),每层partition时间为O(n),所以平均时间复杂度为O(nlogn)3.2 代码实现int partition(int arr[], int left, int right) { int pivot = arr[right]; int i = left - 1; for (int j = left; j < right; ++j) { if (arr[j] < pivot) { ++i; swap(arr[i], arr[j]); } } swap(arr[i + 1], arr[right]); return i + 1; } void quickSort(int arr[], int left, int right) { if (left < right) { int pivot = partition(arr, left, right); quickSort(arr, left, pivot - 1); quickSort(arr, pivot + 1, right); } }3.3 GIF原理图没找到合适的动图，排序过程请看算法介绍4. C++ STL里的排序C++ 标准库里实现了排序的函数std::sort(),印象中其效率是和快排差不多的,该函数定义于头文件 <algorithm>传入参数:参数说明first,last要搜索部分范围的迭代器comp比较函数4.1 对数组进行升序排序sort默认排序顺序是升序#include <iostream> #include <algorithm> using namespace std; int main() { int a[10] = {1,5,9,8,7,5,3,2,6,4}; sort(a, a+10); for (int i = 0; i < 10; ++i) cout << a[i] << ' '; // 1 2 3 4 5 5 6 7 8 9 return 0; } 4.2 对数组进行降序排序这时候就需要自定义比较函数bool compare(int a, int b) { return a > b; } 然后再排序sort(a, a+10, compare); 4.3 对结构体数组进行排序同理自定义排序函数可以让我们对结构体进行排序bool compare(struct aaa A, struct aaa B) { if (A.a == B.a) return A.b > B.b; return A.a > B.a; } 然后再进行排序sort(aaa, aaa+10, compare); 猫猫说