|
|
題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=3397
  /**//*
 題意：
給出一個長度為N(N <= 100000)的數(shù)列，然后是五種操作：
插入操作:
0 a b 將所有[a, b]區(qū)間內(nèi)的數(shù)改成0
1 a b 將所有[a, b]區(qū)間內(nèi)的數(shù)改成1
2 a b 將所有[a, b]區(qū)間內(nèi)的數(shù)異或一下（0邊1,1變0）
輸出操作:
3 a b 輸出[a, b]區(qū)間內(nèi)1的數(shù)量
4 a b 輸出[a, b]區(qū)間內(nèi)最長的連續(xù)1串
解法：
線段樹
思路：
這題看起來是一般的區(qū)間覆蓋問題，還是有一點(diǎn)小trick讓我卡了很久，先
來看看線段樹的結(jié)點(diǎn)要求保存的信息：
enum eLazyTag {
ZERO = 0,
ONE = 1,
XOR = 2,
TAG_MAX = 3
}; // lazy標(biāo)記的枚舉類型
char lazy[TAG_MAX]; // 對應(yīng)的lazy標(biāo)記
int root, l, r; // 當(dāng)前結(jié)點(diǎn)管理的左右區(qū)間以及編號
int lMax[2]; // 包含當(dāng)前結(jié)點(diǎn)管理區(qū)間左端點(diǎn)的最長連續(xù)相同數(shù)字串
int rMax[2]; // 包含當(dāng)前結(jié)點(diǎn)管理區(qū)間右端點(diǎn)的最長連續(xù)相同數(shù)字串
int Max[2]; // 當(dāng)前結(jié)點(diǎn)管理區(qū)間的最長連續(xù)相同數(shù)字串
int Sum; // 記錄當(dāng)前區(qū)間的和，也就是1的數(shù)量
這題的異或操作是亮點(diǎn)，因為它不是單純的覆蓋，而是和先前的線段狀態(tài)取反，這個操作
和直接覆蓋不一樣，需要知道以前這塊線段的信息，所以如果之前這個線段的lazy標(biāo)記是
ZERO，傳入的變量要求做XOR，那么不能僅僅將XOR賦值給lazy，這樣當(dāng)前結(jié)點(diǎn)的左右子樹
就不能享受到ZERO帶來的“福利”。所以我們保存三個lazy標(biāo)記（其實只需要兩個就夠了
，因為0和1的情況是一樣，都是普通的覆蓋，不涉及到先前值），每次傳遞標(biāo)記的時候需
要三個標(biāo)記都傳遞下去。
我們用以下函數(shù)從左右兒子中得到當(dāng)前結(jié)點(diǎn)的信息：
void UpdateBy(Tree* ls, Tree* rs);
之所以把它寫成函數(shù)是因為這里的處理比較麻煩，很容易出錯，并且需要
調(diào)用多次，這個函數(shù)的作用就是通過左右兒子的信息填充本身的信息。
這里沿用LCIS那題的思想，保存lMax，rMax，但是需要注意這里有一種異或操作，所以
光保存連續(xù)1串的最大長度是不夠的，異或之后1就變成了0，于是保存兩種值，0和1的分
別最大長度，這樣如果有XOR操作，直接將lMax[0]和lMax[1]交換即可，其它兩個值亦然。
講一下我的代碼的結(jié)構(gòu)吧。首先是建樹，通過Build函數(shù)建立完全二叉樹，進(jìn)入函數(shù)時將
一些必要的值初始化，當(dāng)遇到葉子結(jié)點(diǎn)時處理那個結(jié)點(diǎn)的信息，如果不是葉子結(jié)點(diǎn)，則遞
歸建立二個兒子的信息，然后通過兒子的信息，將父親結(jié)點(diǎn)的所有值算出來，這個計算過
程是通過void UpdateBy(Tree* ls, Tree* rs)來完成的，ls和rs分別表示當(dāng)前結(jié)點(diǎn)的兩個
兒子的結(jié)點(diǎn)指針，UpdateBy計算的信息包括區(qū)間和Sum，區(qū)間最長連續(xù)0串和1串。對操作分
情況討論：
插入操作：
如果當(dāng)前區(qū)間已經(jīng)完全包含了結(jié)點(diǎn)區(qū)間，則調(diào)用CoverBy函數(shù)將插入標(biāo)記傳給當(dāng)前
結(jié)點(diǎn)的lazy，具體的CoverBy函數(shù)的實現(xiàn)需要分情況討論：
當(dāng)傳入的插入類型mode為ZERO或者ONE則表明是直接覆蓋，那么當(dāng)前l(fā)azy[mode]標(biāo)
記賦值為1，以便下次傳遞給子孫，而lazy[1-mode]和lazy[XOR]直接置零即可。因為只需
直接覆蓋，先前的標(biāo)記就不起作用了。
當(dāng)插入的類型為XOR時，并且之前有ONE或者ZERO標(biāo)記，說明當(dāng)前區(qū)間肯定全是相同
的數(shù)，因為lazy標(biāo)記存在，說明還沒有傳遞給子孫，則將lazy[ONE]和lazy[ZERO]的值交換
即可（因為當(dāng)前插入類型為XOR）。如果之前沒有標(biāo)記或者只有XOR標(biāo)記，直接將lazy[XOR]
和1異或即可。
插入完畢然后更新當(dāng)前區(qū)間的結(jié)點(diǎn)值。如果當(dāng)前區(qū)間沒有完全包含結(jié)點(diǎn)區(qū)間，則先將當(dāng)前
結(jié)點(diǎn)的lazy標(biāo)記傳遞給左右兒子，然后分別遞歸左右兒子進(jìn)行插入操作，插入完畢后，通
過左右兒子得到的結(jié)點(diǎn)值利用void UpdateBy(Tree* ls, Tree* rs)更新父親結(jié)點(diǎn)。
詢問操作：
完全覆蓋時直接返回當(dāng)前結(jié)點(diǎn)，否則需要遞歸左右兒子將兩個結(jié)點(diǎn)合并。
 */
#include <iostream>
using namespace std;
enum eLazyTag  {
ZERO = 0,
ONE = 1,
XOR = 2,
TAG_MAX = 3
};
#define maxn 100010
int MMax(int a, int b) {
return a > b ? a : b;
}
int MMax(int a, int b, int c, int d) {
return MMax( MMax(a, b), MMax(c, d) );
}
struct Tree {
char lazy[TAG_MAX]; // 對應(yīng)的lazy標(biāo)記是否存在以及它的奇偶性
int root, l, r; // 當(dāng)前結(jié)點(diǎn)管理的左右區(qū)間以及編號
int lMax[2]; // 包含當(dāng)前結(jié)點(diǎn)管理區(qū)間左端點(diǎn)的最長連續(xù)相同數(shù)字串
int rMax[2]; // 包含當(dāng)前結(jié)點(diǎn)管理區(qū)間右端點(diǎn)的最長連續(xù)相同數(shù)字串
int Max[2]; // 當(dāng)前結(jié)點(diǎn)管理區(qū)間的最長連續(xù)相同數(shù)字串
int Sum; // 記錄當(dāng)前區(qū)間的和，也就是1的數(shù)量
void ProcessUnit(int val);
void UpdateBy(Tree* ls, Tree* rs);
void CoverBy(int mode);
void TranslateToSon();
void TranslateTo(Tree* ts);
  int len() {
return r - l + 1;
 }
}T[maxn*4];
int val[maxn];
void Tree::ProcessUnit(int val) {
lMax[val] = rMax[val] = Max[val] = len();
lMax[val^1] = rMax[val^1] = Max[val^1] = 0;
Sum = val * len();
}
void Tree::UpdateBy(Tree* ls, Tree* rs) {
Sum = ls->Sum + rs->Sum;
l = ls->l;
r = rs->r;
int i;
for(i = 0; i < 2; i++) {
lMax[i] = (ls->lMax[i]==ls->len()) ? ls->len() + rs->lMax[i] : ls->lMax[i];
rMax[i] = (rs->rMax[i]==rs->len()) ? rs->len() + ls->rMax[i] : rs->rMax[i];
Max[i] = MMax(ls->Max[i], rs->Max[i]);
Max[i] = MMax(Max[i], lMax[i], rMax[i], ls->rMax[i]+rs->lMax[i]);
}
}
void Tree::CoverBy(int mode) {
if(mode == ZERO || mode == ONE) {
ProcessUnit(mode);
lazy[mode] = 1;
lazy[mode^1] = 0;
lazy[XOR] = 0;
}else if(mode == XOR){
swap(lMax[0], lMax[1]);
swap(rMax[0], rMax[1]);
swap( Max[0], Max[1]);
Sum = len() - Sum;
if(lazy[ZERO]) {
lazy[ONE] = 1;
lazy[ZERO] = 0;
}else if(lazy[ONE]) {
lazy[ONE] = 0;
lazy[ZERO] = 1;
}else
lazy[mode] ^= 1;
}
}
void Tree::TranslateTo(Tree* ts) {
int i;
for(i = 0; i < TAG_MAX; i++) {
if(lazy[i]) {
ts->CoverBy(i);
}
}
}
void Tree::TranslateToSon() {
TranslateTo(&T[root<<1]);
TranslateTo(&T[root<<1|1]);
for(int i = 0; i < TAG_MAX; i++)
lazy[i] = 0;
}
void Build(int p, int l, int r) {
int i;
for(i = 0; i < TAG_MAX; i++)
T[p].lazy[i] = 0;
T[p].l = l; T[p].r = r;
T[p].root = p;
if(l == r) {
T[p].ProcessUnit(val[l]);
return ;
}
int mid = (l + r) >> 1;
Build(p<<1, l, mid);
Build(p<<1|1, mid+1, r);
T[p].UpdateBy(&T[p<<1], &T[p<<1|1]);
}
void Insert(int root, int l, int r, int mode) {
if(l <= T[root].l && T[root].r <= r) {
T[root].CoverBy(mode);
return ;
}
if(mode != XOR && T[root].lazy[mode]) {
return ;
}
T[root].TranslateToSon();
int mid = T[root<<1].r;
if(r <= mid) {
Insert(root<<1, l, r, mode);
}else if(mid + 1 <= l) {
Insert(root<<1|1, l, r, mode);
}else {
Insert(root<<1, l, r, mode);
Insert(root<<1|1, l, r, mode);
}
T[root].UpdateBy(&T[root<<1], &T[root<<1|1]);
}
Tree Query(int root, int l, int r) {
if(l <= T[root].l && T[root].r <= r) {
return T[root];
}
T[root].TranslateToSon();
int mid = T[root<<1].r;
if(r <= mid) {
return Query(root<<1, l, r);
}else if(l >= mid + 1) {
return Query(root<<1|1, l, r);
}else {
Tree A = Query(root<<1, l, r);
Tree B = Query(root<<1|1, l, r);
Tree X;
X.UpdateBy(&A, &B);
return X;
}
}
int n, m;
int main() {
int t;
int i;
int p, a, b;
scanf("%d", &t);
while(t--) {
scanf("%d %d", &n, &m);
for(i = 1; i <= n; i++) {
scanf("%d", &val[i]);
}
Build(1, 1, n);
while(m--) {
scanf("%d %d %d", &p, &a, &b);
a++; b++;
if(p <= 2) {
Insert(1, a, b, p);
}else {
Tree X = Query(1, a, b);
if(p == 3) {
printf("%d\n", X.Sum);
}else
printf("%d\n", X.Max[1]);
}
}
}
return 0;
}
|