http://codeforces.com/contest/444/problem/C
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?
Input
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.
Output
For each operation 2, print a line containing the answer — sum of colorfulness.
Examples
Input
3 3 1 1 2 4 1 2 3 5 2 1 3
Output
8
Input
3 4 1 1 3 4 2 1 1 2 2 2 2 3 3
Output
3 2 1
Input
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
Output
129
Note
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.
C++版本一
分块
https://www.cnblogs.com/MingSD/p/9119191.html
#include <iostream>
#include<string.h>
#include<algorithm>
#include<math.h>
#include <stdio.h>
using namespace std;
typedef long long ll;
const int N=500000+100;
int n,m,sq,bl[N],op,L[N],R[N],tot;
ll a[N],b[N],tag[N],lz[N],sum[N];
void pushdown(int rt){
for(int i=L[rt];i<=R[rt];i++){
a[i]=tag[rt];
}
tag[rt]=0;
}
void updata(int l ,int r ,ll x){
int rx=bl[l],ry=bl[r];
if(rx==ry){
if(tag[rx])pushdown(rx);
for(int i=l;i<=r;i++){
sum[rx]+=abs(a[i]-x);
b[i]+=abs(a[i]-x);
a[i]=x;
}
}else{
if(tag[rx])pushdown(rx);
if(tag[ry])pushdown(ry);
for(int i=l;i<=R[rx];i++){
sum[rx]+=abs(a[i]-x);
b[i]+=abs(a[i]-x);
a[i]=x;
}
for(int i=rx+1;i<=ry-1;i++){
if(tag[i]){
lz[i]+=abs(tag[i]-x);
sum[i]+=(R[i]-L[i]+1)*abs(tag[i]-x);
}else{
for(int j=L[i];j<=R[i];j++){
sum[i]+=abs(a[j]-x);
b[j]+=abs(a[j]-x);
a[j]=x;
}
}
tag[i]=x;
}
for(int i=L[ry];i<=r;i++){
sum[ry]+=abs(a[i]-x);
b[i]+=abs(a[i]-x);
a[i]=x;
}
}
}
ll query(int l,int r){
ll ans=0;
int rx=bl[l],ry=bl[r];
if(rx==ry){
for(int i=l;i<=r;i++){
ans+=(b[i]+lz[rx]);
}
}else{
for(int i=l;i<=R[rx];i++){
ans+=(b[i]+lz[rx]);
}
for(int i=rx+1;i<=ry-1;i++){
ans+=sum[i];
}
for(int i=L[ry];i<=r;i++){
ans+=(b[i]+lz[ry]);
}
}
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
sq=sqrt(n);
tot=n/sq;
if(n%sq)tot++;
for(int i=1;i<=tot;i++){
L[i]=(i-1)*sq+1;
R[i]=i*sq;
}
R[tot]=n;
for(int i=1;i<=n;i++){
bl[i]=(i-1)/sq+1;
a[i]=i;
b[i]=0;
}
int l,r;
ll x;
while(m--){
scanf("%d",&op);
if(op==1){
scanf("%d%d%I64d",&l,&r,&x);
updata(l,r,x);
}else{
scanf("%d%d",&l,&r);
cout << query(l,r) << endl;
}
}
//cout << "Hello world!" << endl;
return 0;
}
C++版本二
线段树
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
typedef long long LL;
using namespace std;
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define CLEAR( a , x ) memset ( a , x , sizeof a )
const int maxn=1e5+100;
LL col[maxn<<2],sum[maxn<<2],d[maxn<<2];//col[i]!=0代表区间颜色都为col[i]；d[i]用于lazy操作
int n,m;
void pushup(int rs)
{
if(col[rs<<1]==col[rs<<1|1]) col[rs]=col[rs<<1];
else col[rs]=0;
sum[rs]=sum[rs<<1]+sum[rs<<1|1];
}
void pushdown(int rs,int m)
{
if(col[rs])
{
col[rs<<1]=col[rs<<1|1]=col[rs];
d[rs<<1]+=d[rs];d[rs<<1|1]+=d[rs];
sum[rs<<1]+=(LL)(m-(m>>1))*d[rs];
sum[rs<<1|1]+=(LL)(m>>1)*d[rs];
d[rs]=col[rs]=0;
}
}
void build(int rs,int l,int r)
{
if(l==r)
{
sum[rs]=0;
col[rs]=l;
return ;
}
col[rs]=d[rs]=0;
int mid=(l+r)>>1;
build(rs<<1,l,mid);
build(rs<<1|1,mid+1,r);
pushup(rs);
}
void update(int rs,int x,int y,int l,int r,int c)
{
if(l>=x&&r<=y&&col[rs])
{
sum[rs]+=abs(col[rs]-c)*(LL)(r-l+1);
d[rs]+=abs(col[rs]-c);
col[rs]=c;
return ;
}
pushdown(rs,r-l+1);
int mid=(l+r)>>1;
if(x<=mid) update(rs<<1,x,y,l,mid,c);
if(y>mid) update(rs<<1|1,x,y,mid+1,r,c);
pushup(rs);
}
LL query(int rs,int x,int y,int l,int r)
{
// cout<<"2333 "<<<<endl;
if(l>=x&&y>=r)
return sum[rs];
// if(l==r) return sum[rs];
int mid=(l+r)>>1;
pushdown(rs,r-l+1);
LL res=0;
if(x<=mid) res+=query(rs<<1,x,y,l,mid);
if(y>mid) res+=query(rs<<1|1,x,y,mid+1,r);
return res;
}
int main()
{
// std::ios::sync_with_stdio(false);
int l,r,x,op;
while(~scanf("%d%d",&n,&m))
{
build(1,1,n);
while(m--)
{
scanf("%d",&op);
if(op==1)
{
scanf("%d%d%d",&l,&r,&x);
update(1,l,r,1,n,x);
}
else
{
scanf("%d%d",&l,&r);
printf("%I64d\n",query(1,l,r,1,n));
}
}
}
return 0;
}
京公网安备 11010502036488号