题面

题目描述

DZY喜欢色彩，他热爱绘画。

在一个多姿多彩的日子里，$DZY$得到了一个彩色的缎带，它由$N$个单元组成（从左到右从$1$到$n$编号）。色带的第$i$个单位的最初颜色是$i$。虽然颜色足够丰富，但我们仍然认为每个单元的颜色数量最初是$0$。

我们知道$DZY$热衷于绘画。他拿起一把彩色笔，用它在缎带上画一条线。在这种情况下，他就绘制了一段连续的单元。想象一下，单位$i$被涂之前颜色是$y$。被涂之后时，单元的颜色变为$x$，令单位的颜色增加了$|x-y|$。 $DZY$想要执行$M$个操作，每个操作可以是下列操作之一：

1、将区间$[L,R]$内单元绘制为颜色$x$。

2、询问$[L,R]$之间的单位颜色的总和（包括两者）。

你能帮助$DZY$吗？

输入：

第一行包含用空格隔开的整数$n,m$（$1 \leq n\leq m \leq 10^5$）。

接下来$m$行中的每一行都以一个整数开头（$1\leq tyqe \leq 2$）开始，表示该操作的类型。

如果$type = 1$，则在该行中，有$3$个整数$L,R,x(1 \leq L \leq R \leq n; 1\leq x \leq 10^8)$，表示操作$1$。

如果$type=2$，则这一行，有$2$个整数$L,R,(1 \leq L \leq R \leq n)$，表示操作$2$。

输出：

对于每个操作$2$，输出一行，包含着色数量的和。

思路：

这是一个区间覆盖的题，不经过思考就想到了$Old\ Driver\ Tree$，然后配合着线段树，就用数据结构过去了qaq

时间复杂度分析

O(玄学)最坏的查询是$log$级的，显然不是影响时间复杂度关键，假设所有都是修改操作，修改绝大多数的时候都是使原本$n$个点变少的，最坏的情况应该是把同一个区间分裂成三个不同的区间，也就是每次把三个连在一起，再把一个区间分开三个，似乎复杂度也不会很高，最多三倍，加上$lower_bound$的$log$和线段树的$log$，时间复杂度$O(能过)$，结束，cheer

Code：

#include<bits/stdc++.h>
#define It set<node>::iterator 
#define N 100010
#define ll long long
using namespace std;
struct node{//用于ODT
    int l,r;
    mutable int val;
    node(int a,int b=-1,int c=0):l(a),r(b),val(c){    }
    node(){    }
    bool operator< (const node x) const{
        return l<x.l;
    }
};
int n,T,L,R,val,y;
ll f[N<<2],tag[N<<2],ans;//线段树，别忘了开ll
set<node>s;
It Itl,Itr,it;//迭代器
inline int read(){
    register int s=0;
    register char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c))
    {
        s=(s<<1)+(s<<3)+c-'0';
        c=getchar();
    }
    return s;
}
It Split(int pos)//分离
{
    it=s.lower_bound(node(pos));
    if(it!=s.end() && it->l ==pos) return it;
    --it;
    int l=it->l,r=it->r,val=it->val;
    s.erase(it);
    s.insert(node(l,pos-1,val));
    return s.insert(node(pos,r,val)).first;//返回的是pair类型，第一段关键字是插入位置的迭代器
}
void push(int k,int l,int r)
{
    f[k]+=tag[k]*(r-l+1);
    if(l!=r)
    {
        int cur=k<<1;
        tag[cur]+=tag[k];
        tag[cur|1]+=tag[k];
    }
    tag[k]=0;
}
void Modify(int k,int l,int r)
{
    if(tag[k]) push(k,l,r);
    if(r<L||R<l) return;
    if(L<=l&&r<=R)
    {
        tag[k]=y;
        push(k,l,r);
        return;
    }
    int mid=(l+r)>>1,cur=k<<1;
    Modify(cur,l,mid);
    Modify(cur|1,mid+1,r);
    f[k]=f[cur]+f[cur|1];
}
void Cov(int l,int r)
{
    Itr=Split(r+1);it=Itl=Split(l);
    for(;it!=Itr;++it)
    {
        L=it->l;R=it->r;y=abs(val- it->val);
        Modify(1,1,n);
    }
    s.erase(Itl,Itr);
    s.insert(node(l,r,val));//记得这里要重新插入过
}
void Query(int k,int l,int r)
{
    if(tag[k]) push(k,l,r);
    if(r<L||R<l) return;
    if(L<=l&&r<=R){ans+=f[k];return;}
    int mid=(l+r)>>1,cur=k<<1;
    Query(cur,l,mid);
    Query(cur|1,mid+1,r);
}
int main()
{
    int i;
    n=read();T=read();
    for(i=1;i<=n;i++)
        s.insert(node(i,i,i));
    while(T--)
    {
        if(read()==1)
        {
            L=read(),R=read(),val=read();
            Cov(L,R);
        }
        else
            ans=0,L=read(),R=read(),Query(1,1,n),printf("%lld\n",ans);
    }
    return 0;
}

devil.