看到网上有许多快速排序和快速选择的代码，但是相当一部分都有些错误，这里放一下自己的写法
快速排序模板题：https://www.luogu.com.cn/problem/P1177
快速选择模板题：https://vjudge.net/problem/POJ-2388
#include <cstdio>#include <cstdlib>#include <algorithm>using namespace std;const int maxn = 1e6 + 5;int n, a[maxn];void kth_element(int * l,
题目描述给定一棵n个点的树，点带点权。 有m次操作，每次操作给定x,y，表示修改点x的权值为y。 你需要在每次操作之后求出这棵树的最大权独立集的权值大小。 输入输出格式输入格式： 第一行，n,m，分别代表点数和操作数。 第二行，V1,V2,...,Vn，代表nn个点的权值。 接下来n−1行，x,y，描述这棵树的n−1条边。 接下来m行，x,y，修改点x的权值为y。 输出格式： 对于每个操作输出一行一个整数，代表这次操作后的树上最大权独立集。 保证答案在int范围内 输入输出样例输入样例#1： 复制10 10
-11 80
题目背景这是一道简单的AC自动机模板题。 用于检测正确性以及算法常数。 为了防止卡OJ，在保证正确的基础上只有两组数据，请不要恶意提交。 管理员提示：本题数据内有重复的单词，且重复单词应该计算多次，请各位注意 题目描述给定n个模式串和1个文本串，求有多少个模式串在文本串里出现过。 输入输出格式输入格式： 第一行一个n，表示模式串个数； 下面n行每行一个模式串； 下面一行一个文本串。 输出格式： 一个数表示答案 输入输出样例输入样例#1： 复制2
a
aa
aa 输出样例#1： 复制2 说明subtask1[50pts
题目描述给出两个n位10进制整数x和y，你需要计算x*y。 输入输出格式输入格式： 第一行一个正整数n。 第二行描述一个位数为n的正整数x。 第三行描述一个位数为n的正整数y。 输出格式： 输出一行，即x*y的结果。（注意判断前导0） 输入输出样例输入样例#1： 复制1
3
4 输出样例#1： 复制12 说明数据范围： n<=60000 来源：bzoj2179 本题数据为洛谷自造数据，使用CYaRon耗时5分钟完成数据制作。 寻找了很久，最终还是发现算法导论的FFT讲解的是最详细的，前置技能：复数四则运算，矩阵
题目背景这是一道经典的Splay模板题——文艺平衡树。 题目描述您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1 输入输出格式输入格式： 第一行为n,m n表示初始序列有n个数，这个序列依次是(1,2,⋯n−1,n) m表示翻转操作次数 接下来m行每行两个数 [l,r] 数据保证 1≤l≤r≤n 输出格式： 输出一行n个数字，表示原始序列经过m次变换后的结果 输入输出样例
题目描述如题，已知一个数列，你需要进行下面两种操作： 1.将某区间每一个数加上x 2.求出某区间每一个数的和 输入输出格式输入格式： 第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。 第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。 接下来M行每行包含3或4个整数，表示一个操作，具体如下： 操作1： 格式：1 x y k 含义：将区间[x,y]内每个数加上k 操作2： 格式：2 x y 含义：输出区间[x,y]内每个数的和 输出格式： 输出包含若干行整数，即为所有操作2的结果。 输入输出样例输入样例
题目描述如题，已知一棵包含N个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作： 操作1： 格式： 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z 操作2： 格式： 2 x y 表示求树从x到y结点最短路径上所有节点的值之和 操作3： 格式： 3 x z 表示将以x为根节点的子树内所有节点值都加上z 操作4： 格式： 4 x 表示求以x为根节点的子树内所有节点值之和 输入输出格式输入格式： 第一行包含4个正整数N、M、R、P，分别表示树的结点个数、操作个数、根节点序号和取模数（即所有的输出结果均对此取模）。 接下来一行包含N个非负整数，分别依次
题目描述如题，给定N个字符串（第i个字符串长度为Mi，字符串内包含数字、大小写字母，大小写敏感），请求出N个字符串中共有多少个不同的字符串。 友情提醒：如果真的想好好练习哈希的话，请自觉，否则请右转PJ试炼场:)输入输出格式输入格式： 第一行包含一个整数N，为字符串的个数。 接下来N行每行包含一个字符串，为所提供的字符串。 输出格式： 输出包含一行，包含一个整数，为不同的字符串个数。 输入输出样例输入样例#1：5
abc
aaaa
abc
abcc
12345 输出样例#1：4 说明时空限制：1000ms,128M 数据规模： 对于30
题目描述如题，已知一个数列，你需要进行下面两种操作： 1.将某区间每一个数数加上x 2.求出某一个数的和 输入输出格式输入格式： 第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。 第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。 接下来M行每行包含2或4个整数，表示一个操作，具体如下： 操作1： 格式：1 x y k 含义：将区间[x,y]内每个数加上k 操作2： 格式：2 x 含义：输出第x个数的值 输出格式： 输出包含若干行整数，即为所有操作2的结果。 输入输出样例输入样例#1：5 5
题目背景这是个非常经典的主席树入门题——静态区间第K小 数据已经过加强，请使用主席树。同时请注意常数优化 题目描述如题，给定N个正整数构成的序列，将对于指定的闭区间查询其区间内的第K小值。 输入输出格式输入格式： 第一行包含两个正整数N、M，分别表示序列的长度和查询的个数。 第二行包含N个正整数，表示这个序列各项的数字。 接下来M行每行包含三个整数l, r, kl,r,k , 表示查询区间[l, r][l,r]内的第k小值。 输出格式： 输出包含k行，每行1个正整数，依次表示每一次查询的结果 输入输出样例输入样例#1：5&nbs
Rockdu's Blog