洛谷 2572 bzoj 1858 [SCOI2010]序列操作 题解

发表于 | 阅读次数：
本文字数： 2.4k 字 | 阅读时长 ≈ 11 分钟

题意简述

你有一个长度为$n$的01序列，支持$m$个操作，操作分五种，形式分别是：

  • 0 l r 从$l$到$r$都变成$0$
  • 1 l r 从$l$到$r$都变成$1$
  • 2 l r 从$l$到$r$全部取反（$0$变成$1$，$1$变成$0$）
  • 3 l r 询问$l$到$r$有多少$1$
  • 4 l r 询问$l$到$r$最长的连续的$1$有多长

思路框架

线段树多标记。

具体思路

线段树，分几个方面讲

  1. 每个节点存什么信息
  2. 如何维护这些信息（Update 函数）
  3. lazytag 的优先级，以及如何单节点修改，还有如何 PushDown。

节点信息

我们按操作顺序考虑。首先是区间覆盖的操作，那么我们就要维护一个标记，设为 $cover$ 标记（简记为 $C$）。由于 $C$ 取 $0/1$ 都是有意义的，那么就只好用 $-1$ 表示没有标记了。

然后还有取反操作。那么我们维护一个 $flip$ 标记（简记为 $F$ ），$F=0/1$ 表示区间被取反了$F$ 次。由于取反两次就相当于没有取反，所以 $F$ 只需要设置为 $0/1$ 即珂。

然后询问有多少个 $1$。显然我们需要维护区间有多少个 $1$ ，设为 $s[1]$ （$s$ 就是 $sum$ 啦）。然后我们发现，取反完之后， $0$ 变成 $1$，$1$ 变成$0$。所以$1$有的标记，$0$ 都要有。所以我们还有维护区间有多少 $0$，设为 $s[0]$。

然后询问连续的 $1$ 。这个是套路：我们维护从左边起最大连续的 $0/1$ ，设为 $lc[0/1]$（就是left consecutive的简写 ），还有从右边起最大连续的 $0/1$，设为 $rc[0/1]$。还有最长的连续 $0/1$，记为$x$。（这个名字是瞎jb取的，因为没有名字了）

如何维护

众所周知，update 的时候，lazytag 是不重要的。我们直接将其设置为空标记即珂。

显然，$s[0/1]$ 就直接左子树+右子树即珂。

$lc[0/1]$ 就先设置成左子树的 $lc$。如果发现它占满了整个左子树，那就要跨越到右子树去了。此时再加上右子树的 $lc$ 即珂。
$rc$ 同理。

然后 $x$（最长连续的 $0/1$）的维护也很容易，就是左子树连续的 $1$，右子树连续的 $1$，还有左子树的右连续（$rc$）+右子树的左连续（$lc$），三个取 $max$。

（实现小技巧：我们珂以把节点打个 $struct$，然后封装一个加号）
先放个代码上来，方便理解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct node{int l,r,f,c,lc[2],rc[2],s[2],x[2];}; 
//l,r表示当前节点表示的区间
//f,c是两个tag
//lc,rc,s,x和上面一样，表示左连续，右连续，总计数，最大连续
node operator+(node ls,node rs)
{
    node ans;
    ans.l=ls.l; ans.r=rs.r; //这个不用我讲吧...
    ans.f=0,ans.c=-1; //标记
    for(int i=0;i<2;++i)
    {
        ans.lc[i]=ls.lc[i]; if (ls.lc[i]==ls.r-ls.l+1) ans.lc[i]+=rs.lc[i];
        //默认直接取左儿子的。如果满了，再加上右儿子的左连续
        ans.rc[i]=rs.rc[i]; if (rs.rc[i]==rs.r-rs.l+1) ans.rc[i]+=ls.rc[i];
        //rc同理
        ans.s[i]=ls.s[i]+rs.s[i];
        //总计数比较方便，直接左右加起来即珂
        ans.x[i]=max(max(ls.x[i],rs.x[i]),ls.rc[i]+rs.lc[i]);
        //最长连续要分三种情况讨论
    }
    return ans;
}

