题目大意：
1 l r x操作 讲 [l，r]上的节点涂成x颜色，并且每个节点的值都加上 |y-x| y为涂之前的颜色
2 l r 操作，求出[l,r]上的和。
思路分析：
如果一个区间为相同的颜色。那么我们才可以合并操作。
所以我们之前找相同的区间就好。
但是问题是如何合并操作。
那么我们定义一个val 表示这个区间每个位置上应该加上的值。
pushdown 的时候这个值是可以相加的。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define maxn 100005
#define lson num<<1,s,mid
#define rson num<<1|1,mid+1,e
using namespace std;
typedef long long LL;
LL color[maxn<<2];
LL sum[maxn<<2];
LL val[maxn<<2];
LL Abs(LL x)
{
return x>0?x:-x;
}
void pushdown(int num,int s,int e)
{
if(color[num]!=-1)
{
int mid=(s+e)>>1;
sum[num<<1]+=val[num]*(mid-s+1);
sum[num<<1|1]+=val[num]*(e-mid);
val[num<<1]+=val[num];
val[num<<1|1]+=val[num];
color[num<<1]=color[num<<1|1]=color[num];
color[num]=-1;
val[num]=0;
}
}
void pushup(int num)
{
if(color[num<<1]==color[num<<1|1])
color[num]=color[num<<1];
else color[num]=-1;
sum[num]=sum[num<<1]+sum[num<<1|1];
}
void build(int num,int s,int e)
{
sum[num]=0;
val[num]=0;
color[num]=-1;
if(s==e)
{
color[num]=s;
return;
}
int mid=(s+e)>>1;
build(lson);
build(rson);
}
void update(int num,int s,int e,int l,int r,LL v)
{
if(l<=s && r>=e)
{
if(color[num]!=-1)
{
sum[num]+=(LL)Abs(v-color[num])*(e-s+1);
val[num]+=Abs(color[num]-v);
color[num]=v;
return;
}
}
int mid=(s+e)>>1;
pushdown(num,s,e);
if(l<=mid)update(lson,l,r,v);
if(r>mid)update(rson,l,r,v);
pushup(num);
}
LL query(int num,int s,int e,int l,int r)
{
if(l<=s && r>=e)
{
return sum[num];
}
int mid=(s+e)>>1;
pushdown(num,s,e);
if(r<=mid)return query(lson,l,r);
else if(l>mid)return query(rson,l,r);
else return query(lson,l,mid)+query(rson,mid+1,r);
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
build(1,1,n);
while(m--)
{
int type;
scanf("%d",&type);
if(type==1){
int l,r;
LL x;
scanf("%d%d%I64d",&l,&r,&x);
update(1,1,n,l,r,x);
}
else
{
int l,r;
scanf("%d%d",&l,&r);
printf("%I64d\n",query(1,1,n,l,r));
}
}
return 0;
}
/*
10 10
1 5 9 6
2 6 10
1 1 9 3
1 3 10 5
2 4 6
*/
codeforces 444 C. DZY Loves Colors(线段树),布布扣,bubuko.com
codeforces 444 C. DZY Loves Colors(线段树)
原文：http://blog.csdn.net/u010709592/article/details/37560847