「UVa 11992」Fast Matrix Operations

给定一个$r\times c$矩阵，支持子矩阵加某一个值，子矩阵覆盖为某一个值，查询某个子矩阵的值。

链接

一如既往放洛谷的链接……
UVa 11992

题解

一个暴力的想法是由于$r$不超过$20$，所以可以开$20$棵线段树，修改和覆盖就不难啦qwq。
至于查询，可以处理这一行的时候合并这一行的答案和原来的答案就好了qwq。所以我查询了$3$次
这个时间复杂度是$O(r\log c)$，绝对不会T掉的

代码

代码略丑，$233$行……

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
const ll MAXN=5e4+51;
struct SegmentTree{
    ll l,r,sum,maxn,minn,tag,cover;
}; 
SegmentTree tree[21][MAXN<<2];
ll length,width,qcnt,lx,rx,ly,ry,op,val,sum,maxn,minn;
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
}
inline void update(ll dim,ll node)
{
    tree[dim][node].sum=tree[dim][node<<1].sum+tree[dim][(node<<1)|1].sum;
    tree[dim][node].maxn=max(tree[dim][node<<1].maxn,tree[dim][(node<<1)|1].maxn);
    tree[dim][node].minn=min(tree[dim][node<<1].minn,tree[dim][(node<<1)|1].minn);
}
inline void create(ll dim,ll l,ll r,ll node)
{
    tree[dim][node].l=l,tree[dim][node].r=r,tree[dim][node].cover=-1;
    if(l==r)
    {
        tree[dim][node].sum=tree[dim][node].maxn=tree[dim][node].minn=0;
        return;
    }
    ll mid=(l+r)>>1;
    create(dim,l,mid,node<<1);
    create(dim,mid+1,r,(node<<1)|1);
    update(dim,node);
}
inline void spread(ll dim,ll node)
{
    ll ls=node<<1,rs=ls|1;
    ll lx=(tree[dim][ls].r-tree[dim][ls].l+1);
    ll rx=(tree[dim][rs].r-tree[dim][rs].l+1);
    if(tree[dim][node].cover!=-1)
    {
        tree[dim][ls].maxn=tree[dim][node].cover;
        tree[dim][rs].maxn=tree[dim][node].cover;
        tree[dim][ls].minn=tree[dim][node].cover;
        tree[dim][rs].minn=tree[dim][node].cover;
        tree[dim][ls].sum=tree[dim][node].cover*lx;
        tree[dim][rs].sum=tree[dim][node].cover*rx;
        tree[dim][ls].cover=tree[dim][rs].cover=tree[dim][node].cover;
        tree[dim][ls].tag=tree[dim][rs].tag=0;
        tree[dim][node].cover=-1;
    }
    if(tree[dim][node].tag)
    {
        tree[dim][ls].maxn+=tree[dim][node].tag;
        tree[dim][rs].maxn+=tree[dim][node].tag;
        tree[dim][ls].minn+=tree[dim][node].tag;
        tree[dim][rs].minn+=tree[dim][node].tag;
        tree[dim][ls].sum+=tree[dim][node].tag*lx;
        tree[dim][rs].sum+=tree[dim][node].tag*rx;
        tree[dim][ls].tag+=tree[dim][node].tag;
        tree[dim][rs].tag+=tree[dim][node].tag;
        tree[dim][node].tag=0;
    } 
}
inline void add(ll dim,ll l,ll r,ll val,ll node)
{
    if(l<=tree[dim][node].l&&r>=tree[dim][node].r)
    {
        tree[dim][node].sum+=(tree[dim][node].r-tree[dim][node].l+1)*val;
        tree[dim][node].maxn+=val,tree[dim][node].minn+=val;
        tree[dim][node].tag+=val;
        return;
    }
    spread(dim,node);
    ll mid=(tree[dim][node].l+tree[dim][node].r)>>1;
    if(l<=mid)
    {
        add(dim,l,r,val,node<<1);
    }
    if(r>mid)
    {
        add(dim,l,r,val,(node<<1)|1);
    }
    update(dim,node);
}
inline void cover(ll dim,ll l,ll r,ll val,ll node)
{
    if(l<=tree[dim][node].l&&r>=tree[dim][node].r)
    {
        tree[dim][node].sum=(tree[dim][node].r-tree[dim][node].l+1)*val;
        tree[dim][node].maxn=tree[dim][node].minn=val;
        tree[dim][node].cover=val;
        tree[dim][node].tag=0;
        return;
    }
    spread(dim,node);
    ll mid=(tree[dim][node].l+tree[dim][node].r)>>1;
    if(l<=mid)
    {
        cover(dim,l,r,val,node<<1);
    }
    if(r>mid)
    {
        cover(dim,l,r,val,(node<<1)|1);
    }
    update(dim,node);
}
inline ll query(ll dim,ll l,ll r,ll node)
{
    if(l<=tree[dim][node].l&&r>=tree[dim][node].r)
    {
        return tree[dim][node].sum;
    }
    ll mid=(tree[dim][node].l+tree[dim][node].r)>>1,res=0;
    spread(dim,node);
    if(l<=mid)
    {
        res+=query(dim,l,r,node<<1);  
    } 
    if(r>mid)
    {
        res+=query(dim,l,r,(node<<1)|1);
    }
    return res;
}
inline ll queryMax(ll dim,ll l,ll r,ll node)
{
    if(l<=tree[dim][node].l&&r>=tree[dim][node].r)
    {
        return tree[dim][node].maxn;
    }
    ll mid=(tree[dim][node].l+tree[dim][node].r)>>1,res=0;
    spread(dim,node);
    if(l<=mid)
    {
        res=max(res,queryMax(dim,l,r,node<<1));  
    }
    if(r>mid)
    {
        res=max(res,queryMax(dim,l,r,(node<<1)|1));
    }
    return res;
}
inline ll queryMin(ll dim,ll l,ll r,ll node)
{
    if(l<=tree[dim][node].l&&r>=tree[dim][node].r)
    {
        return tree[dim][node].minn;
    }
    ll mid=(tree[dim][node].l+tree[dim][node].r)>>1,res=0x7fffffff;
    spread(dim,node);
    if(l<=mid)
    {
        res=min(res,queryMin(dim,l,r,node<<1));  
    }
    if(r>mid)
    {
        res=min(res,queryMin(dim,l,r,(node<<1)|1));
    }
    return res;
}
inline void solve()
{
    width=read(),qcnt=read();
    for(register int i=1;i<=length;i++)
    {
        create(i,1,width,1);
    }
    for(register int i=1;i<=qcnt;i++)
    {
        op=read(),lx=read(),ly=read(),rx=read(),ry=read();
        if(op==1)
        {
            val=read();
            for(register int j=lx;j<=rx;j++)
            {
                add(j,ly,ry,val,1);
            }
        }
        if(op==2)
        {
            val=read(); 
            for(register int j=lx;j<=rx;j++)
            {
                cover(j,ly,ry,val,1);
            }
        } 
        if(op==3)
        {
            sum=maxn=0,minn=0x7fffffff;
            for(register int j=lx;j<=rx;j++)
            {
                sum+=query(j,ly,ry,1);
                maxn=max(maxn,queryMax(j,ly,ry,1));
                minn=min(minn,queryMin(j,ly,ry,1));
            }
            printf("%d %d %d\n",sum,minn,maxn);
        } 
    }
}
int main()
{
    while(scanf("%d",&length)!=EOF)
    {
        solve();
        memset(tree,0,sizeof(tree));
    }
}