codeforces 445E - DZY Loves Colors

n個のノード、各ノードには1つの色と1つの重み値があり、初期色は1-nの順で、重み値は初期は0である.
2つの操作があります.
1、区間[L,R]内の全ての接点をcに染色し、各接点の重み増加量は元の色と現在の色の差の絶対値とする.
2、区間[L,R]のノードの重み値とを求める.
分析:
第2の操作では、セグメントツリーの基本操作の1つであることは明らかです.区間和です.
第1の動作では、区間の色状況を1つのタグ配列colで表すことができる.colが0であれば、その区間の色の種類が統一されていないことを示し、そうでなければ色値を示す.
では、更新するときは、ある区間の色が同じになるまで、その区間を更新し、徐々にアップデートします.

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
typedef __int64 LL;
#define N 100000
#define lson l,m,rt<<1
#define rson m+1,r,(rt<<1)|1
LL s[N<<2],add[N<<2],col[N<<2];
inline void PushUp(int rt){
    s[rt]=s[rt<<1]+s[(rt<<1)|1];
    if(col[rt<<1]&&col[rt<<1]==col[rt<<1|1]) col[rt]=col[rt<<1];
    else col[rt]=0;
}
inline void PushDown(int rt,int m)
{
    if(add[rt])
    {
        add[rt<<1]+=add[rt];
        add[(rt<<1)|1]+=add[rt];
        col[rt<<1]=col[(rt<<1)|1]=col[rt];
        s[rt<<1]+=add[rt]*(m-(m>>1));
        s[(rt<<1)|1]+=add[rt]*(m>>1);
        add[rt]=0;
    }
}
void update(int L,int R,int c,int l,int r,int rt)
{
        if(L<=l&&r<=R&&col[rt]) //  ：          ，   ！！！
        {
            add[rt]+=abs(col[rt]-c);
            s[rt]+=(LL)abs(col[rt]-c)*(r-l+1);
            col[rt]=c;
            return;
        }
        PushDown(rt,r-l+1);
        int m=(l+r)>>1;
        if(L<=m) update(L,R,c,lson);
        if(m<R) update(L,R,c,rson);
        PushUp(rt);
}

LL query(int L,int R,int l,int r,int rt)
{
    if(L<=l&&r<=R) return s[rt];
    PushDown(rt,r-l+1);
    int m=(l+r)>>1;
    LL ret=0;
    if(L<=m) ret+=query(L,R,lson);
    if(m<R) ret+=query(L,R,rson);
    return ret;
}

void build(int l,int r,int rt){
    if(l==r){
        col[rt]=l;
        return;
    }
    int m=(l+r)>>1;
    build(lson);
    build(rson);
    PushUp(rt);
}
int main()
{
    int n,T,L,R,m,x;
    scanf("%d%d",&n,&m);
    memset(col,0,sizeof(col));
    build(1,n,1);
    while(m--)
    {
        scanf("%d%d%d",&T,&L,&R);
        if(T==1){
            scanf("%d",&x);
            update(L,R,x,1,n,1);
        }
        else
            printf("%I64d
",query(L,R,1,n,1));
    }
    return 0;
}