题解 P2038 【无线网络发射器选址】

decoqwq · 2018-08-18 14:12:47 · 题解

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

然乎求矩阵(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)