lazytag的优先级&如何维护lazytag

单区间修改

  1. 覆盖操作：显然，覆盖的优先级绝对大于取反，所以先令 $F=0$。接着，假设我们都覆盖上了$c$，$c=0/1$。然后 $lc[c],rc[c],s[c],x[c]$ 都等于区间长度，而另一个颜色（$c$ 取反）的$lc,rc,s,x$ 都等于$0$。

  2. 如果是取反的操作，因为是低优先级的操作，所以直接修改 $F$ 标记即珂。由于取反完之后，$0$ 变成 $1$，$1$ 变成 $0$，所以我们只需要把 $lc,rc,s,x$的$0/1$ 两维交换一下即珂。

PushDown

PushDown 的时候，先操作 $C$ 标记，再操作 $F$ 标记。我们下传标记的时候，只对儿子作修改，而不对本身作修改（因为在 PushDown 前面一次单区间修改的时候，应该已经改过了）。所以如果遇到“先覆盖后翻转”的情况，就不会错误地把 $F$ 标记删掉了。而两个儿子也是 $C$ 标记先到，$F$ 后到，所以儿子节点的 $F$ 标记也不会被错删掉。

一个小问题：如何写最长连续1的Query函数（代码中的QueryLen）

Query 函数返回一个线段树节点即珂。最后取节点的 $x[1]$ 属性，就是最长连续 $1$ 的长度了。

