「CF444C」DZY Loves Colors
DZY loves colors, and he enjoys painting.
On a colorful day, DZY gets a colorful ribbon, which consists of n units (they are numbered from 1 to n from left to right). The color of the i-th unit of the ribbon is i at first. It is colorful enough, but we still consider that the colorfulness of each unit is 0 at first.
DZY loves painting, we know. He takes up a paintbrush with color 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 currently is y. When it is painted by this paintbrush, the color of the unit becomes x, and the colorfulness of the unit increases by |x - y|.
DZY wants to perform m operations, each operation can be one of the following:
- Paint all the units with numbers between l and r (both inclusive) with color x.
- Ask the sum of colorfulness of the units between l and r (both inclusive).
Can you help DZY?
The first line contains two space-separated integers n, m (1 ≤ n, m ≤ 105).
Each of the next m lines begins with a integer type (1 ≤ type ≤ 2), which represents the type of this operation.
If type = 1, there will be 3 more integers l, r, x (1 ≤ l ≤ r ≤ n; 1 ≤ x ≤ 108) in this line, describing an operation 1.
If type = 2, there will be 2 more integers l, r (1 ≤ l ≤ r ≤ n) in this line, describing an operation 2.
For each operation 2, print a line containing the answer — sum of colorfulness.
|
1 2 3 4 |
3 3 1 1 2 4 1 2 3 5 2 1 3 |
|
1 |
8 |
|
1 2 3 4 5 |
3 4 1 1 3 4 2 1 1 2 2 2 2 3 3 |
|
1 2 3 |
3 2 1 |
|
1 2 3 4 5 6 7 |
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 |
|
1 |
129 |
In the first sample, the color of each unit is initially [1, 2, 3], and the colorfulness is [0, 0, 0].
After the first operation, colors become [4, 4, 3], colorfulness become [3, 2, 0].
After the second operation, colors become [4, 5, 5], colorfulness become [3, 3, 2].
So the answer to the only operation of type 2 is 8.
题解
把相同的一段合并，修改的时候一次性修改T T
这样可以证明是nlogn的T T
注意longlong
|
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 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 |
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #define ll long long using namespace std; inline ll read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m; struct data{int l,r,c,ctag,size;ll ans,atag;}t[400005]; void pushdown(int k) { if(t[k].l==t[k].r)return; int ctag=t[k].ctag;ll atag=t[k].atag; t[k].ctag=t[k].atag=0; if(ctag) { t[k<<1].c=ctag;t[k<<1|1].c=ctag; t[k<<1].ctag=ctag;t[k<<1|1].ctag=ctag; } if(atag) { t[k<<1].atag+=atag;t[k<<1|1].atag+=atag; t[k<<1].ans+=t[k<<1].size*atag; t[k<<1|1].ans+=t[k<<1|1].size*atag; } } inline void pushup(int k) { if(t[k<<1].c==t[k<<1|1].c) t[k].c=t[k<<1].c; else t[k].c=-1; t[k].ans=t[k<<1].ans+t[k<<1|1].ans; } ll query(int k,int x,int y) { pushdown(k); int l=t[k].l,r=t[k].r; if(l==x&&y==r) return t[k].ans; int mid=(l+r)>>1; if(y<=mid)return query(k<<1,x,y); else if(x>mid)return query(k<<1|1,x,y); else return query(k<<1,x,mid)+query(k<<1|1,mid+1,y); } void update(int k,int x,int y,int val) { pushdown(k); int l=t[k].l,r=t[k].r; if(l==x&&y==r&&t[k].c!=-1) { ll tmp=abs(t[k].c-val); t[k].ans+=t[k].size*tmp; t[k].atag+=tmp; t[k].c=val; t[k].ctag=val; return; } int mid=(l+r)>>1; if(y<=mid)update(k<<1,x,y,val); else if(x>mid)update(k<<1|1,x,y,val); else { update(k<<1,x,mid,val); update(k<<1|1,mid+1,y,val); } pushup(k); } void build(int k,int l,int r) { t[k].l=l;t[k].r=r;t[k].size=r-l+1;t[k].c=-1; if(l==r) { t[k].c=l;return; } int mid=(l+r)>>1; build(k<<1,l,mid);build(k<<1|1,mid+1,r); } int main() { n=read();m=read(); build(1,1,n); for(int i=1;i<=m;i++) { int f=read(),l=read(),r=read(); if(f==1) { int x=read(); update(1,l,r,x); } else { printf("%I64d\n",query(1,l,r)); } } return 0; } |
OI 课件=>
