评论详情-牛客网

b诡异的因数

暴力试除法，强力试除即可。

c表单

$P.S.:$ 由于数据的问题读入的操作可能不是1,2

一个 $map$ 预处理，每次清0即可

d分数的运算

加减法通分，乘除法直接做。

g ftos的测试

##题解

可以发现，只修改一个数，所以如果有解，这个数一定减少了 $(\sum_{i=l}^r a_i)-\lfloor \sqrt {a_k} \rfloor$ 的值，

又因为没有修改，所以我们可以在一开始预处理 $a_i-\sqrt {a_i}$ 的值，然后我用的是分块，

对于这个差值我们进行块内排序处理，然后每次询问我可以块内二分upper和lower

然后在 $O(log_n)$ 找到满足减少了 $(\sum_{i=l}^r a_i)-k$ 的解的数量，对于边角料暴力就OK了

然后我们发现找到的这个数量有两种情况：

###情况一

这个数量=0，即无解

这好办，输出"Error"

###情况二

数量>0，有可能有唯一解，也有可能有多个解，如 $8-\lfloor \sqrt 8 \rfloor = 9-\sqrt 9$

因为 $a_i$ 比较小，所以我们桶排+块内二分判断头尾的 $a_i$ 是否相同。

如果做出来这些解的 $a_i$ 都是相同的输出"pass"

否则输出"INF"

这样做至少 $O(n\sqrt n log_n)$ 还有桶排清零的大常数，但是在 $3000ms$ 内还是能卡过去的。

##关于数据

数据是随机的，但是为了不全是Error，我们手动修改了数据。

##其他解法

线段树应该也是可以的，我们维护 $a_i$ 和 $a_i-\sqrt {a_i}$ ，然后方法与分块差不多，时间复杂度 $O(nlog^2 n)$

但是线段树代码太长了，本人懒得打（逃

如果有更好的解法敬请指出。

h 数据结构题

分块，块内排序二分找相同。很经典的题了。
线段树也同样可以。

j 开挂

$100pts:$

首先，我们发现

$\sum_{i=l}^r (a_i \times \sum_{j=i+1}^r a_j) = \sum_{i=l}^r \sum_{j=i+1}^r a_i \times a_j$

有没有觉得后面这个东西很熟?其实这个询问就是求区间的数两两相乘的和。

但是好像还是没法算啊！

我们再观察这个东西，又可以发现

$\sum_{i=l}^r \sum_{j=i+1}^r a_i \times a_j = \frac {1}{2} \times ((\sum_{i=l}^r a_i)^2-\sum_{i=l}^r a_i^2)$

其实就是区间和的平方减掉区间平方和的 $\frac{1}{2}$ 。

对于区间加，线段树维护一下和与平方和就好了，时间复杂度小到爆炸 $O(Q \log n)$ (实际的话因为数据随机，后面 $7$ 个点每个点标程跑的不到 $100ms$ ，开 $1000ms$ 都是出题人良心了)。

这个公式的来源其实就是

$(a_1+a_2+...+a_n)^2=a_1^2+a_2^2+...+a_n^2 + 2\sum_{i=1}^n \sum_{j=i+1}^n a_i \times a_j$

然后移项一下，提个式子，分解一下就是这道题了。