description
给定一个长度为 \(n\) 的数组 \(a\)，求有多少对 \(i,j,k(1\leq i<j<k\leq n)\) 满足 \(a_k-a_j=a_j-a_i\)
\(n\leq 10^5\)
值域大小 3e4.
solution
三个数，看起来就不好用数据结构维护。
\(2a_j=a_i+a_k\) 可以当做多项式两项的指数相加得到指数为 \(2a_j\) 的项。由于 \(i,j,k\) 有大小顺序，不好直接构造多项式统计，也难分治做。
由于序列长度只有 \(1e5\) 直接分块。对于 \(i,j,k\) 中至少两个在同一个块中的情况，不难 \(O(n\sqrt{n})\) 枚举得到它们对答案的贡献。
然后考虑 \(i,j,k\) 不在同一个块中的情况。设 \(belong(x)\) 表示 \(x\) 所在的块从左往右的编号。枚举块编号 \(t\)，构造多项式 \(A(x)=\sum \sum\limits_{belong(p)<t} [a_p=i] x^i\) 以及 \(B(x)=\sum \sum\limits_{belong(p)>t} [a_p=i] x^i\)。计算他们的乘积。然后扫描块 \(t\) 中的元素 \(a_i\)，将多项式乘积的次数为 \(2a_i\) 的项的系数加到答案中即可。
时间复杂度 \(O(m\sqrt{n}+n\sqrt{n})\)，\(m\) 是值域大小。
code
参考代码链接：BZOJ By Hydro OJ
标签：3509,多项式,sum,belong,sqrt,2a,BZOJ From： https://www.cnblogs.com/FreshOrange/p/17715705.html