DZY Loves Colors

CF #446C:http://codeforces.com/problemset/problem/444/C

题意：给你n个数，大小从1到n，然后又两种操作，1 a b c表示把区间a b 更新为c,那么每个数与之前的数有一个改变量|c-ai|, 2 a b 表示查询a b 之间的改变量。

题解：正解必然是线段树。但是线段树的lazy还是不会用，以及要维护的东西也不清楚，这道水线段树都不会。一个值 mul维护当前的数，ans表示总的改变量，sum表示改变量。这里只有mul！=0才开始更新，否则pushdown();

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 #include<map>

 #include<set>

 using namespace std;

 const int N=*1e5+;

 int n,m;

 int a,b,c;

 long long d,cnt;

 struct Node{

     int l,r;

    long long ans;

    long long  val,mul;

    long long sum;

    inline int mid(){

      return (l+r)/;

    }

    inline int len(){

      return  r-l+;

    }

 }num[N*];

 void pushup(int rt){

    if(num[rt<<].mul==num[rt<<|].mul)

     num[rt].mul=num[rt<<].mul;

    num[rt].ans=num[rt<<].ans+num[rt<<|].ans;

 }

 void pushdown(int rt){

    if(num[rt].mul!=){

        num[rt<<|].mul=num[rt<<].mul=num[rt].mul;

        num[rt<<].ans+=num[rt].sum*num[rt<<].len();

        num[rt<<|].ans+=num[rt].sum*num[rt<<|].len();

        num[rt<<].sum+=num[rt].sum;

        num[rt<<|].sum+=num[rt].sum;

        num[rt].mul=num[rt].sum=;

    }

 }

 void build(int l,int r,int rt){

     num[rt].l=l;

     num[rt].r=r;

     num[rt].mul=num[rt].ans=num[rt].sum=;

     if(l==r){

         num[rt].mul=++cnt;

         return;

     }

    int mid=(l+r)/;

    build(l,mid,rt<<);

    build(mid+,r,rt<<|);

    pushup(rt);

 }

 void update(int l,int r,int rt,long long  val){

     if(num[rt].l==l&&num[rt].r==r&&num[rt].mul){

             num[rt].sum+=abs(num[rt].mul-val);

             num[rt].ans+=abs(num[rt].mul-val)*num[rt].len();

             num[rt].mul=val;

             return;

     }

     pushdown(rt);

     int mid=num[rt].mid();

     if(mid>=r)update(l,r,rt<<,val);

     else if(mid<l)update(l,r,rt<<|,val);

     else{

         update(l,mid,rt<<,val);

         update(mid+,r,rt<<|,val);

     }

     pushup(rt);

 }

 long long query(int l,int r,int rt){

     if(num[rt].l==l&num[rt].r==r){

         return num[rt].ans;

     }

     pushdown(rt);

     int mid=num[rt].mid();

     if(mid>=r)return query(l,r,rt<<);

     else if(mid<l)return query(l,r,rt<<|);

     else{

         return query(l,mid,rt<<)+query(mid+,r,rt<<|);

     }

     pushup(rt);

 }

 int main(){

     while(~scanf("%d%d",&n,&m)){

             cnt=;

         build(,n,);

         for(int i=;i<=m;i++){

             scanf("%d%d%d",&a,&b,&c);

             if(a==){

                 scanf("%I64d",&d);

                 update(b,c,,d);

             }

             else

                 printf("%I64d\n",query(b,c,));

         }

     }

 }

巴特西

DZY Loves Colors

最新文章

热门文章