您的位置: 首页  >  IT文章  >  UVa 11992 Fast Matrix Operations (线段树)

UVa 11992 Fast Matrix Operations (线段树)

分类: IT文章 • 2022-08-02 18:37:12

Fast Matrix Operations

Description

There is a matrix containing at most 106 elements divided into r rows and c columns. Each element has a location (x, y) where 1 ≤ x ≤ r, 1 ≤ y ≤ c. Initially, all the elements are zero.

You need to handle four kinds of operations:

1 x1 y1 x2 y2 v Increment each element (x, y) in submatrix (x1, y1, x2, y2) by v (v > 0)

2 x1 y1 x2 y2 v Set each element (x, y) in submatrix (x1, y1, x2, y2) to v

3 x1 y1 x2 y2 Output the summation, min value and max value of submatrix (x1, y1, x2, y2)

In the above descriptions, submatrix (x1, y1, x2, y2) means all the elements (x, y) satisfying x1 ≤ x ≤ x2 and y1 ≤ x ≤ y2. It is guaranteed that 1 ≤ x1 ≤ x2 ≤ r, 1 ≤ y1 ≤ y2 ≤ c. After any operation, the sum of all the elements in the matrix does not exceed 109 .

Input

There are several test cases. The first line of each case contains three positive integers r, c, m, where m (1 ≤ m ≤ 20, 000) is the number of operations. Each of the next m lines contains a query. There will be at most twenty rows in the matrix. The input is terminated by end-of-file (EOF).

Output

For each type-3 query, print the summation, min and max.

Sample Input

4 4 8

1 1 2 4 4 5

3 2 1 4 4

1 1 1 3 4 2

3 1 2 4 4

3 1 1 3 4

2 2 1 4 4 2

3 1 2 4 4

1 1 1 4 3 3

Sample Output

45 0 5

78 5 7

69 2 7

39 2 7

题意：给你一个矩阵，有三个操作。首先很容易想到用线段树来做，注意到r<=20,故可以开20个线段树来储存每一行的信息。

