UVA 11992 懒惰标记应用

这个题目要求和还有设置区间值区间增值，明显要用线段树来

由于行数不超过20 而列数多达 10^5,所以对每一行建一棵线段树。

然后主要是在懒惰标记方面是难点针对两种操作分别设置 set 和 add 方法，但是优先级方面要好好考虑

可能出现的结果无非是单独的 set 或者 add 以及先set再add 或者先add再set，单独的那两种就按常规写法，然后先set再add，则明显 add标记不能清除set，所以在pushdown的时候先set 再 add，先set 再add ，则直接清除当前的add标记，在pushdown的时候同样清除子节点的add标记

其实只要搞清优先级也挺简单的。。。懒惰标记用的还不熟练，要继续加强

#include <iostream>

#include <cstdio>

#include <cstring>

#define lson rt<<1,l,mid

#define rson rt<<1|1,mid+1,r

using namespace std;

const int N = +;

int d[][N*],dmax[][N*],dmin[][N*],setv[][N*],addv[][N*];

int r,c,m;

struct node

{

    int tot,maxn,mini;

};

void up(int num,int rt)

{

    d[num][rt]=d[num][rt<<]+d[num][rt<<|];

    dmax[num][rt]=max(dmax[num][rt<<],dmax[num][rt<<|]);

    dmin[num][rt]=min(dmin[num][rt<<],dmin[num][rt<<|]);

}

void build(int num,int rt,int l,int r)

{

    setv[num][rt]=-;

    addv[num][rt]=;

    d[num][rt]=dmax[num][rt]=dmin[num][rt]=;

    if (l>=r){

        return;

    }

    int mid=(l+r)>>;

    build(num,lson);

    build(num,rson);

}

void pushdown(int num,int rt,int l,int r)

{

    if (l>=r) return;

    int mid=(l+r)>>;

    if (setv[num][rt]>=){

        d[num][rt<<]=(mid-l+)*setv[num][rt];

        dmax[num][rt<<]=setv[num][rt];

        dmin[num][rt<<]=setv[num][rt];

        d[num][rt<<|]=(r-mid)*setv[num][rt];

        dmax[num][rt<<|]=setv[num][rt];

        dmin[num][rt<<|]=setv[num][rt];

        setv[num][rt<<]=setv[num][rt<<|]=setv[num][rt];

        setv[num][rt]=-;

        addv[num][rt<<]=addv[num][rt<<|]=;

    }

    if (addv[num][rt]){

        d[num][rt<<]+=(mid-l+)*addv[num][rt];

        dmax[num][rt<<]+=addv[num][rt];

        dmin[num][rt<<]+=addv[num][rt];

        d[num][rt<<|]+=(r-mid) *addv[num][rt];

        dmax[num][rt<<|]+=addv[num][rt];

        dmin[num][rt<<|]+=addv[num][rt];

        addv[num][rt<<]+=addv[num][rt];

        addv[num][rt<<|]+=addv[num][rt];

        addv[num][rt]=;

    }

}

void pushdown2(int num,int rt,int l,int r)

{

    if (l>=r) return;

    int mid=(l+r)>>;

    if (setv[num][rt]>=){

        d[num][rt<<]=(mid-l+)*setv[num][rt];

        dmax[num][rt<<]=setv[num][rt];

        dmin[num][rt<<]=setv[num][rt];

        d[num][rt<<|]=(r-mid)*setv[num][rt];

        dmax[num][rt<<|]=setv[num][rt];

        dmin[num][rt<<|]=setv[num][rt];

        setv[num][rt<<]=setv[num][rt<<|]=setv[num][rt];

        setv[num][rt]=-;

        addv[num][rt<<]=addv[num][rt<<|]=;

    }

    if (addv[num][rt]){

        d[num][rt<<]+=(mid-l+)*addv[num][rt];

        dmax[num][rt<<]+=addv[num][rt];

        dmin[num][rt<<]+=addv[num][rt];

        d[num][rt<<|]+=(r-mid) *addv[num][rt];

        dmax[num][rt<<|]+=addv[num][rt];

        dmin[num][rt<<|]+=addv[num][rt];

        addv[num][rt<<]+=addv[num][rt];

        addv[num][rt<<|]+=addv[num][rt];

        addv[num][rt]=;

    }

}

void add(int num,int v,int L,int R,int rt,int l,int r)

{

    if (L<=l && r<=R){

        d[num][rt]+=v*(r-l+);

        dmax[num][rt]+=v;

        dmin[num][rt]+=v;

        addv[num][rt]+=v;

        return;

    }

    pushdown(num,rt,l,r);

    int mid=(l+r)>>;

    if (L<=mid) add(num,v,L,R,lson);

    if (R>mid)  add(num,v,L,R,rson);

    up(num,rt);

}

void sets(int num,int v,int L,int R,int rt,int l,int r)

{

    if (L<=l && r<=R){

        d[num][rt]=v*(r-l+);

        dmax[num][rt]=v;

        dmin[num][rt]=v;

        setv[num][rt]=v;

        addv[num][rt]=; //set标记直接清除当前的add标记 这里要注意别漏掉

        return;

    }

    pushdown(num,rt,l,r);

    int mid=(l+r)>>;

    if (L<=mid) sets(num,v,L,R,lson);

    if (R>mid)  sets(num,v,L,R,rson);

    up(num,rt);

}

node query(int num,int L,int R,int rt,int l,int r)

{

    int mid=(l+r)>>;

    pushdown2(num,rt,l,r);

    if (L<=l && r<=R){

        node tmp=(node){d[num][rt],dmax[num][rt],dmin[num][rt]};

        return tmp;

    }

    node t1=(node){-,,};

    node t2=(node){-,,};

    if (L<=mid) t1=query(num,L,R,lson);

    if (R>mid) t2=query(num,L,R,rson);

    if (t1.tot<) return t2;

    if (t2.tot<) return t1;

    t1.tot+=t2.tot;

    t1.maxn=max(t2.maxn,t1.maxn);

    t1.mini=min(t1.mini,t2.mini);

    return t1;

}

int main()

{

    while (scanf("%d%d%d",&r,&c,&m)!=EOF)

    {

        for (int i=;i<r;i++){

            build(i,,,c);

        }

        while (m--){

            int deno,x1,y1,x2,y2,v;

            scanf("%d",&deno);

            if (deno<=){

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

                x1--;x2--;

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

                    if (deno==) add(i,v,y1,y2,,,c);

                    else sets(i,v,y1,y2,,,c);

                }

            }

            else{

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

                x1--;x2--;

                node ans;

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

                    if (i==x1) ans=query(i,y1,y2,,,c);

                    else {

                        node tmp=query(i,y1,y2,,,c);

                        ans.tot+=tmp.tot;

                        ans.maxn=max(tmp.maxn,ans.maxn);

                        ans.mini=min(tmp.mini,ans.mini);

                    }

                }

                printf("%d %d %d\n",ans.tot,ans.mini,ans.maxn);

            }

        }

    }

    return ;

}

巴特西

UVA 11992 懒惰标记应用

最新文章

热门文章