本文主要是介绍Codeforces 444C DZY Loves Colors 线段树区间更新，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
// Codeforces 444C DZY Loves Colors 线段树区间更新// 题目链接:// http://codeforces.com/problemset/problem/444/C// 题目大意:// 有长度为n的数组,起始值A[i] = i,val[i] = 0现给两种操作
// 1 left right x:
// 将A[left],A[left + 1].....A[right]都改为x,val[i] = abs(x - A[i]);
// 2 left right
// 统计[left,right]的val之和// 自己思路:// 说来惭愧,想的太简单了,注意到只是第一次的修改不同,特判第一次的变化,
// 之后的变化可以简单地成段更新,所以维护三个值,一个sum肯定的,一个col表示
// 是否是第一次修改,laz表示累加值,但是这样貌似push_down()不好写,就是错在
// 这里,思路上还有很大的欠缺.太菜了// 正解思路:// 也是维持三个变量,一个laz,一个col,一个最后答案sum.laz表示累加的变化
// (这个是很常见的累加),col表示该区间的颜色,如果不是一种,则为0.更新的时候
// 更新到颜色相同的一块上(看大牛的证明没看懂,如果有大神能够指点迷津,小子将
// 愿奉上2.56程序员的祝福),然后普通的区间更新,区间求和.// 感悟:// 自己太菜,继续努力奋斗^ _ ^,图中的注释是自己写的原思路,给自己留作纪念,
// 以及debug时候的代码#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>using namespace std;
typedef long long ll;const int MAXN = 1e5 + 8;struct SegmentTree{
#define lson(x) (x << 1)
#define rson(x) (x << 1 | 1)ll sum[MAXN << 2];int col[MAXN << 2];ll laz[MAXN << 2];int val;int ql,qr;void init(){memset(sum,0,sizeof(sum));memset(col,0,sizeof(col));memset(laz,0,sizeof(laz));}void setlr(int l,int r){ql = l;qr = r;}void setv(int v){val = v;}void push_up(int rt){// cout << rt << " lson: " << sum[lson(rt)] << " " << sum[rson(rt)] << endl;if (col[lson(rt)] == col[rson(rt)]){col[rt] = col[lson(rt)];}elsecol[rt] = 0;sum[rt] = sum[lson(rt)] + sum[rson(rt)];}void push_down(int rt,int L,int R){int M = (L + R) >> 1;if (col[rt] > 0){col[lson(rt)] = col[rt];col[rson(rt)] = col[rt];laz[lson(rt)] += laz[rt];laz[rson(rt)] += laz[rt];sum[lson(rt)] += (ll)(M - L + 1) * laz[rt];sum[rson(rt)] += (ll)(R - M) * laz[rt];col[rt] = 0;laz[rt] = 0;}// cout << rt << " " << L << " " << R << " laz " << laz[rt] << " col " << col[rt] << endl;// if (laz[rt] > 0){
// laz[lson(rt)] = laz[rt];
// laz[rson(rt)] = laz[rt];
//
// if (col[rt] > 0){
// sum[lson(rt)] += (ll)abs(laz[rt] - col[rt]) * (M - L + 1);
// sum[rson(rt)] += (ll)abs(laz[rt] - col[rt]) * (R - M + 1);
// }else {
// sum[lson(rt)] += abs((ll)laz[rt] * (M - L + 1) - (ll)(L + M) * (M - L + 1) / 2);
// sum[rson(rt)] += abs((ll)laz[rt] * (R - M) - (ll)(M + R) * (R - M + 1) / 2);
// }
// laz[rt] = -1;
//
// }
//
// if(col[rt] > 0){
// col[lson(rt)] = col[rt];
// col[rson(rt)] = col[rt];
// }}void build(int rt,int L,int R){sum[rt] = 0;col[rt] = 0;laz[rt] = 0;if (L == R){col[rt] = L;return ;}int M = (L + R) >> 1;build(lson(rt),L,M);build(rson(rt),M + 1,R);push_up(rt);}void update(int rt,int L,int R){
// cout << rt << " " << L << " " << R << " sum " << sum[rt] << " col " << col[rt] << " laz " << laz[rt] << endl;if (ql <= L && R <= qr && col[rt]){sum[rt] += (ll)abs(col[rt] - val) * (R - L + 1);laz[rt] += abs(col[rt] - val);col[rt] = val;return ;
// if (col[rt] > 0){
// sum[rt] += (ll)(R - L + 1) * (abs(col[rt] - val));
// }else {
// sum[rt] += abs((ll)(val)*(R - L + 1) - (ll)(L + R) * (R - L + 1) / 2);
// }
// col[rt] = val;
// laz[rt] = val;
// return ;}push_down(rt,L,R);int M = (L + R) >> 1;if (ql <= M)update(lson(rt),L,M);if (M < qr)update(rson(rt),M + 1,R);
// cout << rt << " " << L << " " << R << " sum " << sum[rt] << " col " << col[rt] << " laz " << laz[rt] << endl;push_up(rt);}ll query(int rt,int L,int R){if (ql <= L && R <= qr){return sum[rt];}push_down(rt,L,R);int M = (L + R) >> 1;ll ans = 0;if (ql <= M)ans += query(lson(rt),L,M);if (M < qr)ans += query(rson(rt),M + 1,R);return ans;}void print(int rt,int L,int R){cout << rt << " " << L << " " << R << " sum " << sum[rt] << " col " << col[rt] << " laz " << laz[rt] << endl;if (L == R){return ;}int M = (L + R) >> 1;print(lson(rt),L,M);print(rson(rt),M+1,R);}
}it;int main(){int n,m;//freopen("1.txt","r",stdin);while(scanf("%d%d",&n,&m)!=EOF){int op;int l,r;int x;//it.init();it.build(1,1,n);for (int i = 1;i <= m;i ++){// cout << i << "----------" << endl;scanf("%d%d%d",&op,&l,&r);it.setlr(l,r);if (op == 1){scanf("%d",&x);it.setv(x);it.update(1,1,n);}else {printf("%I64d\n",it.query(1,1,n));}//cout << "-------------" << endl;//it.print(1,1,n);}}return 0;
}
这篇关于Codeforces 444C DZY Loves Colors 线段树区间更新的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
