题目链接：http://codeforces.com/contest/444/problem/C
给定一个长度为n的序列,初始时ai=i,vali=0(1≤i≤n).有两种操作:
- 将区间[L,R]的值改为x,并且当一个数从y改成x时它的权值vali会增加|x−y|.
- 询问区间[L,R]的权值和.
n≤10^5,1≤x≤10^6.
感觉这是一个比较好的考察线段树区间更新的性质。
当区间的a[i]一样时，区间更新即可，这是剪枝。
注意，lazy标记存的是增量。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + ;
struct SegTree {
LL l, r, Min, Max;
LL val, lazy;
}T[N << ]; LL Abs(LL a) {
return a < ? -a : a;
} void pushup(int p) {
T[p].Min = min(T[p << ].Min, T[(p << )|].Min);
T[p].Max = max(T[p << ].Max, T[(p << )|].Max);
T[p].val = T[p << ].val + T[(p << )|].val;
} void pushdown(int p) {
if(T[p].l == T[p].r) {
return ;
} else if(T[p].lazy) {
T[p << ].lazy += T[p].lazy;
T[(p << )|].lazy += T[p].lazy;
T[p << ].val += T[p].lazy*(LL)(T[p << ].r - T[p << ].l + );
T[(p << )|].val += T[p].lazy*(LL)(T[(p << )|].r - T[(p << )|].l + );
T[p << ].Min = T[p << ].Max = T[(p << )|].Max = T[(p << )|].Min = T[p].Min;
T[p].lazy = ;
}
} void build(int p, int l, int r) {
int mid = (l + r) >> ;
T[p].l = l, T[p].r = r, T[p].lazy = ;
if(l == r) {
T[p].Max = l, T[p].Min = l;
T[p].val = ;
return ;
}
build(p << , l, mid);
build((p << )|, mid + , r);
pushup(p);
} void update(int p, int l, int r, LL add) {
int mid = (T[p].l + T[p].r) >> ;
pushdown(p);
if(l == T[p].l && T[p].r == r && T[p].Min == T[p].Max) {
T[p].val += (LL)Abs(add - T[p].Min)*(LL)(r - l + );
T[p].lazy += Abs(add - T[p].Max);
T[p].Max = T[p].Min = add;
return ;
}
if(r <= mid) {
update(p << , l, r, add);
} else if(l > mid) {
update((p << )|, l, r, add);
} else {
update(p << , l, mid, add);
update((p << )|, mid + , r, add);
}
pushup(p);
} LL query(int p, int l, int r) {
int mid = (T[p].l + T[p].r) >> ;
pushdown(p);
if(l == T[p].l && T[p].r == r) {
return T[p].val;
}
if(r <= mid) {
return query(p << , l, r);
} else if(l > mid) {
return query((p << )|, l, r);
} else {
return query(p << , l, mid) + query((p << )|, mid + , r);
}
pushup(p);
} int main()
{
int n, m, l, r, c;
LL add;
scanf("%d %d", &n, &m);
build(, , n);
while(m--) {
scanf("%d %d %d", &c, &l, &r);
if(c == ) {
scanf("%lld", &add);
update(, l, r, add);
} else {
printf("%lld\n", query(, l, r));
}
}
return ;
}