Należy odpowiedzieć na $q$ zapytań, każde o sumę liczb z pól znajdujących się w prostokącie, którego przeciwległe wierzchołki są w polach $(x_1,y_1)$ oraz $(x_2,y_2)$.
Podzadanie 1 możemy rozwiązać, rysując całą spiralę w tablicy dwuwymiarowej. Następnie stosujemy dwuwymiarowe sumy prefiksowe, które pozwalają obliczać sumę liczb w dowolnym prostokącie zawartym w tablicy w czasie stałym.
Złożoność czasowa tego rozwiązania to $O(n^2 + q)$:
const int N = 1100, MOD = 1000000007; int n,q; int b[2*N+1][2*N+1]; int dp[2*N+2][2*N+2]; int main() { scanf("%d%d",&n,&q); int x=n, y=n, dist=1, k=1; b[y][x++] = k++; REP(i,n) { REP(j,dist) { b[y++][x] = k++; } REP(j,dist+1) { b[y][x--] = k++; } REP(j,dist+1) { b[y--][x] = k++; } REP(j,dist+2) { b[y][x++] = k++; } dist += 2; } REP(y,2*n+1) REP(x,2*n+1) { dp[y+1][x+1] = (ll(dp[y+1][x]) + dp[y][x+1] + MOD - dp[y][x] + b[y][x]) % MOD; } for (int i=0; i<q; ++i) { int x1,y1,x2,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2); x1 += n; y1 += n; x2 += n; y2 += n; x2++; y2++; int ans = (ll(dp[y2][x2]) + MOD - dp[y1][x2] + MOD - dp[y2][x1] + dp[y1][x1]) % MOD; printf("%d\n",ans); } }
W podzadaniu 2 każde zapytanie dotyczy jednego pola. Niech $m=\max(|x_1|,|y_1|)$, czyli jest to minimalny rozmiar kwadratu (zaczepionego w środkowym polu), w którym znajduje się szukane pole. Zatem w środku tego kwadratu znajduje się $(2m-1)^2$ pól, a szukane pole jest na jednym z czterech boków. Wystarczy zatem odpowiednio rozważyć cztery przypadki, aby uzyskać odpowiedź na zapytanie w czasie stałym.
Tak więc złożoność czasowa to $O(q)$:
int calculate(int x, int y) { ll m = max(abs(x), abs(y)); if (m == 0) { return 1; } ll s = (2*m-1) * (2*m-1) % MOD; ll ans; if (y == -m) { ans = s+6*m + x+m; } else if (x == -m) { ans = s+4*m + -y+m; } else if (y == m) { ans = s+2*m + -x+m; } else { ans = s+1 + y+m-1; } return ans % MOD; }
Kartkę papieru z usuniętą środkową kratką dzielimy na cztery ćwiartki. Ćwiartka 0 zawiera liczby $2, 11, 28\ldots$ oraz liczby powyżej nich, ćwiartka 1 zawiera liczby $4, 15, 34\ldots$ oraz te na lewo, ćwiartka 2 zawiera liczby $6, 19, 40\ldots$ oraz te poniżej, a ćwiartka 3 zawiera liczby $8, 23, 46\ldots$ oraz te na prawo. Powiemy, że powyżej wymienione liczby leżą na głównym wierszu ćwiartki (zacienionym na poniższym rysunku):
Teraz możemy rozwiązać zadanie niezależnie dla każdej ćwiartki (rozpatrując przecięcie prostokąta z daną ćwiartką) i zsumować uzyskane wyniki (plus uwzględniając ewentualny wkład ze środkowego pola z liczbą 1). Dodatkowo możemy założyć, że prostokąt zawiera kratkę z najmniejszą liczbą w ćwiartce (w przeciwnym wypadku to kwestia prostych operacji arytmetycznych na wkładzie z czterech takich prostokątów).
W rozwiązaniu będziemy obliczać sumy potęg kolejnych liczb naturalnych. Oznaczmy to ogólnie przez \begin{equation*} P_r(m) = \sum_{1\leq i\leq m} i^r, \end{equation*} a w szczególności przydadzą się nam wzory pozwalające obliczać je w czasie stałym: \begin{equation*} P_1(m) = \frac12 m(m+1),\qquad P_2(m) = \frac16 m(m+1)(2m+1),\qquad P_3(m) = \frac14 m^2(m+1)^2. \end{equation*}
Oznaczmy przez $A(k,i)$ (dla $0\leq k\leq 3$, $0\leq i$) $i$-tą liczbę w głównym wierszu ćwiartki o numerze $k$. Wypisując sobie ciągi różnicowe dla tych wierszy, możemy zgadnąć następujący wzór: \begin{equation*} A(k,i) = 1 + (2k+1)(i+1) + 8P_1(i). \end{equation*}
Załóżmy, że prostokąt ma rozmiar $h\times w$ kratek (dla ćwiartki 0 to oznacza prostokąt o wysokości $h$ i szerokości $w$, dla każdej kolejnej ćwiartki jest on obrócony o $90^\circ$). Rozważmy najpierw przypadek $w \geq h-1$. Wtedy spiralę zawartą w prostokącie można podzielić na $w$ kawałków, z których każdy zaczyna się liczbą z głównego wiersza i zawiera kolejne liczby naturalne (więc jest opisany początkową liczbą i swoją długością). Oznaczmy przez $S(k,i,\ell)$ sumę liczb w kawałku zaczynającym się $i$-tą liczbą o długości $\ell$. Wtedy \begin{equation*} S(k,i,\ell) = A(k,i) \cdot \ell + P_1(\ell-1). \end{equation*}
Oznaczmy jeszcze $\gamma_k = [k=3]$ (nawias Iversona). Pierwsze $h-1-\gamma_k$ kawałków mają po jednym zakręcie, a $i$-ty z nich ma długość $2i+2+\gamma_k$. Pozostałe kawałki są proste i mają długość $h$. Więc suma liczb w prostokącie wynosi \begin{equation*} S_{\geq}\ =\ \sum_{0\leq i < h-1-\gamma_k} S(k,i,2i+2+\gamma_k)\ +\ \sum_{h-1-\gamma_k\leq i < w} S(k,i,h). \end{equation*}
W przypadku $w < h-1$ jest trochę trudniej. Mamy $w$ kawałków z zakrętem, a dodatkowo $h-1-w-\gamma_k$ kawałków poziomych o długości $w$, z tym że nie zaczynają się one liczbami z głównego wiersza ćwiartki. Można jednak zrobić następujący trik: ponieważ kończą się one liczbą tuż przed głównym wierszem następnej ćwiartki, można od tej liczby policzyć $w$ liczb poprzednich. Da to następujący wzór: \begin{equation*} S_{<}\ =\ \sum_{0\leq i<w} S(k,i,2i+2+\gamma_k)\ +\ \sum_{w+\gamma_k\leq i<h-1} -S((k+1)\bmod 4, i, -w). \end{equation*}
Wzory te pozwalają rozwiązać podzadanie 3 w czasie $O(n)$:
const int M = 1000000007; int n,x1,Y1,x2,y2; ll sum; ll P1(ll m) { if (m % 2 == 0) return ((m/2) * (m+1)) % M; return (m * ((m+1)/2)) % M; } ll S(ll k, ll i, ll l) { ll r = 2*M; r = (r + 2*k+2) % M; r = (r + i * (2*k+5)) % M; r = (r + 4*i*i) % M; r = (r * l) % M; r = (r + P1(l-1)) % M; return r; } ll rog_cwiartka(ll k, ll w, ll h) { ll sum = 2*M; int g = k==3; if (w >= h-1) { for(int i=0;i<h-1-g;++i) sum += S(k,i,2*i+2+g); for(int i=h-1-g;i<w;++i) sum += S(k,i,h); } else { for(int i=0;i<w;++i) sum += S(k,i,2*i+2+g); for(int i=w+g;i<h-1;++i) sum += -S((k+1)%4,i,-w); } return sum % M; } ll cwiartka(int k, int x1, int Y1, int x2, int y2) { return rog_cwiartka(k, x2, y2) - rog_cwiartka(k, x2, Y1) - rog_cwiartka(k, x1, y2) + rog_cwiartka(k, x1, Y1); } void obroc(int& x1, int& Y1, int& x2, int& y2) { int nx1 = Y1, nY1 = -x2, nx2 = y2, ny2 = -x1; x1 = nx1; Y1 = nY1; x2 = nx2; y2 = ny2; } int main() { int q; scanf("%d",&n); scanf("%d", &q); while (q--) { scanf("%d%d%d%d",&x1,&Y1,&x2,&y2); sum = 2*M + int(x1 <= 0 && 0 <= x2 && Y1 <= 0 && 0 <= y2); for (int k=0; k<4; ++k) { sum += cwiartka(k, max(1,x1)-1, max(0,Y1), max(1,x2+1)-1, max(0,y2+1)); obroc(x1, Y1, x2, y2); } printf("%lld\n",sum % M); } }
Aby uzyskać szybsze rozwiązanie, rozwiniemy sumy w tych wzorach. Skorzystamy z ogólnej reguły sumowania wartości wielomianu w kolejnych punktach: \begin{equation*} \sum_{0\leq i<m} (a_0 + a_1 i + a_2 i^2 + a_3 i^3) = a_0 m + a_1 P_1(m-1) + a_2 P_2(m-1) + a_3 P_3(m-1). \end{equation*}
Grupując współczynniki we wzorach na $A$ i $S$ względem potęg $i$, dostajemy: \begin{equation*} \begin{split} A(k,i) &= (2k+2) + (2k+5)i + 4i^2, \\ S(k,i,\ell) &= (2k+2)\ell + P_1(\ell-1) + (2k+5)\ell i + 4\ell i^2, \\ S(k,i,2i+2+\gamma_k) &= \frac12(2+\gamma_k)(2k+5+\gamma_k) + (8k+2k\gamma_k+7\gamma_k+17)i + 4(k+\gamma_k+5)i^2 + 8i^3. \end{split} \end{equation*}
Zatem sumy dla prostych kawałków i kawałków z zakrętem są następujące: \begin{equation*} \begin{split} T_P(k,m,\ell) &= \sum_{0\leq i<m} S(k,i,\ell) = ((2k+2)\ell + P_1(\ell-1)) m + (2k+5)\ell P_1(m-1) + 4\ell P_2(m-1), \\ T_Z(k,m) &= \sum_{0\leq i<m} S(k,i,2i+2+\gamma_k) = {} \\ &= \frac12(2+\gamma_k)(2k+5+\gamma_k)m + (8k+2k\gamma_k+7\gamma_k+17) P_1(m-1) + {}\\ &\quad\quad\quad{}+ 4(k+\gamma_k+5) P_2(m-1) + 8P_3(m-1). \end{split} \end{equation*}
Ostatecznie daje to wzory pozwalające rozwiązać zadanie w czasie stałym: \begin{equation*} \begin{split} S_{\geq} &= T_Z(k,h-1-\gamma_k) + T_P(k,w,h) - T_P(k,h-1-\gamma_k,h), \\ S_{<} &= T_Z(k,w) - T_P((k+1)\bmod 4,h-1,-w) + T_P((k+1)\bmod 4,w+\gamma_k,-w). \end{split} \end{equation*}
ll A(ll a, ll b) { a %= M; b %= M; return (a+b) % M; }
ll B(ll a, ll b) { a %= M; b %= M; return (a*b) % M; }
ll oblicz(vector<ll> mnoz, vector<int> p_dziel) {
for (int i = 0; i < (int)p_dziel.size(); i++) {
bool ok = false;
for (int j = 0; j < (int)mnoz.size(); j++)
if (mnoz[j] % p_dziel[i] == 0) {
mnoz[j] /= p_dziel[i];
ok = true;
break;
}
assert(ok);
}
ll r = 1;
for (int i = 0; i < (int)mnoz.size(); i++)
r = B(r, mnoz[i]);
return r;
}
ll P1(ll m) { return oblicz({m, m+1}, {2}); }
ll P2(ll m) { return oblicz({m, m+1, 2*m+1}, {2, 3}); }
ll P3(ll m) { return oblicz({m, m, m+1, m+1}, {2, 2}); }
ll TP(ll k, ll m, ll l) {
return (B(A(B(2*k+2, l), P1(l-1)), m) + B(B(2*k+5, l), P1(m-1))
+ B(B(4, l), P2(m-1))) % M;
}
ll TZ(ll k, ll m, ll g) {
return (oblicz({4*k+5+g, 2+g, m}, {2})
+ B(A(A(A(B(8, k), B(2, B(k, g))), B(7, g)), 17), P1(m-1))
+ B(B(4, g+k+5), P2(m-1))
+ B(8, P3(m-1))) % M;
}
ll rog_cwiartka(int k, int w, int h) {
ll sum = 0;
int g = k==3;
if (w >= h-1) {
sum = (TZ(k,h-1-g,g) + TP(k,w,h) - TP(k,h-1-g,h) + M) % M;
} else {
sum = (TZ(k,w,g) - TP((k+1)%4,h-1,-w) + TP((k+1)%4,w+g,-w) + M) % M;
}
return sum;
}