题目链接：
http://codeforces.com/problemset/problem/444/C
J. DZY Loves Colors
time limit per test：2 secondsmemory limit per test：256 megabytes
#### 问题描述
> DZY loves colors, and he enjoys painting.
>
> On a colorful day, DZY gets a colorful ribbon, which consists of n units (they are numbered from 1 to n from left to right). The color of the i-th unit of the ribbon is i at first. It is colorful enough, but we still consider that the colorfulness of each unit is 0 at first.
>
> DZY loves painting, we know. He takes up a paintbrush with color x and uses it to draw a line on the ribbon. In such a case some contiguous units are painted. Imagine that the color of unit i currently is y. When it is painted by this paintbrush, the color of the unit becomes x, and the colorfulness of the unit increases by |x - y|.
>
> DZY wants to perform m operations, each operation can be one of the following:
>
> Paint all the units with numbers between l and r (both inclusive) with color x.
> Ask the sum of colorfulness of the units between l and r (both inclusive).
> Can you help DZY?
#### 输入
> The first line contains two space-separated integers n, m (1 ≤ n, m ≤ 105).
>
> Each of the next m lines begins with a integer type (1 ≤ type ≤ 2), which represents the type of this operation.
>
> If type = 1, there will be 3 more integers l, r, x (1 ≤ l ≤ r ≤ n; 1 ≤ x ≤ 108) in this line, describing an operation 1.
>
> If type = 2, there will be 2 more integers l, r (1 ≤ l ≤ r ≤ n) in this line, describing an operation 2.
#### 输出
> For each operation 2, print a line containing the answer — sum of colorfulness.
#### 样例
> **sample input**
> 3 3
> 1 1 2 4
> 1 2 3 5
> 2 1 3
>
> **sample output**
> 8
题意
初始的时候第i个位子的颜色是i，每个位子的值是0，现在用一把刷子，能把一段区间刷成颜色y，对于每个位子的值会增加abs(y-x)(x代表原先的颜色)。 并且给你区间（l,r），要你输出当前区间的值的和是多少
题解
线段树。
和普通的区间更新有点不一样，因为你刷一个区间，由于区间内有可能不止一种颜色，那你就没办法马上算出贡献值了。
所以我们增加一个Clear()函数，当我们找到需要更新的子区间的时候，在打标标记之前，先Clear()一下，把子区间下面的区间的标记统统清除掉，同时把更新的值维护上来。（我们只有当clear()到一段颜色相同的区间的时候，才能更新，否则就Clear()递归下去。）
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define lson (o<<1)
#define rson ((o<<1)|1)
#define M l+(r-l)/2
using namespace std;
const int maxn=1e5+10;
typedef __int64 LL;
//mark标记区间的颜色
//sumv计算区间的贡献值的和
//addv计算区间的增量
LL sumv[maxn<<2],addv[maxn<<2];
LL mark[maxn<<2];
int n,m;
void pushdown(int o){
if(mark[o]>0){
mark[lson]=mark[rson]=mark[o];
mark[o]=0;
}
}
void build(int o,int l,int r){
if(l==r){
mark[o]=l;
}else{
build(lson,l,M);
build(rson,M+1,r);
mark[o]=0;
}
}
void maintain(int o,int l,int r){
sumv[o]=sumv[lson]+sumv[rson]+addv[o]*(r-l+1);
}
int ql,qr,_v;
//Clear()到一段颜色相同的区间才能计算贡献值
void Clear(int o,int l,int r){
if(mark[o]>0){
addv[o]+=abs(mark[o]-_v);
sumv[o]+=abs(mark[o]-_v)*(r-l+1);
}else{
Clear(lson,l,M);
Clear(rson,M+1,r);
maintain(o,l,r);
}
mark[o]=0;
}
void update(int o,int l,int r){
if(ql<=l&&r<=qr){
Clear(o,l,r);
mark[o]=_v;
}else{
pushdown(o);
if(ql<=M) update(lson,l,M);
if(qr>M) update(rson,M+1,r);
maintain(o,l,r);
}
}
LL _sum;
void query(int o,int l,int r,LL add){
if(ql<=l&&r<=qr){
_sum+=sumv[o]+add*(r-l+1);
}else{
if(ql<=M) query(lson,l,M,add+addv[o]);
if(qr>M) query(rson,M+1,r,add+addv[o]);
}
}
void init(){
memset(sumv,0,sizeof(sumv));
memset(addv,0,sizeof(addv));
memset(mark,0,sizeof(mark));
}
int main(){
init();
scanf("%d%d",&n,&m);
build(1,1,n);
while(m--){
int cmd;
scanf("%d%d%d",&cmd,&ql,&qr);
if(cmd==1){
scanf("%d",&_v);
update(1,1,n);
}else{
_sum=0;
query(1,1,n,0);
printf("%I64d\n",_sum);
}
}
return 0;
}