UVA 11992

9156 ワード

データ構造線分樹 ACM

Problem F
Fast Matrix Operations
The re is a matrix containing at most 106 elemens divided into r rows and c columns.Each element has a location(x,y)where 1<=r,1<=y==c.Initially,all the element s are.You need to handle four kids of operation:

1 x1 y1 x2 y2 v

Increment each element(x,y)in submatix(x 1,y 1,x 2,y 2)by v(v>0)

2 x1 y1 x2 y2 v

Set each element(x,y)in submatix(x 1,y 1,x 2,y 2)to v

3 x1 y1 x2 y2

Output the summation、min value and max value of submatirix(x 1,y 1,x 2,y 2)
In the abobove descriptions、submatirix(x 1,y 1,x 2,y 2)means all the elemens(x,y)satisfying x 1<=x 2 andy 1==y 2.It isgarteteteteteteteteteteteteth that 1<=x 1=x 1=x 1=thethethethethethethethetheaftytytytytytytytyx=1==thethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethe
Input
The e e e e are several test cases.The first line of each case contains three positive integers r,c,m,where m(1==20,000)is the number of operatis.Each of the next m ininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininint file does not exceed 500 KB.
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

Output for the Sample Input

Rujia Liu's Present 3:A Data Structure Contact Celebrating the 100 th Anniversary of Tsunghua University
Special Thanks:Yeji Shen,Dun Liang
Note:Please make sure to test your program with the gift I/O files before submitting!
デバッグは本当に死人ができます..
簡単に200＋行と書いてあります.shlに深く見下されました.
本題の線分樹は、3つの操作をすることを意味します.x 1、x 2 ,y 1,y 2は、行列を加算し、値を賦課し、和を求める.二次元であるが、行数は20より小さく、一次元に簡略化することができる.

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <map>
#include <string>
#include <stack>
#include <cctype>
#include <vector>
#include <queue>
#include <set>
#include <iomanip>

using namespace std;
//#define Online_Judge
#define outstars cout << "***********************" << endl;
#define clr(a,b) memset(a,b,sizeof(a))
#define lson l , mid  , rt << 1
#define rson mid + 1 , r , rt << 1|1
#define FOR(i , x , n) for(int i = (x) ; i < (n) ; i++)
#define FORR(i , x , n) for(int i = (x) ; i <= (n) ; i++)
#define REP(i , x , n) for(int i = (x) ; i > (n) ; i--)
#define REPP(i ,x , n) for(int i = (x) ; i >= (n) ; i--)