完整代码（超长）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
    #define N 155555
    // #define F(i,l,r) for(int i=l;i<=r;++i)
    // 为了不和F标记重名，删掉了这个define
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)
    #define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
    #define p_b push_back
    #define sz(a) ((int)a.size())
    #define iter(a,p) (a.begin()+p)
    void R1(int &x)
    {
        x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        x=(f==1)?x:-x;
    }
    void Rd(int cnt,...)
    {
        va_list args;
        va_start(args,cnt);
        for(int i=1;i<=cnt;++i)
        {
            int* x=va_arg(args,int*);R1(*x);
        }
        va_end(args);
    } //这些都是次要内容
    //以下正片
    //==============================
    struct node{int l,r,f,c,lc[2],rc[2],s[2],x[2];}; 
    //一个线段树节点
    node operator+(node ls,node rs) //这一段上面有
    {
        node ans;
        ans.l=ls.l; ans.r=rs.r;
        ans.f=0,ans.c=-1;
        for(int i=0;i<2;++i)
        {
            ans.lc[i]=ls.lc[i]; if (ls.lc[i]==ls.r-ls.l+1) ans.lc[i]+=rs.lc[i];
            ans.rc[i]=rs.rc[i]; if (rs.rc[i]==rs.r-rs.l+1) ans.rc[i]+=ls.rc[i];
            ans.s[i]=ls.s[i]+rs.s[i];
            ans.x[i]=max(max(ls.x[i],rs.x[i]),ls.rc[i]+rs.lc[i]);
        }
        return ans;
    }
    class SegmentTree
    {
    public:
        node tree[N<<2];

        #define ls index<<1
        #define rs index<<1|1

        #define LC tree[index].lc
        #define RC tree[index].rc
        #define S  tree[index].s
        #define X  tree[index].x
        #define L  tree[index].l
        #define R  tree[index].r
        #define C  tree[index].c
        #define F  tree[index].f

        #define lLC tree[ls].lc
        #define lRC tree[ls].rc
        #define lS  tree[ls].s
        #define lX  tree[ls].x
        #define lL  tree[ls].l
        #define lR  tree[ls].r
        #define lC  tree[ls].c
        #define lF  tree[ls].f

        #define rLC tree[rs].lc
        #define rRC tree[rs].rc
        #define rS  tree[rs].s
        #define rX  tree[rs].x
        #define rL  tree[rs].l
        #define rR  tree[rs].r
        #define rC  tree[rs].c
        #define rF  tree[rs].f //中二define，让代码简介一点
        void Update(int index=1) //这个似乎就很好写了对吧
        {
            tree[index]=tree[ls]+tree[rs];
        }
        void Build(int l,int r,int index=1)
        {
            L=l,R=r;
            if (l==r)
            {
                int x; scanf("%d",&x);
                C=-1;F=0; // 注意: C的空标记为-1
                S[x]=LC[x]=RC[x]=X[x]=1;
                x^=1;
                S[x]=LC[x]=RC[x]=X[x]=0;
                return;
            }
            int mid=(l+r)>>1;
            Build(l,mid,ls); Build(mid+1,r,rs);
            Update(index);
        }
        void FlipOne(int index=1)
        {
            F^=1;
            //注意: F^=1即珂
            swap(LC[0],LC[1]); 
            swap(RC[0],RC[1]); 
            swap(S[0],S[1]); 
            swap(X[0],X[1]);
            //把0和1对应的属性换一下
        } 
        void ChangeOne(int x,int index=1)
        {
            F=0; //清空F标记
            C=x; 
            S[x]=LC[x]=RC[x]=X[x]=R-L+1; //x的属性全部设置为区间长度,x^1的属性全部为0
            x^=1;
            S[x]=LC[x]=RC[x]=X[x]=0;
        }
        //封装单区间修改函数，代码看起来结构清晰些(?)
        void PushDown(int index=1)
        {
            //先传C标记，再传F标记
            if (~C)
            {
                ChangeOne(C,ls); ChangeOne(C,rs);
                C=-1;
            }
            if (F)
            {
                FlipOne(ls); FlipOne(rs);
                F=0;
            }
        }
        void Change(int l,int r,int x,int index=1) //覆盖[l,r]为x
        {
            if (l>R or L>r) return;
            if (l<=L and R<=r) return ChangeOne(x,index);
            PushDown(index);
            Change(l,r,x,ls); Change(l,r,x,rs);
            Update(index);
        }
        void Flip(int l,int r,int index=1) //区间[l,r]翻转
        {
            if (l>R or L>r) return;
            if (l<=L and R<=r) return FlipOne(index);
            PushDown(index);
            Flip(l,r,ls); Flip(l,r,rs);
            Update(index);
        }
        int Query1(int l,int r,int index=1) //询问[l,r]中1的数量
        {
            if (l>R or L>r) return 0;
            if (l<=L and R<=r) return S[1];
            PushDown(index);
            return Query1(l,r,ls)+Query1(l,r,rs);
        }
        node QueryLen(int l,int r,int index=1) //询问[l,r]中连续1的长度
        {
            if (l<=L and R<=r) return tree[index]; //返回一个线段树节点
            PushDown(index);
            int mid=(L+R)>>1;
            if (r<=mid) return QueryLen(l,r,ls);
            if (l>mid)  return QueryLen(l,r,rs);
            return QueryLen(l,mid,ls)+QueryLen(mid+1,r,rs); //这样用节点合并就珂以了，是不是很简单呢
        }
    }T;

    int n,m;
    void Input()
    {
        Rd(2,&n,&m);
        T.Build(1,n);
    }

    void Soviet()
    {
        for(int i=1;i<=m;++i)
        {
            int o,l,r;Rd(3,&o,&l,&r);
            ++l,++r; //0编号转1编号
            if (o==0) T.Change(l,r,0);
            if (o==1) T.Change(l,r,1);
            if (o==2) T.Flip(l,r);
            if (o==3) printf("%d\n",T.Query1(l,r));
            if (o==4) printf("%d\n",T.QueryLen(l,r).x[1]); //取x[1]属性就是答案啦
        }
    }

    #define Flan void
    Flan IsMyWife()
    {
        Input();
        Soviet();
    }
}
int main()
{
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}
w