|
|
題目鏈接：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;
}
|