|
|
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1698
  /**//*
 题意：
给定一个长度为N(N <= 100000)的数列Si，紧接着Q(1 <= Q <= 100000)条操作
，每条操作将[A, B]的区间颜色改成C（权值为C），颜色C最多三种，问最后所有数
的权值总和。
解法：
线段树
思路：
线段树的区间修改，还是利用lazy思想。线段树结点维护一个Color域和一个
Count域，Color要么是-1表示当前结点有多种颜色，要么是颜色的编号，每次插入
到完全覆盖时在该结点的Color域上打上一个标记，表示当前颜色，计算当前结点的
Count值。如果当前结点的颜色和插入的颜色相同，说明不必再往下插入了。如果没
有完全覆盖，并且当前结点的颜色单一，那么直接将父亲的值传递给而两个儿子，
还是同样的道理，之前的儿子如果有lazy标记，肯定是在当前标记之前，所以直接覆
盖即可。最后通过两个儿子的权值计算当前子树的权值。
 */
#include <iostream>
using namespace std;
#define maxn 100010
#define MULTIPLE_COLOR -1
struct Tree  {
int nColor, nCount;
int son[2];
int l, r;
  void clear() {
son[0] = son[1] = -1;
nColor = 1;
nCount = r - l + 1;
 }
int len() {
return r - l + 1;
}
void TranslateToSon();
void UpdateBy(Tree* ls, Tree* rs);
}T[ maxn*4 ];
int tot;
int GetID(int& root, int l, int r) {
if(root == -1) {
root = tot++;
T[root].l = l;
T[root].r = r;
T[root].clear();
}
return root;
}
void Tree::TranslateToSon() {
if(nColor != MULTIPLE_COLOR) {
int mid = (l + r) >> 1;
int i0 = GetID(son[0], l, mid);
T[i0].nColor = nColor;
T[i0].nCount = nColor * T[i0].len();
int i1 = GetID(son[1], mid+1, r);
T[i1].nColor = nColor;
T[i1].nCount = nColor * T[i1].len();
nColor = MULTIPLE_COLOR;
}
}
void Tree::UpdateBy(Tree* ls, Tree* rs){
if(ls->nColor == rs->nColor) {
nColor = ls->nColor;
}else {
nColor = MULTIPLE_COLOR;
}
nCount = ls->nCount + rs->nCount;
}
void Insert(int& root, int nl, int nr, int l, int r, int val) {
if(l > nr || r < nl)
return ;
GetID(root, l, r);
if(T[root].nColor == val)
return ;
if(nl <= l && r <= nr) {
T[root].nColor = val;
T[root].nCount = val * (r - l + 1);
return ;
}
T[root].TranslateToSon();
int mid = (l + r) >> 1;
Insert(T[root].son[0], nl, nr, l, mid, val);
Insert(T[root].son[1], nl, nr, mid+1, r, val);
T[root].UpdateBy(&T[ T[root].son[0] ], &T[ T[root].son[1] ]);
}
int n, m;
int main() {
int t;
int Case = 1;
scanf("%d", &t);
while(t--) {
int root = -1;
tot = 0;
scanf("%d %d", &n, &m);
Insert(root, 1, n, 1, n, 1);
while(m--) {
int x, y, z;
scanf("%d %d %d", &x, &y, &z);
Insert(root, x, y, 1, n, z);
}
printf("Case %d: The total value of the hook is %d.\n", Case++, T[root].nCount);
}
return 0;
}
|