自动搬运

查看原文

来自洛谷，原作者为

	decoqwq **

搬运于2025-08-24 21:33:15，当前版本为作者最后更新于2018-08-18 14:12:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这道题可以采用很多种方法来快速算出一个矩阵的和，可以采用二维前缀和，递推公式即

$$f(x,y)=f(x-1,y)+a[x][y]\ \ \ y=1\ or\ y=m$$ $$f(x,y)=f(x,y-1)+a[x][y]\ \ \ x=1\ or\ x=n$$ $$f(x,y)=f(x-1,y)+f(x,y-1)-f(x-1,y-1)+a[x][y]\ \ \ x,y\neq 1\ and\ x\neq n\ and\ y\neq m $$

然乎求矩阵$(x1,y1,x2,y2)$的和差分一下即可，时间复杂度为$O(n^2)$

而如果不用前缀和呢？我们如何快速的求出矩阵的和？

二维树状数组

时间复杂度略慢于前缀和，为$O(n^2\ log^2n)$

我们来观察一下二维树状数组基本操作代码：

添加：

#define lowbit(x) (x&(-x))
void add(int x,int y,int k)
{
	for(int i=x;i<=n;i+=lowbit(i))
    {
    	for(int j=y;j<=m;j+=lowbit(j))
        {
        	c[i][j]+=k;
        }
    }
}

显然的，就是一维树状数组再纵向添加了一次，查询也类似

代码：

#include <bits/stdc++.h>
#define lowbit(x) (x&(-x))
using namespace std;
int c[130][130];
int ans=0,maxn=-0x3f3f3f3f;
void add(int x,int y,int k)
{
    for(int i=x;i<=129;i+=lowbit(i))
    {
        for(int j=y;j<=129;j+=lowbit(j))
        {
            c[i][j]+=k;
        }
    }
}
int query(int x,int y)
{
    int ans=0;
    for(int i=x;i>=1;i-=lowbit(i))
    {
        for(int j=y;j>=1;j-=lowbit(j))
        {
            ans+=c[i][j];
        }
    }
    return ans;
}
int main()
{
    int d,n;
    cin>>d>>n;
    for(int i=1;i<=n;i++)
    {
        int x,y,k;
        scanf("%d%d%d",&x,&y,&k);
        add(x+1,y+1,k);
    }
    for(int i=1;i<=129;i++)
    {
        for(int j=1;j<=129;j++)
        {
            int i1=i-d;
            if(i1<=0)
            {
                i1=1;
            }
            int i2=(i+d);
            if(i2>=130)
            {
                i2=129;
            } 
            int j1=(j-d);
            if(j1<=0)
            {
                j1=1;
            }
            int j2=(j+d);
            if(j2>=130)
            {
                j2=129;
            } 
            int ans1=query(i2,j2)-query(i2,j1-1)-query(i1-1,j2)+query(i1-1,j1-1);
            if(ans1>maxn)
            {
                ans=1;
                maxn=ans1;
            }
            else if(ans1==maxn)
            {
                ans++;
            }
        }
    }
    cout<<ans<<" "<<maxn;
}

倍增

既然没有修改，我们为何不采用倍增的方法来求出矩阵的值？

倍增通过每次向一个点往后跳$2^j$的方式快速获得区间答案，因为其查询复杂度为$O(1)$并且将所求矩阵二进制分解需要$O(log^2n)$，故时间复杂度与二维树状数组类似，为$O(n^2\ log^2n)$

$a[i][j][k][p]$代表矩阵$(i,j)-(i+2^k,j)-(i,j+2^p)-(i+2^k,j+2^p)$的值，预处理时间复杂度也为$O(n^2)$，可以快速完成本题，这里就不发代码了。

后记：这道题虽然简单，但希望各位可以从简单的题目中探寻多种解决问题的方法，博主只是发掘了其冰山一角，只有平时更多的积累，才能在考场上胸有成竹。