频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
CodeForces 444C DZY Loves Colors
2014-07-16 10:42:37         来源:House、房子  
收藏   我要投稿

题意:

一段区间a一开始是1、2、3、4……n这样的 每次1操作可以将[l,r]覆盖成x 同时得到abs(a[i]-x)的价值 2操作查询[l,r]的价值


思路:

线段树 又是一道加深线段树理解的题

操作2是简单的求和 线段树基本操作 难点在操作1

用cov表示该区间的值(如果为0说明是混合区间) 用val表示该区间的价值和

那么在更新时就不仅仅是找到 tree[i].l==l&&tree[i].r==r 就停止了 而是继续向下递归 直到一段区间的cov>0才结束

之所以这么做是因为要将x覆盖到之前覆盖过的连续的区间(其实就是将以前混合的区间合并成一个) 这是更新val所必须的

但如此做了我们会发现val只计算到了更新过的位置 无法将这次更新down下去 那么就需要设置一个lazy标志

lazy记录该区间还没有被down下去的价值


代码:

#include
#include
#include
using namespace std;
#define N 101000
#define L(x) (x<<1)
#define R(x) ((x<<1)|1)
typedef __int64 ll;

int n,m;
struct node
{
    int l,r,cov;
    ll val,lazy;
}tree[N*4];
ll ans;

int abs(int x)
{
    if(x<0) return -x;
    return x;
}

void up(int i)
{
    tree[i].val=tree[L(i)].val+tree[R(i)].val;
}

void down(int i)
{
    if(tree[i].cov)
    {
        tree[L(i)].cov=tree[i].cov;
        tree[R(i)].cov=tree[i].cov;
        tree[i].cov=0;
    }
    if(tree[i].lazy)
    {
        tree[L(i)].lazy+=tree[i].lazy;
        tree[L(i)].val+=tree[i].lazy*(tree[L(i)].r-tree[L(i)].l+1);
        tree[R(i)].lazy+=tree[i].lazy;
        tree[R(i)].val+=tree[i].lazy*(tree[R(i)].r-tree[R(i)].l+1);
        tree[i].lazy=0;
    }
}

void init(int l,int r,int i)
{
    tree[i].l=l; tree[i].r=r; tree[i].val=tree[i].lazy=0;
    if(l==r)
    {
        tree[i].cov=l;
        return ;
    }
    int mid=(l+r)/2;
    init(l,mid,L(i));
    init(mid+1,r,R(i));
}

void solve(int i,int key)
{
    if(tree[i].cov)
    {
        tree[i].lazy+=abs(key-tree[i].cov);
        tree[i].val+=(ll)(abs(key-tree[i].cov))*(tree[i].r-tree[i].l+1);
        tree[i].cov=key;
        return ;
    }
    else
    {
        down(i);
        solve(L(i),key);
        solve(R(i),key);
        up(i);
    }
    tree[i].cov=key;
}

void update(int l,int r,int i,int key)
{
    if(tree[i].l==l&&tree[i].r==r)
    {
        solve(i,key);
        return ;
    }
    down(i);
    int mid=(tree[i].l+tree[i].r)/2;
    if(r<=mid) update(l,r,L(i),key);
    else if(l>mid) update(l,r,R(i),key);
    else
    {
        update(l,mid,L(i),key);
        update(mid+1,r,R(i),key);
    }
    up(i);
}

void query(int l,int r,int i)
{
    if(tree[i].l==l&&tree[i].r==r)
    {
        ans+=tree[i].val;
        return ;
    }
    down(i);
    int mid=(tree[i].l+tree[i].r)/2;
    if(r<=mid) query(l,r,L(i));
    else if(l>mid) query(l,r,R(i));
    else
    {
        query(l,mid,L(i));
        query(mid+1,r,R(i));
    }
    up(i);
}

int main()
{
    int p,l,r,w;
    scanf("%d%d",&n,&m);
    init(1,n,1);
    while(m--)
    {
        scanf("%d%d%d",&p,&l,&r);
        if(p==1)
        {
            scanf("%d",&w);
            update(l,r,1,w);
        }
        else
        {
            ans=0;
            query(l,r,1);
            printf("%I64d\n",ans);
        }
    }
    return 0;
}


点击复制链接 与好友分享!回本站首页
相关TAG标签
上一篇:编程算法 - 求1+2+...+n(函数继承) 代码(C++)
下一篇:编程算法 - 求1+2+...+n(模板类) 代码(C++)
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站