这是本蒟蒻有史以来做的第二道线段树的题,竟然调了3天。在%%%wangyi%%%的帮助下终于于2017年4月27日19时10分AC。感谢上帝感谢主感谢社会感谢党感谢人民感谢毛主席。。。。

题意:其实这就是一道区间最大最小求和线段树。给定一个矩阵,最多有20行,106次方个元素。有3种操作:

1 x1 y1 x2 y2 c : 把(x1,y1),(x2,y2)间的元素加上c(c>0,x1<x2,y10,x1<x2,y1<y2)

3 x1 y1 x2 y2 : 把(x1,y1),(x2,y2)间的总和、最小值、最大值。

思路:由于行数很小,所以对每一行建树,暴力更新每一行。对于每个树节点,保存最大、最小、和。

以下是代码的注释

upshdown(标记下传):有set操作先下传并将子节点的add清空,再下传add。(就是这样)

upgrade(即updata):更新最大、最小、和。

所以就是这么简单的题,坑了我3天。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <cmath>

#define MX 1000005

using namespace std;

typedef struct nodee
{
    int mx,mn,sm,l,r,st,ad;
} nd;

vector <nd> tree[21];
int n,m,q;

int input()
{
    if((scanf("%d%d%d",&m,&n,&q))==EOF)return 0;
    return 1;
}

void init()
{
    nd newnode;
    newnode.ad=newnode.l=newnode.mn=newnode.mx=newnode.r=newnode.sm=newnode.st=0;
    for(int j=1;j<=20;j++)tree[j].clear();
    for(int j=1; j<=20; j++)for(int i=0; i<=MX; i++)tree[j].push_back(newnode);
}

void reset()
{
    nd newnode;
    newnode.ad=newnode.l=newnode.mn=newnode.mx=newnode.r=newnode.sm=newnode.st=0;
    for(int j=1; j<=m; j++)for(int i=0; i<=n*4; i++)tree[j][i]=newnode;
}

void build(int node,int l,int r,int w)
{
    tree[w][node].l=l;
    tree[w][node].r=r;
    if(l==r) tree[w][node].mx=tree[w][node].mn=tree[w][node].sm=tree[w][node].st=tree[w][node].ad=0;
    else
    {
        build(node*2,l,(l+r)/2,w);
        build(node*2+1,(l+r)/2+1,r,w);
    }
}

void pushdown(int node,int w)
{
    int sst,aad;
    sst=tree[w][node].st;
    aad=tree[w][node].ad;
    if(sst>0)
    {
        if(tree[w][node].l!=tree[w][node].r)
        {
            tree[w][node*2].ad=0;
            tree[w][node*2].st=sst;
            tree[w][node*2].mn=sst;
            tree[w][node*2].mx=sst;
            tree[w][node*2].sm=(tree[w][node*2].r-tree[w][node*2].l+1)*sst;
            tree[w][node*2+1].ad=0;
            tree[w][node*2+1].st=sst;
            tree[w][node*2+1].mn=sst;
            tree[w][node*2+1].mx=sst;
            tree[w][node*2+1].sm=(tree[w][node*2+1].r-tree[w][node*2+1].l+1)*sst;
            tree[w][node].st=0;
        }
    }
    if(aad>0)
    {
        if(tree[w][node].l<tree[w][node].r)
        {
            tree[w][node*2].ad+=aad;
            tree[w][node*2].mn+=aad;
            tree[w][node*2].mx+=aad;
            tree[w][node*2].sm+=(tree[w][node*2].r-tree[w][node*2].l+1)*aad;//mid-l+1
            tree[w][node*2+1].ad+=aad;
            tree[w][node*2+1].mn+=aad;
            tree[w][node*2+1].mx+=aad;
            tree[w][node*2+1].sm+=(tree[w][node*2+1].r-tree[w][node*2+1].l+1)*aad;//r-mid
            tree[w][node].ad=0;
        }
    }
}

void upgrade(int node,int w)
{
    if(tree[w][node].l!=tree[w][node].r)
    {
        tree[w][node].mn=min(tree[w][node*2].mn,tree[w][node*2+1].mn);
        tree[w][node].mx=max(tree[w][node*2].mx,tree[w][node*2+1].mx);
        tree[w][node].sm=tree[w][node*2].sm+tree[w][node*2+1].sm;
    }
}

void add(int node,int ql,int qr,int w,int x)
{
    int l=tree[w][node].l,r=tree[w][node].r;
    int mid=(l+r)/2;
pushdown(node,w);
    if(ql<=l&&r<=qr) tree[w][node].ad+=x,tree[w][node].mx+=x,tree[w][node].mn+=x,tree[w][node].sm+=(r-l+1)*x;
    else
    {

        if(ql<=mid) add(node*2,ql,qr,w,x);
        if(qr>mid) add(node*2+1,ql,qr,w,x);
        upgrade(node,w);
    }
}

void st(int node,int ql,int qr,int w,int x)
{
    int l=tree[w][node].l,r=tree[w][node].r;
    pushdown(node,w);
    int mid=(l+r)/2;
    if(ql<=l&&r<=qr) tree[w][node].st=x,tree[w][node].ad=0,tree[w][node].mx=x,tree[w][node].mn=x,tree[w][node].sm=(r-l+1)*x;
    else
    {

        if(ql<=mid) st(node*2,ql,qr,w,x);
        if(qr>mid) st(node*2+1,ql,qr,w,x);
        upgrade(node,w);
    }
}

int amn,amx,asu;

void query(int node,int ql,int qr,int w)
{
    int l=tree[w][node].l,r=tree[w][node].r;
    pushdown(node,w);
    if(ql<=l&&r<=qr)
    {
        amn=min(amn,tree[w][node].mn);
        amx=max(amx,tree[w][node].mx);
        asu+=tree[w][node].sm;
    }
    else if(r<ql||l>qr)return;
    else
    {

        query(node*2,ql,qr,w);
        query(node*2+1,ql,qr,w);
    }
}

int main()
{
    freopen("fm.in","r",stdin);
    freopen("fm.out","w",stdout);
    int op,x1,x2,y1,y2,c;
    init();
    while(input())
    {
        reset();
        for(int i=1; i<=m; i++)build(1,1,n,i);
        for(int i=1; i<=q; i++)
        {
            scanf("%d",&op);
            if(op==1)
            {
                scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c);
                for(int j=x1; j<=x2; j++) add(1,y1,y2,j,c);
            }
            else if(op==2)
            {
                scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c);
                for(int j=x1; j<=x2; j++) st(1,y1,y2,j,c);
            }
            else
            {
                scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
                asu=amx=0;
                amn=999999999;
                for(int j=x1; j<=x2; j++) query(1,y1,y2,j);
                cout<<asu<<" "<<amn<<" "<<amx<<endl;
            }
        }
    }
    return 0;
}


分享至ヾ(≧∇≦*)ゝ:
分类: 所有

1 条评论

蒟蒻XZY · 2017年4月27日 11:43 下午

二维线段树?Orz太强啦%%……怎么办感觉回来以后要被泥萌甩三条大马路了……

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *