随笔 - 97, 文章 - 22, 评论 - 81, 引用 - 0
数据加载中……

HDU 3397 Sequence operation

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3397

/*
题意:
    给出一个长度为N(N <= 100000)的数列,然后是五种操作:
插入操作:
0 a b 将所有[a, b]区间内的数改成0
1 a b 将所有[a, b]区间内的数改成1
2 a b 将所有[a, b]区间内的数异或一下(0边1,1变0)
输出操作:
3 a b 输出[a, b]区间内1的数量
4 a b 输出[a, b]区间内最长的连续1串


解法:
线段树

思路:
    这题看起来是一般的区间覆盖问题,还是有一点小trick让我卡了很久,先
来看看线段树的结点要求保存的信息:

    enum eLazyTag {
        ZERO     = 0,
        ONE      = 1,
        XOR      = 2,
        TAG_MAX  = 3
    }; // lazy标记的枚举类型

    char lazy[TAG_MAX];      // 对应的lazy标记
    int root, l, r;          // 当前结点管理的左右区间以及编号
    int lMax[2];             // 包含当前结点管理区间左端点的最长连续相同数字串
    int rMax[2];             // 包含当前结点管理区间右端点的最长连续相同数字串
    int Max[2];              // 当前结点管理区间的最长连续相同数字串
    int Sum;                 // 记录当前区间的和,也就是1的数量

这题的异或操作是亮点,因为它不是单纯的覆盖,而是和先前的线段状态取反,这个操作
和直接覆盖不一样,需要知道以前这块线段的信息,所以如果之前这个线段的lazy标记是
ZERO,传入的变量要求做XOR,那么不能仅仅将XOR赋值给lazy,这样当前结点的左右子树
就不能享受到ZERO带来的“福利”。所以我们保存三个lazy标记(其实只需要两个就够了
,因为0和1的情况是一样,都是普通的覆盖,不涉及到先前值),每次传递标记的时候需
要三个标记都传递下去。

我们用以下函数从左右儿子中得到当前结点的信息:
void UpdateBy(Tree* ls, Tree* rs);
之所以把它写成函数是因为这里的处理比较麻烦,很容易出错,并且需要
调用多次,这个函数的作用就是通过左右儿子的信息填充本身的信息。

这里沿用LCIS那题的思想,保存lMax,rMax,但是需要注意这里有一种异或操作,所以
光保存连续1串的最大长度是不够的,异或之后1就变成了0,于是保存两种值,0和1的分
别最大长度,这样如果有XOR操作,直接将lMax[0]和lMax[1]交换即可,其它两个值亦然。


讲一下我的代码的结构吧。首先是建树,通过Build函数建立完全二叉树,进入函数时将
一些必要的值初始化,当遇到叶子结点时处理那个结点的信息,如果不是叶子结点,则递
归建立二个儿子的信息,然后通过儿子的信息,将父亲结点的所有值算出来,这个计算过
程是通过void UpdateBy(Tree* ls, Tree* rs)来完成的,ls和rs分别表示当前结点的两个
儿子的结点指针,UpdateBy计算的信息包括区间和Sum,区间最长连续0串和1串。对操作分
情况讨论:

插入操作:
    如果当前区间已经完全包含了结点区间,则调用CoverBy函数将插入标记传给当前
结点的lazy,具体的CoverBy函数的实现需要分情况讨论:
    当传入的插入类型mode为ZERO或者ONE则表明是直接覆盖,那么当前lazy[mode]标
记赋值为1,以便下次传递给子孙,而lazy[1-mode]和lazy[XOR]直接置零即可。因为只需
直接覆盖,先前的标记就不起作用了。
    当插入的类型为XOR时,并且之前有ONE或者ZERO标记,说明当前区间肯定全是相同
的数,因为lazy标记存在,说明还没有传递给子孙,则将lazy[ONE]和lazy[ZERO]的值交换
即可(因为当前插入类型为XOR)。如果之前没有标记或者只有XOR标记,直接将lazy[XOR]
和1异或即可。

插入完毕然后更新当前区间的结点值。如果当前区间没有完全包含结点区间,则先将当前
结点的lazy标记传递给左右儿子,然后分别递归左右儿子进行插入操作,插入完毕后,通
过左右儿子得到的结点值利用void UpdateBy(Tree* ls, Tree* rs)更新父亲结点。

询问操作:
完全覆盖时直接返回当前结点,否则需要递归左右儿子将两个结点合并。

*/




#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];  // 对应的lazy标记是否存在以及它的奇偶性
    int root, l, r;      // 当前结点管理的左右区间以及编号
    int lMax[2];         // 包含当前结点管理区间左端点的最长连续相同数字串
    int rMax[2];         // 包含当前结点管理区间右端点的最长连续相同数字串
    int Max[2];          // 当前结点管理区间的最长连续相同数字串
    int Sum;             // 记录当前区间的和,也就是1的数量

    
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(
11, 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;
}

posted on 2011-04-02 12:55 英雄哪里出来 阅读(1824) 评论(0)  编辑 收藏 引用 所属分类: 线段树


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理