然后有两个标记，set和add，在push_down的时候，先处理set，后处理add。还有需要注意的是，在更新时，如果是set操作，会将add置为0，而add则不改变set。

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1e6+100;
const int INF = 0x3f3f3f3f;
struct Node
{
    int l,r;
    int sum,mi,ma;
    int addv,setv;
}segTree[22][MAXN*4];
void push_up(int idx,int id)
{
    segTree[idx][id].sum=segTree[idx][id*2].sum+segTree[idx][id*2+1].sum;
    segTree[idx][id].mi=min(segTree[idx][id*2].mi,segTree[idx][id*2+1].mi);
    segTree[idx][id].ma=max(segTree[idx][id*2].ma,segTree[idx][id*2+1].ma);
}
void push_down(int idx,int id)
{
    int mid=(segTree[idx][id].l+segTree[idx][id].r)/2;
    if(segTree[idx][id].setv>=0)
    {
        segTree[idx][id*2].setv=segTree[idx][id*2+1].setv=segTree[idx][id].setv;
        segTree[idx][id*2].addv=segTree[idx][id*2+1].addv=0;
        segTree[idx][id*2].sum=(mid-segTree[idx][id].l+1)*segTree[idx][id].setv;
        segTree[idx][id*2+1].sum=(segTree[idx][id].r-mid)*segTree[idx][id].setv;
        segTree[idx][id*2].mi=segTree[idx][id*2].ma=segTree[idx][id].setv;
        segTree[idx][id*2+1].mi=segTree[idx][id*2+1].ma=segTree[idx][id].setv;
        segTree[idx][id].setv=-1;
    }
    if(segTree[idx][id].addv>0)
    {
        segTree[idx][id*2].addv+=segTree[idx][id].addv;
        segTree[idx][id*2+1].addv+=segTree[idx][id].addv;
        segTree[idx][id*2].sum+=(mid-segTree[idx][id].l+1)*segTree[idx][id].addv;
        segTree[idx][id*2+1].sum+=(segTree[idx][id].r-mid)*segTree[idx][id].addv;
        segTree[idx][id*2].mi+=segTree[idx][id].addv;
        segTree[idx][id*2].ma+=segTree[idx][id].addv;
        segTree[idx][id*2+1].mi+=segTree[idx][id].addv;
        segTree[idx][id*2+1].ma+=segTree[idx][id].addv;
        segTree[idx][id].addv=0;
    }
}
void build(int idx,int id,int l,int r)
{
    segTree[idx][id].l=l;
    segTree[idx][id].r=r;
    if(l==r)
    {
        segTree[idx][id].sum=0;
        segTree[idx][id].mi=0;
        segTree[idx][id].ma=0;
        segTree[idx][id].addv=0;
        segTree[idx][id].setv=-1;
        return;
    }
    int mid=(l+r)/2;
    build(idx,id*2,l,mid);
    build(idx,id*2+1,mid+1,r);
    push_up(idx,id);
}
void update(int idx,int id,int l,int r,int op,int val)
{
    if(segTree[idx][id].l>=l&&segTree[idx][id].r<=r)
    {
        if(op==1)
        {
            segTree[idx][id].addv+=val;
            segTree[idx][id].sum+=val*(segTree[idx][id].r-segTree[idx][id].l+1);
            segTree[idx][id].mi+=val;
            segTree[idx][id].ma+=val;
        }
        else
        {
            segTree[idx][id].addv=0;
            segTree[idx][id].setv=val;
            segTree[idx][id].sum=val*(segTree[idx][id].r-segTree[idx][id].l+1);
            segTree[idx][id].mi=val;
            segTree[idx][id].ma=val;
        }
        return;
    }
    push_down(idx,id);
    int mid=(segTree[idx][id].l+segTree[idx][id].r)/2;
    if(l>mid) update(idx,id*2+1,l,r,op,val);
    else if(r<=mid) update(idx,id*2,l,r,op,val);
    else
    {
        update(idx,id*2,l,mid,op,val);
        update(idx,id*2+1,mid+1,r,op,val);
    }
    push_up(idx,id);
}
int querysum(int idx,int id,int l,int r)
{
    int res=0;
    if(segTree[idx][id].l>=l&&segTree[idx][id].r<=r) return segTree[idx][id].sum;
    push_down(idx,id);
    int mid=(segTree[idx][id].l+segTree[idx][id].r)/2;
    if(l>mid) res+=querysum(idx,id*2+1,l,r);
    else if(r<=mid) res+=querysum(idx,id*2,l,r);
    else
    {
        res+=querysum(idx,id*2,l,mid);
        res+=querysum(idx,id*2+1,mid+1,r);
    }
    push_up(idx,id);
    return res;
}
int querymax(int idx,int id,int l,int r)
{
    int res=-INF;
    if(segTree[idx][id].l>=l&&segTree[idx][id].r<=r) return segTree[idx][id].ma;
    push_down(idx,id);
    int mid=(segTree[idx][id].l+segTree[idx][id].r)/2;
    if(l>mid) res=max(res,querymax(idx,id*2+1,l,r));
    else if(r<=mid) res=max(res,querymax(idx,id*2,l,r));
    else
    {
        res=max(res,querymax(idx,id*2,l,mid));
        res=max(res,querymax(idx,id*2+1,mid+1,r));
    }
    push_up(idx,id);
    return res;
}
int querymin(int idx,int id,int l,int r)
{
    int res=INF;
    if(segTree[idx][id].l>=l&&segTree[idx][id].r<=r) return segTree[idx][id].mi;
    push_down(idx,id);
    int mid=(segTree[idx][id].l+segTree[idx][id].r)/2;
    if(l>mid) res=min(res,querymin(idx,id*2+1,l,r));
    else if(r<=mid) res=min(res,querymin(idx,id*2,l,r));
    else
    {
        res=min(res,querymin(idx,id*2,l,mid));
        res=min(res,querymin(idx,id*2+1,mid+1,r));
    }
    push_up(idx,id);
    return res;
}
int main()
{
    int r,c,m,op;
    int x1,y1,x2,y2,val;
    while(scanf("%d%d%d",&r,&c,&m)!=EOF)
    {
        for(int i=1;i<=r;i++) build(i,1,1,c);
        while(m--)
        {
            scanf("%d",&op);
            if(op<3)
            {
                scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&val);
                for(int i=x1;i<=x2;i++) update(i,1,y1,y2,op,val);
            }
            else
            {
                scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
                int ressum=0,resmax=-INF,resmin=INF;
                for(int i=x1;i<=x2;i++)
                {
                    ressum+=querysum(i,1,y1,y2);
                    resmax=max(resmax,querymax(i,1,y1,y2));
                    resmin=min(resmin,querymin(i,1,y1,y2));
                }
                printf("%d %d %d
",ressum,resmin,resmax);
            }
        }
    }
    return 0;
}

相关推荐