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

codeforces 444C DZY Loves Colors

2022-08-08 15:14: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 .

One interval can be covered at a time Then each overwrite gets some benefit 即 abs(v-a[i]) 那么 It is directly similar to the line segment sloth marker 复杂度大约是(n+m)log(n) Because presumably each query splits at most two intervals

Or ask about the interval contribution sum every release When it is time to directly lower the solid color range When inquiring, go straight down Go to a solid color 注意 Lazy markers need to be merged after staining

      
      

       
       #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://yzsam.com/2022/220/202208081445530610.html

边栏推荐

猜你喜欢

随机推荐