题意

题目链接

给你一个长、宽均为 $T$ 的网格图，左下角坐标为 $(0,0)$，右上角坐标为 $(T,T)$。现在图上面有 $n$ 个点（一定在格点上），你需要选择一些点，使得你选择的点按 $x$ 从小到大排序后 $y$ 也单调上升。最大化选的点的数量；在此基础上，让排序好的相邻的两点形成的矩形的面积之和最小。输出最小面积和。$T\leqslant 10^6,N\leqslant 2\times 10^5$。

一种亚线性复杂度求积性函数前缀和的筛法。

给定长为 $n$ 的序列 $h$，有 $q$ 次询问，每次询问在 $[l,r]$ 内找一个点 $x$，使得 $[l,r]$ 内每个点到 $x$ 之间最大值的和（即 $\sum\limits_{i=l}^x\max\limits_{j=i}^xh_j+\sum\limits_{i=x+1}^r\max\limits_{j=x}^ih_j$）最小。$n,q\leqslant 750000,h\leqslant 10^9$ 。

题目链接

题目链接

神仙题Orz

给定一张带边权的简单无向连通图，定义一棵生成树 $T$ 的权值为 $$val(T)=\left(\sum\limits_{i=1}^{n-1}w_{e_i}\right)\times\gcd(w_{e_1},w_{e_2},\dots,w_{e_{n-1}})$$ 求所有生成树的权值之和。

给出只包含小写字母 $a,b$ 的字符串 $s,t$，$q$ 次询问，每次询问 $s[l,r]$ 和 $t$ 的最长公共子串长度。$|s|,|t|,q\leqslant 2\times 10^5$。

A. FashionabLee

问是否可以通过旋转使得在平面直角坐标系中的正 $n$ 边形同时有至少一条边与 X 轴平行，有至少一条边与 Y 轴平行。