UVA 11992 Fast Matrix Operations （降维）

题意：对一个矩阵进行子矩阵操作。

元素最多有1e6个，树套树不好开（我不会），把二维坐标化成一维的，一个子矩阵操作分解成多条线段的操作。

一次操作的复杂度是RlogC，很容易找到极端的数据（OJ上实测没有），如果判断一下然后启发式建树复杂度是min(RlogC,ClogR)。

代码中结点没有保存l和r，而且询问是保存在全局变量中，这样做比较省空间。但是也有缺点，比如推区间结点数量的时候会麻烦一点。

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e6+;

int R,C;

#define lid (id<<1)

#define rid (id<<1|1)

struct Seg

{

    int add,setv;

    int Max,Min,sum;

}tr[maxn<<];

#define OP1(id,val)\

tr[id].add += val; tr[id].Max += val; tr[id].Min += val; tr[id].sum += (r-l+)*val;

#define OP2(id,val)\

tr[id].Max = tr[id].setv = tr[id].Min = val; tr[id].add = ; tr[id].sum = val*(r-l+);

inline void push_down(int id,int l,int r)

{

    int lc = lid, rc = rid, mid = (l+r)>>;

    if(tr[id].setv>=){

        int &t = tr[id].setv;

        swap(r,mid);

        OP2(lc,t);

        swap(l,r); l++; swap(mid,r);

        OP2(rc,t);

        l--; swap(mid,l);

        t = -;

    }

    if(tr[id].add>){

        int &t = tr[id].add;

        swap(r,mid);

        OP1(lc,t);

        swap(l,r); l++; swap(mid,r);

        OP1(rc,t);

        l--; swap(mid,l);

        t = ;

    }

}

inline void maintain(int id)

{

    int lc = lid, rc = rid;

    tr[id].sum = tr[lc].sum + tr[rc].sum;

    tr[id].Max = max(tr[lc].Max,tr[rc].Max);

    tr[id].Min = min(tr[lc].Min,tr[rc].Min);

}

int ql,qr,val;

void add1D(int l = ,int r = R*C-,int id = )

{

    if(ql<=l&&r<=qr) { OP1(id,val) return; }

    int mid = (l+r)>>, lc = lid, rc = rid;

    push_down(id,l,r);

    if(ql<=mid) add1D(l,mid,lc);

    if(qr>mid) add1D(mid+,r,rc);

    maintain(id);

}

void set1D(int l = ,int r = R*C-,int id = )

{

    if(ql<=l&&r<=qr) { OP2(id,val) return; }

    int mid = (l+r)>>, lc = lid, rc = rid;

    push_down(id,l,r);

    if(ql<=mid) set1D(l,mid,lc);

    if(qr>mid) set1D(mid+,r,rc);

    maintain(id);

}

int queryMax1D(int l = ,int r = R*C-,int id = )

{

    if(ql<=l&&r<=qr) { return tr[id].Max; }

    int mid = (l+r)>>, lc = lid, rc = rid;

    push_down(id,l,r);

    int ret = ;

    if(ql<=mid) ret = max(ret,queryMax1D(l,mid,lc));

    if(qr>mid) ret = max(ret,queryMax1D(mid+,r,rc));

    return ret;

}

const int INF = 0x3f3f3f3f;

int queryMin1D(int l = ,int r = R*C-,int id = )

{

    if(ql<=l&&r<=qr) { return tr[id].Min; }

    int mid = (l+r)>>, lc = lid, rc = rid;

    push_down(id,l,r);

    int ret = INF;

    if(ql<=mid) ret = min(ret,queryMin1D(l,mid,lc));

    if(qr>mid) ret = min(ret,queryMin1D(mid+,r,rc));

    return ret;

}

int querySum1D(int l = ,int r = R*C-,int id = )

{

    if(ql<=l&&r<=qr) { return tr[id].sum; }

    int mid = (l+r)>>, lc = lid, rc = rid;

    push_down(id,l,r);

    int ret = ;

    if(ql<=mid) ret += querySum1D(l,mid,lc);

    if(qr>mid) ret += querySum1D(mid+,r,rc);

    return ret;

}

//[0,r)

void add2D(int x1,int y1,int x2,int y2,int v)

{

    val = v;

    int st = x1*C+y1, len = y2-y1;

    for(int x = x1; x <= x2; x++){

        ql = st; qr = st+len;

        add1D();

        st += C;

    }

}

void set2D(int x1,int y1,int x2,int y2,int v)

{

    val = v;

    int st = x1*C+y1, len = y2-y1;

    for(int x = x1; x <= x2; x++){

        ql = st; qr = st+len;

        set1D();

        st += C;

    }

}

int querySum2D(int x1,int y1,int x2,int y2)

{

    int ret = ;

    int st = x1*C+y1, len = y2-y1;

    for(int x = x1; x <= x2; x++){

        ql = st; qr = st+len;

        ret += querySum1D();

        st += C;

    }

    return ret;

}

int queryMax2D(int x1,int y1,int x2,int y2)

{

    int ret = ;

    int st = x1*C+y1, len = y2-y1;

    for(int x = x1; x <= x2; x++){

        ql = st; qr = st+len;

        ret = max(ret,queryMax1D());

        st += C;

    }

    return ret;

}

int queryMin2D(int x1,int y1,int x2,int y2)

{

    int ret = INF;

    int st = x1*C+y1, len = y2-y1;

    for(int x = x1; x <= x2; x++){

        ql = st; qr = st+len;

        ret = min(ret,queryMin1D());

        st += C;

    }

    return ret;

}

int main()

{

    //freopen("in.txt","r",stdin);

    int m;

    while(~scanf("%d%d%d",&R,&C,&m)){

        ql = ; qr = R*C-; val = ;

        set1D();

        while(m--){

            int op,x1,y1,x2,y2; scanf("%d%d%d%d%d",&op,&x1,&y1,&x2,&y2);

            if(op == ){

                int v; scanf("%d",&v);

                add2D(x1-,y1-,x2-,y2-,v);

            }else if(op == ){

                int v; scanf("%d",&v);

                set2D(x1-,y1-,x2-,y2-,v);

            }else {

                x1--;x2--;y1--;y2--;

                printf("%d %d %d\n",querySum2D(x1,y1,x2,y2),queryMin2D(x1,y1,x2,y2),queryMax2D(x1,y1,x2,y2));

            }

        }

    }

    return ;

}

巴特西

UVA 11992 Fast Matrix Operations （降维）

最新文章

热门文章