题解 P5620 【[DBOI2019]捡币】

Tritium · 2019-12-16 11:03:59 · 题解

为数不多的二维分块的题目。（我做题太少了QwQ）

本题二维分块的做法就是对行和列分别一维分块，然后将一维数组改为二维数组即可维护二维分块。基本上是裸的。

上一篇题解关于二维分块的讲解复杂度可能有一些问题。这里再分析一波：

++++++++ ++
++++++++ ++
         ++
++ ..... ++
++ ..... ++
++ ..... ++
++ 
++ ++++++++
++ ++++++++

首先点代表中间整块，+代表零散块。我们是这样维护边角料中间块的对吧？

设块的大小为S,边长为N.那么中间的整块的个数为O((\frac{N}{S})^2)个。

周围四个长条,长为O(N),宽为O(S),所以维护边角料长条时间复杂度O(NS).

除去预处理,总复杂度O(Q(NS+(\frac{N}{S})^2)).

对于复杂度来说,我们只关心最大的那一项.而在S>0的时候,NS是一个增函数,(\frac{N}{S})^2是一个减函数.所以会有一个s_0使得两者相等,并且s_0无论变小还是变大,其值max\{ NS,(\frac{N}{S})^2\}都会变大.

所以,当NS=(\frac{N}{S})^2时,复杂度最小.此时S=N^{\frac{1}{3}}.

总复杂度O(N^{\frac{4}{3}}).\because N=1000,\therefore \text{运算量}\to10^7.可过.

