题解：P4676 [BalticOI 2016] Spiral (day1)

· · 题解

题意简述

在边长为 2n+1 的方格中，编号从原点的 1 开始，按照逆时针螺旋依次增大。每次询问一个坐标矩形内所有编号之和，对 10^9+7 取模。

解题思路

先推导一个象限内的二维前缀和，再把询问矩形拆到四个方向中。

从正 y 轴开始，按逆时针方向给四条坐标轴编号为 0,1,2,3。记第 t 条轴上距离原点 k 的编号为 A_t(k)。沿每一层螺旋直接计数可得：

A_t(k)=4k^2+c_tk+1

其中：

(c_0,c_1,c_2,c_3)=(-1,1,3,-3)

把第 t 条轴和下一条轴围成的象限旋转到局部第一象限。局部坐标 (i,j) 的两条轴分别是第 t 条轴和第 t+1 条轴，下标按模 4 计算。

记该位置的编号为 W_t(i,j)。若 i\ge j，它与第 t 条轴位于同一段螺旋边上；否则与第 t+1 条轴位于同一段。于是：

W_t(i,j)= \begin{cases} A_t(i)+j & i\ge j \\ A_{t+1}(j)-i & i<j \end{cases}

先计算轴上的前缀和：

\begin{aligned} G_t(x) & =\sum_{k=0}^xA_t(k) \\ & =\frac{2x(x+1)(2x+1)}{3}+\frac{c_tx(x+1)}{2}+x+1 \end{aligned}

约定 x<0 时 G_t(x)=0。

再记 F_t(x) 为局部正方形 [0,x]\times[0,x] 内的编号和。第 k 层由 i=k 的一列与 j=k 的一行组成，后一部分不重复计算交点。该层的和为：

(k+1)A_t(k)+kA_{t+1}(k)+k

把各层求和并化简，得到：

F_t(x)=2x^2(x+1)^2+\frac{u_tx(x+1)(2x+1)}{3}+v_tx(x+1)+x+1

其中：

\begin{aligned} (u_0,u_1,u_2,u_3) & =(2,4,2,0) \\ (v_0,v_1,v_2,v_3) & =(1,2,3,0) \end{aligned}

接着计算任意局部前缀矩形。记 P_t(x,y) 为 [0,x]\times[0,y] 内的编号和；若 x<0 或 y<0，则值为 0。

当 x=y 时，答案就是 F_t(x)。当 x>y 时，先取边长为 y 的正方形。右侧多出的每一列都是公差为 1 的等差数列，其首尾项之和可以用 G_t 之差计算。x<y 时对上方多出的行作对称处理。因此：

P_t(x,y)= \begin{cases} F_t(x) & x=y \\ F_t(y)+\frac{\left(2G_t(x)-2G_t(y)+y(x-y)\right)(y+1)}{2} & x>y \\ F_t(x)+\frac{\left(2G_{t+1}(y)-2G_{t+1}(x)-x(y-x)\right)(x+1)}{2} & x<y \end{cases}

有了 P_t，局部坐标中的任意矩形都能用四次前缀和求出。

如果让四个象限都包含坐标轴，最后还要逐段减去重复轴。可以直接把整张平面划分为四个互不相交的区域，并把原点单独处理：

t 全局坐标范围 局部坐标 (i,j)
0 x\le0,y\ge1 (y,-x)
1 x\le-1,y\le0 (-x,-y)
2 x\ge0,y\le-1 (-y,x)
3 x\ge1,y\ge0 (x,y)

四个区域恰好覆盖原点以外的所有格点，而且没有交集。对每次询问，分别求原矩形与这四个区域的交集，将交集端点转换为局部非负坐标，再调用局部矩形和。若询问包含原点，最后额外加上 1。这样不需要任何坐标轴去重分支。

公式中的除法在模意义下分别乘以 2 和 3 的逆元。每次询问只进行常数次运算，时间复杂度为 O(1)；总时间复杂度为 O(q)，空间复杂度为 O(1)。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const ll mod=1000000007;
const ll inv2=500000004;
const ll inv3=333333336;
const int cg[4]={-1,1,3,-3};
const int cf[4]={2,4,2,0};
const int cp[4]={1,2,3,0};
ll fix(ll x)
{
    x%=mod;
    if(x<0)x+=mod;
    return x;
}
ll add(ll x,ll y)
{
    return fix(x+y);
}
ll sub(ll x,ll y)
{
    return fix(x-y);
}
ll mul(ll x,ll y)
{
    return fix(x)*fix(y)%mod;
}
ll g(int op,ll x)
{
    if(x<0)return 0;
    ll a=fix(x);
    ll b=add(a,1);
    ll ans=mul(mul(mul(2,a),b),add(mul(2,a),1));
    ans=mul(ans,inv3);
    ans=add(ans,mul(cg[op],mul(mul(a,b),inv2)));
    return add(ans,b);
}
ll f(int op,ll x)
{
    ll a=fix(x);
    ll b=add(a,1);
    ll ans=add(mul(2,mul(mul(a,a),mul(b,b))),b);
    ll sum=mul(mul(mul(a,b),add(mul(2,a),1)),inv3);
    ans=add(ans,mul(cf[op],sum));
    return add(ans,mul(cp[op],mul(a,b)));
}
ll prefix(int op,ll x,ll y)
{
    if(x<0||y<0)return 0;
    if(x==y)return f(op,x);
    if(x>y)
    {
        ll sum=mul(2,sub(g(op,x),g(op,y)));
        sum=add(sum,mul(x-y,y));
        return add(f(op,y),mul(mul(sum,y+1),inv2));
    }
    ll sum=mul(2,sub(g((op+1)%4,y),g((op+1)%4,x)));
    sum=sub(sum,mul(y-x,x));
    return add(f(op,x),mul(mul(sum,x+1),inv2));
}
ll query(int op,ll x1,ll y1,ll x2,ll y2)
{
    ll ans=sub(prefix(op,x2,y2),prefix(op,x1-1,y2));
    ans=sub(ans,prefix(op,x2,y1-1));
    return add(ans,prefix(op,x1-1,y1-1));
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n;
    int q;
    cin>>n>>q;
    while(q--)
    {
        ll x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        ll ans=0;
        if(x1<=0&&y2>=1)
        {
            ll rx=min(x2,0LL);
            ll ly=max(y1,1LL);
            ans=add(ans,query(0,ly,-rx,y2,-x1));
        }
        if(x1<=-1&&y1<=0)
        {
            ll rx=min(x2,-1LL);
            ll ry=min(y2,0LL);
            ans=add(ans,query(1,-rx,-ry,-x1,-y1));
        }
        if(x2>=0&&y1<=-1)
        {
            ll lx=max(x1,0LL);
            ll ry=min(y2,-1LL);
            ans=add(ans,query(2,-ry,lx,-y1,x2));
        }
        if(x2>=1&&y2>=0)
        {
            ll lx=max(x1,1LL);
            ll ly=max(y1,0LL);
            ans=add(ans,query(3,lx,ly,x2,y2));
        }
        if(x1<=0&&x2>=0&&y1<=0&&y2>=0)ans=add(ans,1);
        cout<<ans<<'\n';
    }
    return 0;
}