#define mk make_pair
const int MAXN = 1000010 + 50;
const int maxw = 100 + 20;
const int MAXNNODE = 1000 +10;
const long long LLMAX = 0x7fffffffffffffffLL;
const long long LLMIN = 0x8000000000000000LL;
const int INF = 0x7fffffff;
const int IMIN = 0x80000000;
#define eps 1e-8
#define mod 10007
typedef long long LL;
const double PI = acos(-1.0);
typedef double D;
typedef pair<int , int> pii;
const D e = 2.718281828459;
int row , col , n;
struct Node
{
    int l , r;
    int sum , min_num , max_num;
    int delta;
    bool lazyd , lazyv;
    Node(){}
    Node(int L , int R)
    {
        l = L , r = R;
        sum = max_num = min_num = delta = 0;
        lazyd = lazyv = false;
    }
    int mid(){return (l + r) >> 1;}
    int len(){return (r - l + 1);}
}t[MAXN << 2];
void build( int rt , int L,int R )
{
    t[rt] = Node(L , R);
    if(L == R)return ;
    int mid = t[rt].mid();
    build(rt << 1 , L , mid ) , build(rt << 1 | 1 , mid + 1 , R );
}
void pushdown(int rt)
{
    if(!t[rt].lazyd && !t[rt].lazyv)return ;
    if(t[rt].lazyd)
    {
        t[rt << 1].max_num += t[rt].delta;
        t[rt << 1].min_num += t[rt].delta;
        t[rt << 1].sum += t[rt].delta * t[rt << 1].len();
        t[rt << 1 | 1].max_num += t[rt].delta;
        t[rt << 1 | 1].min_num += t[rt].delta;
        t[rt << 1 | 1].sum += t[rt].delta * t[rt << 1 | 1].len();
        if(!t[rt << 1].lazyv)
        {
            t[rt << 1].lazyd = true;
            t[rt << 1].delta += t[rt].delta;
        }
        if(!t[rt << 1 | 1].lazyv)
        {
            t[rt << 1 | 1].lazyd = true;
            t[rt << 1 | 1].delta += t[rt].delta;
        }
        t[rt].delta = 0;
        t[rt].lazyd = false;
    }
    else
    {
        t[rt << 1].lazyv = t[rt << 1 | 1].lazyv = true;
        t[rt << 1].lazyd = t[rt << 1 | 1].lazyd = false;
        t[rt << 1].delta = t[rt << 1 | 1].delta = 0;
        t[rt << 1].max_num = t[rt << 1].min_num = t[rt].max_num;
        t[rt << 1].sum = t[rt << 1].max_num * t[rt << 1].len();

        t[rt << 1 | 1].max_num = t[rt << 1 | 1].min_num = t[rt].max_num;
        t[rt << 1 | 1].sum = t[rt << 1| 1].max_num * t[rt << 1 | 1].len();
        t[rt].lazyv = false;
    }
}
void pushup(int rt)
{
    t[rt].max_num = max(t[rt << 1].max_num , t[rt << 1 | 1].max_num);
    t[rt].min_num = min(t[rt << 1].min_num , t[rt << 1 | 1].min_num);
    t[rt].sum  = t[rt << 1].sum + t[rt << 1 | 1].sum;
}
void update (int rt , int L , int R , int k , int val)
{
    if(t[rt].l == L && t[rt].r == R)
    {
        if(k == 1)
        {
            t[rt].max_num += val;
            t[rt].min_num += val;
            t[rt].sum += val * t[rt].len();
            if(t[rt].lazyd)t[rt].delta += val;
            else if(t[rt].lazyv)t[rt].delta = 0;
            else
            {
                t[rt].delta = val;
                t[rt].lazyd = true;
            }
        }
        else
        {
            t[rt].lazyv = true;
            t[rt].lazyd = false ;
            t[rt].delta = 0;
            t[rt].max_num = t[rt].min_num = val;
            t[rt].sum = val * t[rt].len();
        }
        return;
    }

    pushdown(rt);
    int mid = t[rt].mid();
    if(R <= mid)update(rt << 1 ,L ,R ,  k , val);
    else if(L > mid)update(rt << 1 | 1 ,L  , R ,  k , val);
    else
    {
        update(rt << 1 , L , mid  , k , val);
        update(rt << 1 |1  , mid + 1 , R , k ,val);
    }
    pushup(rt);
}

Node query(int rt , int L , int R)
{
    if(t[rt].l == L && t[rt].r == R)return t[rt];
    pushdown(rt);
    int mid = t[rt].mid();
    if(R <= mid)return query(rt << 1  , L ,R);
    else if(L > mid)return query (rt << 1 | 1 , L , R);
    else
    {
        Node ans1 = query(rt << 1 , L , mid);
        Node ans2 = query(rt << 1 | 1 , mid + 1 , R);
        Node ans;
        ans.sum = ans1.sum + ans2.sum;
        ans.max_num = max(ans1.max_num , ans2.max_num);
        ans.min_num = min(ans1.min_num , ans2.min_num);
        return ans;
    }
}

int main()
{
    //ios::sync_with_stdio(false);
#ifdef Online_Judge
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif // Online_Judge
    int q;
    while(~scanf("%d%d%d" , &row , & col , &q))
    {
        n = row * col;
        build(1 , 1 , n);

        while(q--)
        {
            int op , x1 , y1 , x2 , y2 , val;
            scanf("%d" , &op);
            if(op == 1)
            {
                scanf("%d%d%d%d%d" ,&x1 , &y1 , & x2 , &y2,  &val);
                FORR(i , x1 ,x2)
                {
                    int a = (i - 1) * col + y1;
                    int b = (i - 1) * col + y2;
                    update(1 , a , b , 1 , val);
                }
            }
            else if(op == 2)
            {
                scanf("%d%d%d%d%d" , &x1 ,& y1 , &x2 , & y2 , &val);
                FORR(i , x1 , x2)
                {
                    int a = (i - 1) * col + y1;
                    int b = (i - 1) * col + y2;
                    update(1  , a  ,b , 2 , val);
                }
            }
            else
            {
                Node ans;
                ans.sum = 0 ,ans.max_num = -INF , ans.min_num = INF;
                scanf("%d%d%d%d", &x1 , &y1 , &x2 , &y2);
                FORR(i , x1 , x2)
                {
                    int a = (i - 1) * col + y1;
                    int b = (i - 1) * col + y2;
                    Node res = query(1 , a , b);
                    ans.min_num = min(ans.min_num , res.min_num);
                    ans.max_num = max(ans.max_num , res.max_num);
                    ans.sum += res.sum;
                }
                printf("%d %d %d
" , ans.sum , ans.min_num , ans.max_num);
            }

        }
    }
    return 0;
}

ubus[3]-cli