题意

题目链接

给你一个长、宽均为 \(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 轴平行。