首页 > 代码库 > CodeForces 444C 分块
CodeForces 444C 分块
题目链接：http://codeforces.com/problemset/problem/444/C
题意：给定一个长度为n的序列a[]。起初a[i]=i,然后还有一个色度的序列b[],起初b[i]=0。现在有2种操作：
1 l r x:区间染色，a[l],a[l+1]...a[r]变成x.同时b[l],b[l+1]...b[r]加上对应的|x-a[i]|值。
2 l r:统计区间和，统计区间b[l],b[l+1]...b[r]的和。
思路：线段树是比较常见的做法。考虑分块。每块维护一个lazy表示是否整块颜色都相同，Bsum表示块的b[i]总和.lazyb表示块的b[i]累加值的和。然后暴力维护即可。
#define _CRT_SECURE_NO_DEPRECATE#include<stdio.h> #include<string.h> #include<cstring>#include<algorithm> #include<queue> #include<math.h> #include<time.h>#include<vector>#include<iostream>#include<map>using namespace std;typedef long long int LL;const int MAXN = 100000 + 10;int belong[MAXN], block, num, L[MAXN], R[MAXN];int n, q;LL a[MAXN],b[MAXN];struct Node{ LL lazy, Bsum,lazyb;}Bval[400];void build(){ block = (int)sqrt(n + 0.5); num = n / block; if (n%block){ num++; } for (int i = 1; i <= num; i++){ Bval[i].Bsum = 0; Bval[i].lazy = 0; Bval[i].lazyb=0; L[i] = (i - 1)*block + 1; R[i] = i*block; } R[num] = n; for (int i = 1; i <= n; i++){ belong[i] = ((i - 1) / block) + 1; }}void modify(int st, int ed,int val){ if (belong[st] == belong[ed]){ if(Bval[belong[st]].lazy){ for(int i=L[belong[st]];i<=R[belong[st]];i++){ a[i]=Bval[belong[st]].lazy; } Bval[belong[st]].lazy=0; } for(int i=st;i<=ed;i++){ Bval[belong[st]].Bsum+=abs(a[i]-val); b[i]+=abs(a[i]-val); a[i]=val; } return; } if(Bval[belong[st]].lazy){ for(int i=L[belong[st]];i<=R[belong[st]];i++){ a[i]=Bval[belong[st]].lazy; } Bval[belong[st]].lazy=0; } for (int i = st; i <= R[belong[st]]; i++){ Bval[belong[st]].Bsum+=abs(val-a[i]); b[i]+=abs(val-a[i]); a[i]=val; } for (int i = belong[st] + 1; i < belong[ed]; i++){ if(Bval[i].lazy){ Bval[i].lazyb+=abs(val-Bval[i].lazy); Bval[i].Bsum+=(1LL*abs(Bval[i].lazy-val)*(R[i]-L[i]+1)); Bval[i].lazy=val; } else{ for(int j=L[i];j<=R[i];j++){ b[j]+=abs(a[j]-val); Bval[i].Bsum+=abs(a[j]-val); a[j]=val; } Bval[i].lazy=val; } } if(Bval[belong[ed]].lazy){ for(int i=L[belong[ed]];i<=R[belong[ed]];i++){ a[i]=Bval[belong[ed]].lazy; } Bval[belong[ed]].lazy=0; } for (int i = L[belong[ed]]; i <= ed; i++){ Bval[belong[ed]].Bsum+=abs(val-a[i]); b[i]+=abs(val-a[i]); a[i]=val; }}LL query(int st, int ed){ LL ans = 0; if (belong[st] == belong[ed]){ for (int i = st; i <= ed; i++){ ans += (b[i]+Bval[belong[st]].lazyb); } return ans; } for (int i = st; i <= R[belong[st]]; i++){ ans += (b[i]+Bval[belong[st]].lazyb); } for (int i = belong[st] + 1; i < belong[ed]; i++){ ans += Bval[i].Bsum; } for (int i = L[belong[ed]]; i <= ed; i++){ ans += (b[i]+Bval[belong[ed]].lazyb); } return ans;}int main(){//#ifdef kirito// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);//#endif// int start = clock(); while (~scanf("%d%d", &n,&q)){ for (int i = 1; i <= n; i++){ a[i]=i; b[i]=0;} build(); int type, l, r, v; for (int i = 1; i <= q; i++){ scanf("%d", &type); if (type == 1){ scanf("%d%d%d", &l, &r,&v); modify(l, r,v); } else{ scanf("%d%d", &l, &r); printf("%lld\n", query(l, r)); } } }//#ifdef LOCAL_TIME// cout << "[Finished in " << clock() - start << " ms]" << endl;//#endif return 0;}
CodeForces 444C 分块
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。