当前位置：网站首页>codeforces 444C DZY Loves Colors

codeforces 444C DZY Loves Colors

2022-08-08 14:58:00 【51CTO】


​ ​http://www.elijahqi.win/2018/03/07/codeforces-444c/​​​ ‎
题目描述

DZY loves colors, and he enjoys painting.

On a colorful day, DZY gets a colorful ribbon, which consists of

n
n units (they are numbered from

1
1 to

n
n from left to right). The color of the

i
i -th unit of the ribbon is

i
i at first. It is colorful enough, but we still consider that the colorfulness of each unit is

0
0 at first.

DZY loves painting, we know. He takes up a paintbrush with color

x
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
i currently is

y
y . When it is painted by this paintbrush, the color of the unit becomes

x
x , and the colorfulness of the unit increases by

|x-y|
∣x−y∣ .

DZY wants to perform

m
m operations, each operation can be one of the following:

Paint all the units with numbers between
l

l and r

r (both inclusive) with color x

x .
Ask the sum of colorfulness of the units between
l

l and r

r (both inclusive).
Can you help DZY?

输入输出格式

输入格式：
The first line contains two space-separated integers n,m(1<=n,m<=105) n , m ( 1 <= n , m <= 10 5 )

Each of the next

m
m lines begins with a integer type(1<=type<=2) t y p e ( 1 <= t y p e <= 2 )

If

type=1
type=1 , there will be

3
3 more integers l,r,x(1<=l<=r<=n;1<=x<=108) l , r , x ( 1 <= l <= r <= n ; 1 <= x <= 10 8 )

1
1 .

If

type=2
type=2 , there will be

2
2 more integers l,r(1<=l<=r<=n) l , r ( 1 <= l <= r <= n )

2
2 .

输出格式：
For each operation

2
2 , print a line containing the answer — sum of colorfulness.

输入输出样例

输入样例#1： 复制

3 3
1 1 2 4
1 2 3 5
2 1 3
输出样例#1： 复制

8
输入样例#2： 复制

3 4
1 1 3 4
2 1 1
2 2 2
2 3 3
输出样例#2： 复制

3
2
1
输入样例#3： 复制

10 6
1 1 5 3
1 2 7 9
1 10 10 11
1 3 8 12
1 1 10 3
2 1 10
输出样例#3： 复制

129
说明

In the first sample, the color of each unit is initially

[1,2,3]
[1,2,3] , and the colorfulness is

[0,0,0]
[0,0,0] .

After the first operation, colors become

[4,4,3]
[4,4,3] , colorfulness become

[3,2,0]
[3,2,0] .

After the second operation, colors become

[4,5,5]
[4,5,5] , colorfulness become

[3,3,2]
[3,3,2] .

So the answer to the only operation of type

2
2 is

8
8 .

每次可以覆盖一个区间 然后每次覆盖都会获得一些收益 即 abs(v-a[i]) 那么 直接类似线段树懒标记即可 复杂度大约是(n+m)log(n) 因为大概每次询问最多分裂两个区间

或者询问区间贡献和 每次下放 的时候直接下放纯色区间 查询的时候也直接一直往下走 走到纯色的地方 注意 染色之后需要合并懒标记

      
      

       
       #include<cmath>
       
       
