hdu-3397 Sequence operation 线段树多种标记

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=3397

题目大意：

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的长度

解题思路：

线段树多种标记。

需要处理的东西比较多：

做题的时候发现一个问题：

我的宏定义Max不可以用于函数，尤其是递归函数，这样会使得同一函数重复调用好几遍，递归函数的话更会超时。

 #include<bits/stdc++.h>

 #define IOS ios::sync_with_stdio(false);//不可再使用scanf printf

 #define Max(a, b) ((a) > (b) ? (a) : (b))//禁用于函数，会超时

 #define Min(a, b) ((a) < (b) ? (a) : (b))

 #define Mem(a) memset(a, 0, sizeof(a))

 #define Dis(x, y, x1, y1) ((x - x1) * (x - x1) + (y - y1) * (y - y1))

 #define MID(l, r) ((l) + ((r) - (l)) / 2)

 #define lson ((o)<<1)

 #define rson ((o)<<1|1)

 #pragma comment(linker, "/STACK:102400000,102400000")//栈外挂

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}

     while (ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 typedef long long ll;

 const int maxn =  + ;

 const int MOD = ;//const引用更快，宏定义也更快

 struct node

 {

     int l, r;//左右区间

     int ls0, rs0, ms0;//左连续的0，右连续的0，区间最大连续的0

     int ls1, rs1, ms1;//左连续的1，右连续的1，区间最大连续的1

     int sum0, sum1;//区间0 1数目

     int lazy, Xor;//懒惰标记和异或标记

 }tree[maxn << ];

 int a[maxn];

 void pushup(int o)

 {

     if(tree[o].l == tree[o].r)return;//叶子节点直接返回

     //根据子节点的信息，更新父节点信息

     //更新0：

     int lc = lson, rc = rson;

     tree[o].ls0 = tree[lc].ls0;

     tree[o].rs0 = tree[rc].rs0;

     if(tree[lc].ls0 == tree[lc].r - tree[lc].l + )

         tree[o].ls0 += tree[rc].ls0;//左节点左连续的0为区间长度 那么根节点左连续的0需要再加上右节点左连续的0

     if(tree[rc].rs0 == tree[rc].r - tree[rc].l + )

         tree[o].rs0 += tree[lc].rs0;

     tree[o].ms0 = Max(Max(tree[lc].ms0, tree[rc].ms0), tree[lc].rs0 + tree[rc].ls0);//最大连续0 = Max(左节点最大连续0， 右节点最大连续0，中间最大连续0)

     tree[o].sum0 = tree[lc].sum0 + tree[rc].sum0;

     //更新1

     tree[o].ls1 = tree[lc].ls1;

     tree[o].rs1 = tree[rc].rs1;

     if(tree[lc].ls1 == tree[lc].r - tree[lc].l + )

         tree[o].ls1 += tree[rc].ls1;//左节点左连续的0为区间长度 那么根节点左连续的0需要再加上右节点左连续的0

     if(tree[rc].rs1 == tree[rc].r - tree[rc].l + )

         tree[o].rs1 += tree[lc].rs1;

     tree[o].ms1 = Max(Max(tree[lc].ms1, tree[rc].ms1), tree[lc].rs1 + tree[rc].ls1);//最大连续0 = Max(左节点最大连续0， 右节点最大连续0，中间最大连续0)

     tree[o].sum1 = tree[lc].sum1 + tree[rc].sum1;

 }

 void XOR(int o)

 {

     swap(tree[o].ls0, tree[o].ls1);

     swap(tree[o].rs0, tree[o].rs1);

     swap(tree[o].ms0, tree[o].ms1);

     swap(tree[o].sum0, tree[o].sum1);

 }

 void pushdown(int o)//标记下传

 {

     if(tree[o].l == tree[o].r)return;

     if(tree[o].lazy != -)//区间覆盖0或者1

     {

         int lc = lson, rc = rson, len = tree[o].r - tree[o].l + ;

         tree[lc].lazy = tree[rc].lazy = tree[o].lazy;

         tree[lc].Xor = tree[rc].Xor = ;

         //左节点长度为(len+1) / 2 右节点长度为len/2

         //左

         tree[lc].ls0 = tree[lc].rs0 = tree[lc].ms0 = tree[o].lazy ?  : (len + ) / ;

         tree[lc].ls1 = tree[lc].rs1 = tree[lc].ms1 = tree[o].lazy ? (len + ) /  : ;

         tree[lc].sum0 = tree[o].lazy ?  : (len + ) / ;

         tree[lc].sum1 = tree[o].lazy ? (len + ) /  : ;

         //右

         tree[rc].ls0 = tree[rc].rs0 = tree[rc].ms0 = tree[o].lazy ?  : (len) / ;

         tree[rc].ls1 = tree[rc].rs1 = tree[rc].ms1 = tree[o].lazy ? (len) /  : ;

         tree[rc].sum0 = tree[o].lazy ?  : (len) / ;

         tree[rc].sum1 = tree[o].lazy ? (len) /  : ;

         tree[o].lazy = -;//清除标记

     }

     if(tree[o].Xor)

     {

         tree[o].Xor = ;

         tree[lson].Xor ^= ;

         tree[rson].Xor ^= ;

         XOR(lson), XOR(rson);

     }

 }

 void build(int o, int l, int r)

 {

     tree[o].l = l, tree[o].r = r, tree[o].lazy = -, tree[o].Xor = ;

     if(l == r)

     {

         tree[o].ls0 = tree[o].rs0 = tree[o].ms0 = (a[l] == );

         tree[o].ls1 = tree[o].rs1 = tree[o].ms1 = (a[l] == );

         tree[o].sum1 = (a[l] == );

         tree[o].sum0 = (a[l] == );

         return;

     }

     int m = MID(l, r);

     build(lson, l, m);

     build(rson, m + , r);

     pushup(o);

 }

 int flag;//标记类型

 int ql, qr;

 void update(int o)

 {

     pushdown(o);

     if(ql <= tree[o].l && qr >= tree[o].r)

     {

         if(flag == )

         {

             tree[o].Xor = ;

             XOR(o);

         }

         else

         {

             int len = tree[o].r - tree[o].l + ;

             tree[o].lazy = flag;

             tree[o].ls0 = tree[o].rs0 = tree[o].ms0 = flag ?  : len;

             tree[o].ls1 = tree[o].rs1 = tree[o].ms1 = flag ? len : ;

             tree[o].sum0 = flag ?  : len;

             tree[o].sum1 = flag ? len : ;

         }

     }

     else

     {

         int m = MID(tree[o].l, tree[o].r);

         if(ql <= m)update(lson);

         if(qr > m)update(rson);

         pushup(o);

     }

 }

 int query(int o)

 {

     pushdown(o);

     if(ql <= tree[o].l && qr >= tree[o].r)

     {

         if(flag == )return tree[o].sum1;

         else return tree[o].ms1;

     }

     else

     {

         if(qr <= tree[lson].r)return query(lson);

         if(ql >= tree[rson].l)return query(rson);

         if(flag == )return query(lson) + query(rson);

         int ans1 = Min(tree[lson].rs1, tree[lson].r - ql + ) + Min(tree[rson].ls1, qr - tree[rson].l + );

         int ans2 = max(query(lson), query(rson));//用宏定义会超时，因为一直在递归

         return Max(ans1, ans2);

     }

 }

 int main()

 {

     int T;

     scanf("%d", &T);

     while(T--)

     {

         int n, m;

         scanf("%d%d", &n, &m);

         for(int i = ; i <= n; i++)scanf("%d", &a[i]);

         build(, , n);

         while(m--)

         {

             scanf("%d%d%d", &flag, &ql, &qr);

             ql++, qr++;

             if(flag < )update();

             else printf("%d\n", query());

         }

     }

     return ;

 }