page1 Simpson各种优化主要是加速图形与直线的求交过程复

Author:

BZOJa-TheR-PeriodsofWordso-ProfessorSzut-Tetriss-Theg-t

y 。复杂度nlogn搜索。精确覆盖问题。dancinglinks n^2logn平衡树(跳表)nlogn??len+tlogn使用STL中的rope。注意不要一个字符一个字符输出，要 nlogn， 输出复杂度len+tlogn。move可过。??nlogn^2n^2logn使用并查集,n^2α(n)dist:逐行扫描，每列上的点只有离这行最近的才有用。单调队列，斜率优化。复杂度n^2?xy，求出(xi+yi)/2和(xi-yi)/2的中位数,分别作为(x+y)/2和(x-y)/2。但为了保证xy都是整数，11就行了，nlognO(n)V1、V2X1-V1-Y1、X2-V2-Y2均为一条

如图，设X0,X1,...,Xn是当前解中的一条链，Y0,Y1,..Ym是原树的最长链（m>nX0、，Xk链的中点?)2l-1条路径使得覆盖的点最多，n+llogn或O(n)。。x到叶子方向的最长链，id[x]xx-id[x]路径上的点标为已，每次只收缩未点向下的最长链。正确性的证明也很容易。n+l*lognO(n)。正确性证明比刚才的还要直接。用桶来叶链，就可以做到O(n)。L>1时应该怎么办呢？中的叶子节点全部删除，得到树T2……如此重复下去，直到第k次得到的树Tk中只有1个或2L求最小值，最后再求一次和就可以了。j-The分别以凸包上每个为基准点，对凸包作三角剖分。f[i][j][k]ij-k个三角S[i][j]i为基准点，第j-k个三角形内的点权和。按极角排序，O(m)s[i][?]。sO(m)f后就O(1)得到三角形内的点权和了。最后枚举三角形的三个顶点，O(1)得出点权和。复杂度n*mlogm+n^3/n*m+n^3k-?k-费用流/KMt?yBZOJ1442：[Poi2006]Crystals?l的逆序插入字母树中(注意空间问题，可使用块状链表/链表/mapBZOJ不卡空间)，枚举rev(B)C的分C是回文串(Manacher判断)且在字母树中找到了rev(B),则更新答案。注意到当分割点向右移动时O(L)L*|Σ|Llog|Σ|Lsqrt(|Σ|)sn-记录每个在i之后最早出现某个数字是在什么地方，然后枚举所有可能的编码，判断否符合这段。当某个编码符合的数达到n时++ans。复杂度10^4*nn-?m-Toy?aPiggy设i的在j里，则j向i连一条边。构成的图所有点的入度为1，出度任意。若连通块中o-knightnkn*klogk单调队列n*ks-二分答案，最大流。把每场比赛作为一个点，Smid21T1t-AJourneyto单调队列。复杂度O(n)m-Fibonacci2：ifa[0]=1thena[11a-Tem相邻两个下标的距离<=i+1j长度覆盖所有的充要条件。非减的，所以用个变量最大值即可。c-Specialnlogn^2(即x坐标x)n^2。t-The扫描线，平衡树DP。复杂度nlogna-Twou-Double-?i-?s-Mirror?1016:[JSOI2008]?ronmanRaceinnlogn^2angingtheoboticnlogn2913:[Poi1997]XORGatesk大的是几：f(x,s)1-xs的数的个数。数位DP。先二分出答案的f判断。1nk是第几大的:f11018252627283032353943475156616798711122344556111224445533的两个数可以归k个“单独值”k/2k个“单独值”，会产生(k+1)/2个等差数列。线段树的节点上记录9个值：左右孩子l,r，左端值le，右端值re，左端单独值的个数ld，右datadd。nlognjmask这个状态的串有多少个，直接进行DP就可以了，但是比较麻烦42的时候才要求输出，于是可以dfs直接从DP终止状态回溯，每次从一个状态拓展时，dfs注意到如果AB，BC显然不会用AC...从上到下，从左到右考虑，那么每列最多一个是有用的人小DPnlogn。我们需要q，队列中每个元素 i，以决策i为优决策的位置的左端点l，右端点r。对于每个i，我们依次执行以下三步操作：取队头元素为最优决策，计算出f[i]将i从队列的 i为最优决策的区间，删除队尾元素(队尾指针-1);若对于队尾元素的右ii加入队列。n^4，Ba2b2A方法得到的结果相同。显然a1+b1=a2+b2f[a1,b1,a2]n^3lueMary二分答案，hashn^2logn。2.f[i,j,k,l]表示以A的(i,j)、B的(k,l)为右下角的最大边长lueMarynlogn线段树nlognnlognlueMarylueMaryOpen]f[i,j]ij的情况下，所能滑的最大距离。f[i,j]f[i+1,j],],j]pre[j]j有多门课程！转移方法：f[ij]转移到f[i+L[kA[k]]L[k]、A[k]分别为当天某个课程的Open] +1就nlognOpen]求出每条直线与圆的交点，排序后边扫描边树状数组。复杂度nlognJan]损坏Jan]f[i,j]jiiJan]径上的最后一条边上。问牛i在不遇到小的前提下从起点到达牛棚i的最短路径。ShortestPathTreevpparent1号点到v的不经过(p,v)的ShortestPathTree1v1号点先v，这条路径上不能有边(p,v)v的边，后通过边(u,v)v。uuv，1uShortestPathTreev走。1->uu)ShortestPathTree的叶子结点（深度最大，然后处理深度次大的点……重复此过程，直到根（1号点）处理完。叶子节点的处理方法，叶子节点不会出现情况二。对于叶子结点vv相邻的点放在一个堆里（为什么用堆之后讨论uudist[u]+w(u,v)。dist[u]1->u的最短路径（不考虑是否经过(p,v)1->v的答案。如果所要处理的节点v不是不是叶子节点，那么还有可能出现情况二。先类似叶子节点处理v的每个childu1->u的结果求出来。根据我们的处理顺序，这一点能uuw(u,v)vw(u,v)uu的路径，需要再走一步(u,v)v。还有，1->uv的descendant作为中间节点，这是不符合要求的答案，要从堆v中删除。nlognnlogn^2。2.首先不考虑小，用spfa或堆优化的dijkstra求出“最短路径树也就是通过这棵树上uv开始，在最短路径树上不断向各自的父亲节点移动这两个点，vlen-dis[u(v)]更新ans[u(v)]，同时把这个点向上移动到其父亲节点，重复上述操作直到u=v。注意到如果仅仅这样做，时间复杂度还是太高。由于我们已经把环nlogn+nα(n)Feb]用堆。复杂度nlogn或nloglognFeb]StockFeb]RevamK(最多更新次数)*k(期望为常数)*m(用spfa)/Km+Knlogn(dijkstra+fibonacci堆)dijkstraHol]Cattle nlogn。Hol]TransmissionDP。f[i][j]ij0的情况下，有多少种可能的输出f[n][k]=f[i][j]+=f[i+1][j+1]iff|j<A|&&|pos0[j]-i|<=df[i][j]+=f[i+1][j]iff|i-j<B|&&|pos1[i-j]-Hol]Holiday--1515*nlognMar]MoonDP。复杂度O(n)Mar]Cleaning每一步f[i]表示不度为i的最前面的数的位置。显然i<=sqrt(n)。复杂度nsqrt(n)。ythonMar]Earthquake其中(x,y)key[x][y]的特殊点，key[x][y]>prev>=totisum{f[r][c][i][j]}j>=iDP。f[i][j]ij堆的答案。枚举上一堆，前缀和。复杂度n^2*ksetnlognnlognO(n+W)Dec]TrickorTreatDP+环。复杂度O(n)Dec]SecretDec]Largest处理)n^3lognn^3Feb]Makingthenlognp[i]i结点对应的线段的左端点。2i，ld[i+i]+rd[i+i+1]>=d是否成立，成立则找到答案；lognmlogn2.用平衡树每段连续的空位。操作1：一段空位因为合并的次数不会多于的次数，所以复杂度nlognJan]nlogq+qlogq^2Jan] 从题目可以知道，草地的连接是一棵树。树形DPO(n)3f[p][0]=∑min{f[p.son][0..2]f[p][1]=∑min{f[p.son][0..1]]<=f[p.son][0]-f[p.son][