#include<cstdio>
       
       
#include<algorithm>
       
       
#define N 110000
       
       
#define ll long long
       
       
using namespace std;
       
       
inline char gc(){
       
       
    static char now[1<<16],*S,*T;
       
       
    if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
       
       
    return *S++;
       
       
}
       
       
inline int read(){
       
       
    int x=0,f=1;char ch=gc();
       
       
    while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();}
       
       
    while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc();
       
       
    return x*f;
       
       
}
       
       
struct node{
       
       
    int left,right,lazy;ll sum,add;
       
       
}tree[N<<1];
       
       
int num,root,n,m;
       
       
inline void build(int &x,int l,int r){
       
       
    x=++num;if (l==r) {tree[x].lazy=l;return;}
       
       
    int mid=l+r>>1;build(tree[x].left,l,mid);build(tree[x].right,mid+1,r);
       
       
}
       
       
inline void update(int x){
       
       
    int l=tree[x].left,r=tree[x].right;
       
       
    tree[x].sum=tree[l].sum+tree[r].sum;
       
       
    if (tree[l].lazy==tree[r].lazy) tree[x].lazy=tree[l].lazy;else tree[x].lazy=0;
       
       
}
       
       
inline void pushdown(int x,int l1,int r1){
       
       
    if(!tree[x].lazy) return;
       
       
    int l=tree[x].left,r=tree[x].right,lz=tree[x].lazy;
       
       
    tree[l].lazy=lz;tree[r].lazy=lz;int mid=l1+r1>>1;
       
       
    tree[l].add+=tree[x].add;tree[r].add+=tree[x].add;
       
       
    tree[l].sum+=(ll)(mid-l1+1)*tree[x].add;
       
       
    tree[r].sum+=(ll)(r1-mid)*tree[x].add;
       
       
    tree[x].add=0;
       
       
}
       
       
inline void insert1(int x,int l,int r,int l1,int r1,int v){
       
       
    if (l1<=l&&r1>=r&&tree[x].lazy){
       
       
        tree[x].sum+=(ll)(r-l+1)*abs(v-tree[x].lazy);
       
       
        tree[x].add+=abs(v-tree[x].lazy);tree[x].lazy=v;return;
       
       
    }int mid=l+r>>1;pushdown(x,l,r);
       
       
    if(l1<=mid) insert1(tree[x].left,l,mid,l1,r1,v);
       
       
    if (r1>mid) insert1(tree[x].right,mid+1,r,l1,r1,v);update(x);
       
       
}
       
       
inline ll query(int x,int l,int r,int l1,int r1){
       
       
    if(l1<=l&&r1>=r) return tree[x].sum;int mid=l+r>>1;ll tmp=0;pushdown(x,l,r);
       
       
    if (l1<=mid) tmp+=query(tree[x].left,l,mid,l1,r1);
       
       
    if (r1>mid) tmp+=query(tree[x].right,mid+1,r,l1,r1);return tmp;
       
       
}
       
       
inline void print(int x,int l,int r){
       
       
    int mid=l+r>>1;//pushdown(x);
       
       
    if (tree[x].left) print(tree[x].left,l,mid);
       
       
    printf("%d %d %lld %lld %d\n",l,r,tree[x].sum,tree[x].add,tree[x].lazy);
       
       
    if (tree[x].right) print(tree[x].right,mid+1,r);
       
       
}
       
       
int main(){
       
       
    freopen("cf444c.in","r",stdin);
       
       
    freopen("cf.out","w",stdout);
       
       
    n=read();m=read();build(root,1,n);
       
       
    for (int i=1;i<=m;++i){
       
       
        int op=read(),l=read(),r=read();
       
       
        if (op==1){int v=read();insert1(root,1,n,l,r,v);}
       
       
        else printf("%lld\n",query(root,1,n,l,r));
       
       
    }
       
       
    return 0;
       
       
}
      
      

      
      
    
       
       
  • 1.
    • 
       
       
  • 2.
    • 
       
       
  • 3.
    • 
       
       
  • 4.
    • 
       
       
  • 5.
    • 
       
       
  • 6.
    • 
       
       
  • 7.
    • 
       
       
  • 8.
    • 
       
       
  • 9.
    • 
       
       
  • 10.
    • 
       
       
  • 11.
    • 
       
       
  • 12.
    • 
       
       
  • 13.
    • 
       
       
  • 14.
    • 
       
       
  • 15.
    • 
       
       
  • 16.
    • 
       
       
  • 17.
    • 
       
       
  • 18.
    • 
       
       
  • 19.
    • 
       
       
  • 20.
    • 
       
       
  • 21.
    • 
       
       
  • 22.
    • 
       
       
  • 23.
    • 
       
       
  • 24.
    • 
       
       
  • 25.
    • 
       
       
  • 26.
    • 
       
       
  • 27.
    • 
       
       
  • 28.
    • 
       
       
  • 29.
    • 
       
       
  • 30.
    • 
       
       
  • 31.
    • 
       
       
  • 32.
    • 
       
       
  • 33.
    • 
       
       
  • 34.
    • 
       
       
  • 35.
    • 
       
       
  • 36.
    • 
       
       
  • 37.
    • 
       
       
  • 38.
    • 
       
       
  • 39.
    • 
       
       
  • 40.
    • 
       
       
  • 41.
    • 
       
       
  • 42.
    • 
       
       
  • 43.
    • 
       
       
  • 44.
    • 
       
       
  • 45.
    • 
       
       
  • 46.
    • 
       
       
  • 47.
    • 
       
       
  • 48.
    • 
       
       
  • 49.
    • 
       
       
  • 50.
    • 
       
       
  • 51.
    • 
       
       
  • 52.
    • 
       
       
  • 53.
    • 
       
       
  • 54.
    • 
       
       
  • 55.
    • 
       
       
  • 56.
    • 
       
       
  • 57.
    • 
       
       
  • 58.
    • 
       
       
  • 59.
    • 
       
       
  • 60.
    • 
       
       
  • 61.
    • 
       
       
  • 62.
    • 
       
       
  • 63.
    • 
       
       
  • 64.
    • 
       
       
  • 65.
    • 
       
       
  • 66.
    • 
       
       
  • 67.
    • 
       
       
  • 68.
    • 
       
       
  • 69.
    •


原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/u_15744996/5555924

边栏推荐

猜你喜欢

随机推荐