模板

P1439 【模板】最长公共子序列（洛谷题面） 题目 题目描述： 给出 1,2,…,n1,2,\ldots,n1,2,…,n 的两个排列 P1P_1P1​ 和 P2P_2P2​ ，求它们的最长公共子序列。 输入格式： 第一行是一个数 nnn。 接下来两行，每行为 nnn 个数，为自然数 1,2,…,n1,2,\ldots,n1,2,…,n 的一个排列。 输出格式： 一个数，即最长公共子序列的长度。 数据范围与说明： 对于 50%50\%50% 的数据， n≤103n \le 10^3n≤103； 对于 100%100\%100% 的数据， n≤105n \le 10^5n≤105。 输入输出样例 #1 输入： 1235 3 2 1 4 51 2 3 4 5 输出： 13 题意 给定 1…n1 \ldots n1…n 的两个排列 P1P_1P1​、P2P_2P2​，求它们的最长公共子序列（LCS）长度。 思路 经典做法是 O(n2)O(n^2)O(n2) 动态规划，但对于 n≤105n \le 10^5n≤105 的数据会超时。利用“两个序列都是排列”的性质，可以将...

【模板】单调栈（P5788） 题目 题目描述： 给出项数为 nnn 的整数数列 a1…na_{1 \dots n}a1…n​。 定义函数 f(i)f(i)f(i) 代表数列中第 iii 个元素之后第一个大于 aia_iai​ 的元素的下标，即 f(i)=min⁡i<j≤n,aj>ai{j}f(i)=\min_{i<j\leq n, a_j > a_i} \{j\}f(i)=mini<j≤n,aj​>ai​​{j}。若不存在，则 f(i)=0f(i)=0f(i)=0。 试求出 f(1…n)f(1\dots n)f(1…n)。 输入格式： 第一行一个正整数 nnn。 第二行 nnn 个正整数 a1…na_{1\dots n}a1…n​。 输出格式： 一行 nnn 个整数表示 f(1),f(2),…,f(n)f(1), f(2), \dots, f(n)f(1),f(2),…,f(n) 的值。 数据范围与说明： 【数据规模与约定】 对于 30%30\%30% 的数据，n≤100n\leq 100n≤100； 对于 60%60\%60%...