六十年一次的魔法战争僦要开始了大魔法师准备从附近的魔法场中汲取魔法能量。
大魔法师有m个魔法物品编号分别为1,2,…,m。每个物品具有一个魔法值我们用Xi表示编号为i的物品的魔法值。每个魔法值Xi是不超过n的正整数可能有多个物品的魔法值相同。
大魔法师认为当且仅当四个编号为a,b,c,d的魔法粅品满足xa<xb<xc<xd，Xb-Xa=2(Xd-Xc)并且xb-xa<(xc-xb)/3时，这四个魔法物品形成了一个魔法阵怎么做他称这四个魔法物品分别为这个魔法阵怎么做的A物品，B物品C物品，D物品
现在，大魔法师想要知道对于每个魔法物品，作为某个魔法阵怎么做的A物品出现的次数作为B物品的次数，作为C物品的次数和作為D物品的次数。

---

---

我们可以把每一个物品放到一个数轴上然后枚举x,再枚举A，就可以算出B
但我们没法去枚舉6x~n去算C和D。
我们发现可以倒过来枚举A然后直接找最小的C，也就是A+8x+1
那么对于每一个新的A，以前出现的C肯定都是是合法的
于是我们用一個后缀和y去维护C*D，就可以算出ansA和ansB了
显然，x≤n/9所以时间复杂度就是o(n2/9)

发布了57 篇原创文章 · 获赞 61 · 访问量 2万+