你需要在平面直角坐标系上进行 $q$ 次操作。每次操作有两种，要么放置一个两条直角边平行于坐标轴的等腰直角三角形，要么查询某一个点被多少个三角形覆盖。保证所有点的坐标都是整数且 $\in [1,n]$。$n \le 5 \times 10^3, q \le 10^5$。

题意大概就是有$n$个点，每个点其坐标$x_i,y_i$与权值$c_i$，其中$1\le n\le 5\cdot 10^5,0\le x_i,y_i\le 10^9,-10^6\le c_i\le 10^6$。

让你选一个正方形，该正方形的左下角及右上角必须在$y=x$这条直线上。所获得的权值为在正方形内的点的权值和减去正方形的边权。输出所获的最大权值及其选择正方形的左下角$x_1,y_1$及右上角$x_2,y_2$，要求$0\le x_1=y_1\le x_2=y_2\le 2\cdot 10^9$。

原题链接

有一趟列车有$M+1$个车站，从$0$到$M$编号。有$N$种商品，第$i$种只在编号$[l_i,r_i]$的车站出售。一辆列车有一个预设好的系数$d$，从$0$出发，只会在$d$的倍数车站停车。对于$d$从$1$到$M$的列车，求最多能买到多少种商品。

$1\le N \le 3\times 10^5;1\le M\le 10^5;1\le l_i\le r_i\le M$。

设计一个数据结构. 给定一个正整数数列$a_0, a_1, ..., a_{n - 1}$，你需要支持以下两种操作：

1. MODIFY id x：将$a_{id}$修改为$x$。
2. QUERY x：求最小的整数$p (0 \le p < n)$，使得$\gcd_{i=0}^pa_i\times \bigotimes_{i=0}^p a_i= x$。无解输出no。

$n \le 100000$，$q \le 10000$，$a_i \le 10^9 (0 \le i < n)$，QUERY x 中的$x \le 10^{18}$，MODIFY id x中的 $0 \le id < n$，$1 \le x \le 10^9$。

给下一届出题，自然是出得水一点比较好咯～

原题链接

有一个长度为$n(n\le 10^5)$的序列$\{a\}(a_i\le 10^5)$，你可以对它进行操作，操作如下：首先选择三个数$v, t, k$，满足$a_v = a_{v+t} = a_{v + 2t} = \cdots = a_{v + kt}$，然后将其删除，得到一个新的序列。每次操作结束后你都能将新数列重排。

现有$Q(Q\le 10^5)$个询问，每次询问$[l, r]$表示问要把$[l, r]$删除所需的最小步数。

和sxd出的大水题，T1T2大样例连续出锅快被表死了。