#include <cstdio>
#include <cmath>
const int S=1003;
int n,m,q,a[S][S],bl[S],add[200][200],_=0,nn,mx[200][200],fr[S],ed[S];
long long s[200][200],f[S][S];
inline void read(int &s)
{
    s=0;char t=1,c=getchar();
    while (c!='-' && (c<'0' || c>'9')) c=getchar();
    if (c=='-') c=getchar(),t=-1;
    while (c>='0' && c<='9') s=(s<<1)+(s<<3)+(c^48),c=getchar();
    s*=t;
}
inline long long ma(long long a,long long b){return a>b?a:b;}
inline void mma(int &a,int b){a=a>b?a:b;}
inline void modify(int u,int x,int y,int xx,int yy)
{
    if (bl[x]==bl[xx] || bl[y]==bl[yy] )
    {
        for (int i=x;i<=xx;++i)
            for (int j=y;j<=yy;++j)
            {
                a[i][j]+=u;
                s[bl[i]][bl[j]]+=u;
                mma(mx[bl[i]][bl[j]],a[i][j]);
            }
        return;
    }
    for (int i=bl[x]+1;i<bl[xx];++i)
        for (int j=bl[y]+1;j<bl[yy];++j)
            add[i][j]+=u;
    for (int i=ed[bl[x]];i>=x;--i)
        for (int j=fr[bl[yy]]-1;j>=y;--j)
        {
            a[i][j]+=u;
            s[bl[i]][bl[j]]+=u;
            mma(mx[bl[i]][bl[j]],a[i][j]);
        }
    for (int i=fr[bl[xx]];i<=xx;++i)
        for (int j=ed[bl[y]]+1;j<=yy;++j)
        {
            a[i][j]+=u;
            s[bl[i]][bl[j]]+=u;
            mma(mx[bl[i]][bl[j]],a[i][j]);
        }
    for (int i=ed[bl[x]]+1;i<=xx;++i)
        for (int j=ed[bl[y]];j>=y;--j)
        {
            a[i][j]+=u;
            s[bl[i]][bl[j]]+=u;
            mma(mx[bl[i]][bl[j]],a[i][j]);
        }
    for (int i=fr[bl[xx]]-1;i>=x;--i)
        for (int j=fr[bl[yy]];j<=yy;++j)
        {
            a[i][j]+=u;
            s[bl[i]][bl[j]]+=u;
            mma(mx[bl[i]][bl[j]],a[i][j]);
        }
}
inline int calmx(int x,int y,int xx,int yy)
{
    int s=0;
    if (bl[x]==bl[xx] || bl[y]==bl[yy] )
    {
        for (int i=x;i<=xx;++i)
            for (int j=y;j<=yy;++j)
                mma(s,a[i][j]+add[bl[i]][bl[j]]);
        return s;
    }
    for (int i=bl[x]+1;i<bl[xx];++i)
        for (int j=bl[y]+1;j<bl[yy];++j)
            mma(s,mx[i][j]+add[i][j]);
    for (int i=ed[bl[x]];i>=x;--i)
        for (int j=fr[bl[yy]]-1;j>=y;--j)
            mma(s,a[i][j]+add[bl[i]][bl[j]]);
    for (int i=fr[bl[xx]];i<=xx;++i)
        for (int j=ed[bl[y]]+1;j<=yy;++j)
            mma(s,a[i][j]+add[bl[i]][bl[j]]);
    for (int i=ed[bl[x]]+1;i<=xx;++i)
        for (int j=ed[bl[y]];j>=y;--j)
            mma(s,a[i][j]+add[bl[i]][bl[j]]);
    for (int i=fr[bl[xx]]-1;i>=x;--i)
        for (int j=fr[bl[yy]];j<=yy;++j)
            mma(s,a[i][j]+add[bl[i]][bl[j]]);
    return s;
}
inline long long cals(int x,int y,int xx,int yy)
{
    long long su=0;
    if (bl[x]==bl[xx] || bl[y]==bl[yy] )
    {
        for (int i=x;i<=xx;++i)
            for (int j=y;j<=yy;++j)
                su+=a[i][j]+add[bl[i]][bl[j]];
        return su;
    }
    for (int i=bl[x]+1;i<bl[xx];++i)
        for (int j=bl[y]+1;j<bl[yy];++j)
            su+=s[i][j]+1ll*(ed[i]-fr[i]+1)*(ed[j]-fr[j]+1)*add[i][j];
    for (int i=ed[bl[x]];i>=x;--i)
        for (int j=fr[bl[yy]]-1;j>=y;--j)
            su+=a[i][j]+add[bl[i]][bl[j]];
    for (int i=fr[bl[xx]];i<=xx;++i)
        for (int j=ed[bl[y]]+1;j<=yy;++j)
            su+=a[i][j]+add[bl[i]][bl[j]];
    for (int i=ed[bl[x]]+1;i<=xx;++i)
        for (int j=ed[bl[y]];j>=y;--j)
            su+=a[i][j]+add[bl[i]][bl[j]];
    for (int i=fr[bl[xx]]-1;i>=x;--i)
        for (int j=fr[bl[yy]];j<=yy;++j)
            su+=a[i][j]+add[bl[i]][bl[j]];
    return su;
}
int main()
{
    read(n);read(m);read(q);
    nn=pow(n,1.0/3.0);
    if (nn<1) nn=1;
    for (int i=1;i<=n;++i)
        bl[i]=(i-1)/nn+1;
    for (int i=1;i<=n;++i)
    {
        if (bl[i]!=bl[i-1])
            fr[bl[i]]=i;
        if (bl[i]!=bl[i+1])
            ed[bl[i]]=i;
    }
    int u,x,y,xx,yy;
    while (q--)
    {
        read(u);read(x);read(y);read(xx);read(yy);
        if (u>0)
        {
            ++_;
            modify(u,x,y,xx,yy);
            if (_==m)
            {
                for (int i=1;i<=n;++i)
                    for (int j=1;j<=n;++j)
                        f[i][j]=ma(f[i-1][j],f[i][j-1])+add[bl[i]][bl[j]]+a[i][j];
            }
        }
        else if (!u)
            printf("%d\n",calmx(x,y,xx,yy));
        else
            printf("%lld\n",cals(x,y,xx,yy));
    }
    printf("%lld\n",f[n][n]);
    return 0;
}