|
|
題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=1698
  /**//*
 題意：
給定一個(gè)長(zhǎng)度為N(N <= 100000)的數(shù)列Si，緊接著Q(1 <= Q <= 100000)條操作
，每條操作將[A, B]的區(qū)間顏色改成C（權(quán)值為C），顏色C最多三種，問(wèn)最后所有數(shù)
的權(quán)值總和。
解法：
線段樹(shù)
思路：
線段樹(shù)的區(qū)間修改，還是利用lazy思想。線段樹(shù)結(jié)點(diǎn)維護(hù)一個(gè)Color域和一個(gè)
Count域，Color要么是-1表示當(dāng)前結(jié)點(diǎn)有多種顏色，要么是顏色的編號(hào)，每次插入
到完全覆蓋時(shí)在該結(jié)點(diǎn)的Color域上打上一個(gè)標(biāo)記，表示當(dāng)前顏色，計(jì)算當(dāng)前結(jié)點(diǎn)的
Count值。如果當(dāng)前結(jié)點(diǎn)的顏色和插入的顏色相同，說(shuō)明不必再往下插入了。如果沒(méi)
有完全覆蓋，并且當(dāng)前結(jié)點(diǎn)的顏色單一，那么直接將父親的值傳遞給而兩個(gè)兒子，
還是同樣的道理，之前的兒子如果有l(wèi)azy標(biāo)記，肯定是在當(dāng)前標(biāo)記之前，所以直接覆
蓋即可。最后通過(guò)兩個(gè)兒子的權(quán)值計(jì)算當(dāng)前子樹(shù)的權(quán)值。
 */
#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;
}
|