魔法陣

六十年一次的魔法戰爭就要開始了，大魔法師準備從附近的魔法場中汲取魔法能量。 大魔法師有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物品的次數。

第一行包含兩個空格隔開的正整數n和m。

接下來m行，每行一個正整數，第i+1行的正整數表示Xi，即編號為i的物品的魔法值。

共輸出m行，每行四個整數。第i行的四個整數依次表示編號為i的物品作 為A,B,C,D物品分別出現的次數。

308

1

24

7

28

5

29

26

24

4 0 0 0

0 0 1 0

0 2 0 0

0 0 1 1

1 3 0 0

0 0 0 2

0 0 2 2

0 0 1 0

15 15

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

5 0 0 0

4 0 0 0

3 5 0 0

2 4 0 0

1 3 0 0

0 2 0 0

0 1 0 0

0 0 0 0

0 0 0 0

0 0 1 0

0 0 2 1

0 0 3 2

0 0 4 3

0 0 5 4

0 0 0 5

1＜=n＜=15000

1＜=m＜=40000

按官網的數據，無腦暴力O(m^4)+判可行性，能拿到30分。

但是，沒有無用的條件，沒有多給的限制。

如果你這麼打，n是幹嘛的？

一眼就要看出來應該桶排序。接着，本文後面所有提到的東西都與m無關。

於是時間複雜度降到了O(n^4)，這樣會有40分，但長進不大，在浙江還是拿不到省一。（就算你前三題全對）

再者就要意識到一個事情，如果Xa,Xb或者Xc,Xd確定了，另兩者之間的距離隨之確定。於是只需枚舉另兩者之中的一個。O(n^3)，似乎最多70分。

然而，根據題目描述，Xc、Xd之間距離不會超過n div 9。這樣就有了85分，前面再錯一點問題也不大。

滿分代碼與85分思想差不多，但是用前綴和把複雜度優化到了O(n^2)。

貼滿分代碼。

var

i,j,n,m,x,y:longint;

a,b,c,d,h,w:array[0..40005]of longint; // a[i]表示以魔法值i作為魔法陣中a元素的總方案，b,c,d以此類推

begin

readln(n,m);

for i:=1 to m do

begin

read(h[i]);

inc(w[h[i]]);

end;

for i:=1 to n div 9 do //枚舉c與d的距離

begin

x:=1+9*i; //x表示a—d的距離 y:=0;

for j:=2+9*i to n do //枚舉d,d定了，c就定了

begin

y:=y+w[(j-x)]*w[j-x+2*i];//w[j-x]:魔法陣為a元素的個數，w[j-x+2*i]：b元素的個數，

//因為是至少為9*i+1，所以在枚舉後面的d時，要將前面的所有a,b的情況累加起來

d[j]:=d[j]+y*w[j-i]; //a*b*c=d

c[j-i]:=c[j-i]+y*w[j];

//a*b*d=c,因為c與d的距離固定為i，所以確定d就可以確定c

end;

x:=8*i+1; //x表示a—c的距離 y:=0;

for j:=n-9*i-1 downto 1 do //枚舉a，a定了，b就定了

begin

y:=y+w[j+x]*w[j+x+i];

//w[j+x]：魔法陣為c元素的個數，w[j+x+i]:d元素的個數 a[j]:=a[j]+y*w[j+i+i];

b[j+i+i]:=b[j+i+i]+y*w[j];

end;

end;

for i:=1 to m dio

writeln(a[h[i]],' ',b[h[i]],' ',c[h[i]],' ',d[h[i]]);

end.