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})$ .

Rozwiązanie brutalne

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);
  }
}

Jedno pole

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ę $(2 m - 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;
}

Rozwiązanie w czasie liniowym

Kartkę papieru z usuniętą środkową kratką dzielimy na cztery ćwiartki. Ćwiartka 0 zawiera liczby $2, 11, 28 \dots$ oraz liczby powyżej nich, ćwiartka 1 zawiera liczby $4, 15, 34 \dots$ oraz te na lewo, ćwiartka 2 zawiera liczby $6, 19, 40 \dots$ oraz te poniżej, a ćwiartka 3 zawiera liczby $8, 23, 46 \dots$ 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 $P_{r} (m) = \sum_{1 \leq i \leq m} i^{r},$ a w szczególności przydadzą się nam wzory pozwalające obliczać je w czasie stałym: $P_{1} (m) = \frac{1}{2} m (m + 1), P_{2} (m) = \frac{1}{6} m (m + 1) (2 m + 1), P_{3} (m) = \frac{1}{4} m^{2} (m + 1)^{2} .$

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: $A (k, i) = 1 + (2 k + 1) (i + 1) + 8 P_{1} (i) .$

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, ℓ)$ sumę liczb w kawałku zaczynającym się $i$ -tą liczbą o długości $ℓ$ . Wtedy $S (k, i, ℓ) = A (k, i) \cdot ℓ + P_{1} (ℓ - 1) .$

Oznaczmy jeszcze $γ_{k} = [k = 3]$ (nawias Iversona). Pierwsze $h - 1 - γ_{k}$ kawałków mają po jednym zakręcie, a $i$ -ty z nich ma długość $2 i + 2 + γ_{k}$ . Pozostałe kawałki są proste i mają długość $h$ . Więc suma liczb w prostokącie wynosi $S_{\geq} = \sum_{0 \leq i < h - 1 - γ_{k}} S (k, i, 2 i + 2 + γ_{k}) + \sum_{h - 1 - γ_{k} \leq i < w} S (k, i, h) .$

W przypadku $w < h - 1$ jest trochę trudniej. Mamy $w$ kawałków z zakrętem, a dodatkowo $h - 1 - w - γ_{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: $S_{<} = \sum_{0 \leq i < w} S (k, i, 2 i + 2 + γ_{k}) + \sum_{w + γ_{k} \leq i < h - 1} - S ((k + 1) mod 4, i, - w) .$

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);
  }
}

Rozwiązanie wzorcowe

Aby uzyskać szybsze rozwiązanie, rozwiniemy sumy w tych wzorach. Skorzystamy z ogólnej reguły sumowania wartości wielomianu w kolejnych punktach: $\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) .$

Grupując współczynniki we wzorach na $A$ i $S$ względem potęg $i$ , dostajemy: $\begin{aligned} A (k, i) & = (2 k + 2) + (2 k + 5) i + 4 i^{2}, \\ S (k, i, ℓ) & = (2 k + 2) ℓ + P_{1} (ℓ - 1) + (2 k + 5) ℓ i + 4 ℓ i^{2}, \\ S (k, i, 2 i + 2 + γ_{k}) & = \frac{1}{2} (2 + γ_{k}) (2 k + 5 + γ_{k}) + (8 k + 2 k γ_{k} + 7 γ_{k} + 17) i + 4 (k + γ_{k} + 5) i^{2} + 8 i^{3} . \end{aligned}$

Zatem sumy dla prostych kawałków i kawałków z zakrętem są następujące: $\begin{aligned} T_{P} (k, m, ℓ) & = \sum_{0 \leq i < m} S (k, i, ℓ) = ((2 k + 2) ℓ + P_{1} (ℓ - 1)) m + (2 k + 5) ℓ P_{1} (m - 1) + 4 ℓ P_{2} (m - 1), \\ T_{Z} (k, m) & = \sum_{0 \leq i < m} S (k, i, 2 i + 2 + γ_{k}) = \\ = \frac{1}{2} (2 + γ_{k}) (2 k + 5 + γ_{k}) m + (8 k + 2 k γ_{k} + 7 γ_{k} + 17) P_{1} (m - 1) + \\ + 4 (k + γ_{k} + 5) P_{2} (m - 1) + 8 P_{3} (m - 1) . \end{aligned}$

Ostatecznie daje to wzory pozwalające rozwiązać zadanie w czasie stałym: $\begin{aligned} S_{\geq} & = T_{Z} (k, h - 1 - γ_{k}) + T_{P} (k, w, h) - T_{P} (k, h - 1 - γ_{k}, h), \\ S_{<} & = T_{Z} (k, w) - T_{P} ((k + 1) mod 4, h - 1, - w) + T_{P} ((k + 1) mod 4, w + γ_{k}, - w) . \end{aligned}$

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;
}