陈年笔记，现在可能不会了。点分治Q1：基本思想是什么？将路径分为经过\(u\)和不经过\(u\)的两类，在每次分治中计算经过\(u\)的路径数量。Q2：如何统计？一般：遍历\(u\)的每个子节点\(v\)，把\(v\)子树内的节点记录下来，得到答案并更新数组。容斥：把\(u\)子树内的节点都记录下

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/?envType=study-plan-v2&envId=top-interview-150gopackageleetcode150import("testing")funcTestMaxProfit(t*testing.T){prices:=[]int{2,1,2,0,1}

考虑去枚举能满足\(1,2\)的个数\(l\)，那自然只能满足\(1\)或\(2\)的个数为\(\max\{k-l,0\}\)。对于还剩下的，可以从只能满足\(1,2\)和不能满足任意一个的选出来。显然如果要选就是选最小的。考虑用个数据结构优化这个过程。查询前\(k\)大的和，插入一个数，可以想

点分治适合处理大规模的树上路径信息。实现取一个中心点计算跨过中心点的贡献。（lsy说得精辟但抽象）先随便指定一个根\(rt\)，我们能将树上的路径分为经过\(rt\)的路径和包含于\(rt\)的某棵子树内的路径（不经过\(rt\)）。对于经过当前根节点的路径，又可以分为两种，一种是以根节

[AGC044E]RandomPawn题解题目链接AtCoder原题链接Step1.拆环原问题是在环上的问题，考虑将环拆开变成链来处理。因此，我们需要找到一个点，使得操作越过这个点一定不优。令使\(a\)的值最大的位置的下标为\(maxp\)。容易发现，如果现在正处在\(maxp\)上，那么继续操作一定不可

首先考虑暴力的贪心。从\(r\)到\(l\)依次遍历，若\(a_i<x\)则一直进行题目中的操作。正确性是能保证的，因为选后面的\(j\)只能\(+1\)，而选\(i\)可以\(+2\)，且\(i\)前面的部分都是\(+1\)。考虑转化一下，把对\(i\)进行操作\(k\)次后，\(\forallj\in[1,i),a_j\l

思路我们实际上发现它计算的就是\(p_i\cdoti\)的和再减去一个\(p_i\cdoti\)中的最大值。那我们可以枚举这个最大值\(p_x\cdotx\)，这个值就是最后和中需要删除的数值。这里我们可以使用贪心。我们可以从\(n\sim1\)枚举除\(p_i\)的每个数字需要配的数字。当然，

牛逼题。先考虑\(l\le10^5,10^5+1\ler\)的部分分：一种方法是线段树，即因为左右端点是独立的，因此对左右端点各维护一个权值线段树表示有多少个区间以这个值为左/右端点，这样对于修改，左端点的部分相当于先查询\(\lel\)的数的个数，然后将它们都挂到\(l\)上，最后把\(<l\)的部

考虑建出AC自动机，朴素做法是高斯消元，\(f_i=\sum\limits_{j=0}^{k-1}f_{to_{i,j}}p_j+1\)，复杂度\(O(n^3m^3)\)，不能接受。考虑优化高斯消元的过程，我们定义以下节点为“关键点”：根节点对于一个trie树（也就是未经过AC自动机getfail操作得到的树）上有超过两个儿子的节点\(x

https://www.luogu.com.cn/problem/P8292题解先把小于等于\(\sqrt{2000}\)的质数打一个表,发现只有\(14\)个,其中第\(14\)个是\(43\).令前\(14\)个质数为小质数,其它的

结论是：答案为\(2^n\)。后手能使结果至多为\(2^n\)：将\(2n\)个格子两两分一组，共\(n\)组。先手每选一组中的某个，后手就跟着选另一个。这样至多有\(2^{n}\)种结果。

对于dp[i]，如果nums[i-1]>0，dp[i-1]也>0，那就是dp[i-1]*nums[i-1]如果<0，>0，那就是nums[i-1]0，<0，那就是nums[i-1]<0，<0，那就是dp[i-1]*nums[i-1]同样参考最大子数和，还需