JZOJ5417. 【NOIP2017提高A组集训10.24】 二维线段树

题意：给一个矩阵，q次询问子矩阵，查询最大值最小值，区间和， 每个询问的方阵的长不超过宽的两倍。

屁股后面那个两倍什么玩意儿的你想用就用，我不想用，懒得打什么鬼畜的rmq，去他的，二维线段树多爽，直接过。

然后我比赛把前缀和打错了啊啊啊啊啊！！！

/喷血 犯了史上最傻逼错误没有之一，更让我绝望的是，我打拍的时候直接把前缀和那个地方黏过去用所以根本没拍出来/喷血。

血的教训，希望我能铭记。

#include<cstdio>
#include<algorithm>
#include<cstring>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int N=;
const int M=+;
const int inf=;
int n,m,q;
int mx[N<<][N<<],mn[N<<][N<<];
typedef long long ll;
ll sum[N][N];
int a[N][N],maxx,minx,X1,X2,Y1,Y2   ;
inline void buildy(int x,int l,int r,int rtx,int rty)
{
    if (l==r)
    {
        if (x!=-)
            mx[rtx][rty]=mn[rtx][rty]=a[x][l]; 
        else
        {
            mx[rtx][rty]=max(mx[rtx<<][rty],mx[rtx<<|][rty]);  
            mn[rtx][rty]=min(mn[rtx<<][rty],mn[rtx<<|][rty]);  
        }
        return;
    }
    int mid=(l+r)>>;
    buildy(x,l,mid,rtx,rty<<);
    buildy(x,mid+,r,rtx,rty<<|);
    mx[rtx][rty]=max(mx[rtx][rty<<],mx[rtx][rty<<|]);  
    mn[rtx][rty]=min(mn[rtx][rty<<],mn[rtx][rty<<|]);  
}
inline void buildx(int l,int r,int rtx)
{
    if (l==r)
    {
        buildy(l,,m,rtx,);
        return;
    }
    int mid=(l+r)>>;
    buildx(l,mid,rtx<<);
    buildx(mid+,r,rtx<<|);
    buildy(-,,m,rtx,);
}
inline void queryy(int l,int r,int rtx,int rty)
{
    if (Y1<=l&&r<=Y2)
    {
        maxx=max(maxx,mx[rtx][rty]);
        minx=min(minx,mn[rtx][rty]);
        return;
    }
    int mid=(l+r)>>;
    if (Y1<=mid)queryy(l,mid,rtx,rty<<);
    if (Y2>mid)queryy(mid+,r,rtx,rty<<|);
}
inline void queryx(int l,int r,int rtx)
{
    if(X1<=l&&r<=X2)
    {
        queryy(,m,rtx,);
        return;
    }
    int mid=(l+r)>>;
    if (X1<=mid)queryx(l,mid,rtx<<);
    if (X2>mid)queryx(mid+,r,rtx<<|);
}
int main()
{
    freopen("phalanx.in","r",stdin);
    freopen("phalanx.out","w",stdout);
    scanf("%d%d",&n,&m);
    fo(i,,n)
    {
        fo(j,,m)
        {
            scanf("%d",&a[i][j]);
        }
    }
    buildx(,n,);
    fo(i,,n)
    {
        fo(j,,m)
        sum[i][j]=sum[i-][j]+sum[i][j-]-sum[i-][j-]+a[i][j];
    }
    scanf("%d",&q);
    fo(i,,q)
    {
        char ch[];
        scanf("%s%d%d%d%d",ch,&X1,&Y1,&X2,&Y2);
        X1++,Y1++,X2++,Y2++;
        if (ch[]=='S')
        {
            printf("%lld\n",sum[X2][Y2]-sum[X2][Y1-]-sum[X1-][Y2]+sum[X1-][Y1-]);
        }
        else
        {
            int op=;
            if (ch[]=='A')op=;
            if (ch[]=='I')op=;
            maxx=-inf,minx=inf;
            queryx(,n,);
            if (op==)
            printf("%d\n",maxx);
            else printf("%d\n",minx);
        }
    }
}