(luogu2572)序列操作[SCOI2010]

发表于 | 分类于 ， ，

原题链接

思路:

其实就是个比较复杂的线段树模板.

首先由于取反操作的存在, 所以需要同时存储有关0和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
#include <cstdio>
typedef long long LL;
const int Mn(100500);
inline int m_max(int x,int y) {
    return x>y ? x : y;
}
inline void m_swap(int& x,int& y) {
    int c = x; x = y; y = c;
}

int a[Mn];
struct Sgn {    //结点结构体
    int sum[2],mxlen[2];    //0/1个数, 最大连续长
    int llen[2],rlen[2];    //左长度, 右长度
    bool lzt,lza,lzi;   //抹平标记, 抹平结果, 取反标记
}t[Mn*4];
void upd(int l,int r,int p) {   //向上更新
    Sgn &np(t[p]),&ls(t[p<<1]),&rs(t[p<<1|1]);
    int mid((l+r)>>1);
    int lln = mid-l+1, rln = r-mid;
    np.sum[0] = ls.sum[0] + rs.sum[0];
    np.sum[1] = ls.sum[1] + rs.sum[1];
    np.llen[0] = ls.llen[0]==lln ? lln+rs.llen[0] : ls.llen[0];
    np.llen[1] = ls.llen[1]==lln ? lln+rs.llen[1] : ls.llen[1];
    np.rlen[0] = rs.rlen[0]==rln ? rln+ls.rlen[0] : rs.rlen[0];
    np.rlen[1] = rs.rlen[1]==rln ? rln+ls.rlen[1] : rs.rlen[1];
    np.mxlen[0] = m_max(ls.mxlen[0],rs.mxlen[0]);
    np.mxlen[0] = m_max(np.mxlen[0],ls.rlen[0]+rs.llen[0]);
    np.mxlen[1] = m_max(ls.mxlen[1],rs.mxlen[1]);
    np.mxlen[1] = m_max(np.mxlen[1],ls.rlen[1]+rs.llen[1]);
}
void tag(int l,int r,int p) {   //下放标记
    Sgn &np(t[p]),&ls(t[p<<1]),&rs(t[p<<1|1]);
    int mid((l+r)>>1);
    int lln = mid-l+1, rln = r-mid;
    if(np.lzt) {    //抹平
        if(np.lza) {    //抹平为0
            ls.sum[1] = ls.llen[1] = ls.rlen[1] = ls.mxlen[1] = lln;
            rs.sum[1] = rs.llen[1] = rs.rlen[1] = rs.mxlen[1] = rln;
            ls.sum[0] = ls.llen[0] = ls.rlen[0] = ls.mxlen[0] = 0;
            rs.sum[0] = rs.llen[0] = rs.rlen[0] = rs.mxlen[0] = 0;
            ls.lza = rs.lza = true;
        } else {        //抹平为1
            ls.sum[0] = ls.llen[0] = ls.rlen[0] = ls.mxlen[0] = lln;
            rs.sum[0] = rs.llen[0] = rs.rlen[0] = rs.mxlen[0] = rln;
            ls.sum[1] = ls.llen[1] = ls.rlen[1] = ls.mxlen[1] = 0;
            rs.sum[1] = rs.llen[1] = rs.rlen[1] = rs.mxlen[1] = 0;
            ls.lza = rs.lza = false;
        }
        ls.lzt = rs.lzt = true;
        ls.lzi = rs.lzi = false;
        np.lzt = false;
    }
    if(np.lzi) {    //取反
        m_swap(ls.sum[0],ls.sum[1]);
        m_swap(ls.llen[0],ls.llen[1]);
        m_swap(ls.rlen[0],ls.rlen[1]);
        m_swap(ls.mxlen[0],ls.mxlen[1]);
        m_swap(rs.sum[0],rs.sum[1]);
        m_swap(rs.llen[0],rs.llen[1]);
        m_swap(rs.rlen[0],rs.rlen[1]);
        m_swap(rs.mxlen[0],rs.mxlen[1]);
        ls.lzi = !ls.lzi;
        rs.lzi = !rs.lzi;
        np.lzi = false;
    }
}
void bud(int l,int r,int p) {   //建树
    Sgn &np(t[p]),&ls(t[p<<1]),&rs(t[p<<1|1]);
    np.lzt = np.lza = np.lzi = false;
    if(l==r) {
        np.sum[a[l]] = np.llen[a[l]] = np.rlen[a[l]] = np.mxlen[a[l]] = 1;
        np.sum[a[l]^1] = np.llen[a[l]^1] = np.rlen[a[l]^1] = np.mxlen[a[l]^1] = 0;
        return;
    }
    int mid((l+r)>>1);
    bud(l,mid,p<<1);
    bud(mid+1,r,p<<1|1);
    upd(l,r,p);
}
void mdfa(int l,int r,int ml,int mr,int ty,int p) { //修改抹平
    Sgn &np(t[p]),&ls(t[p<<1]),&rs(t[p<<1|1]);
    if(ml<=l && mr>=r) {
        np.sum[ty] = np.llen[ty] = np.rlen[ty] = np.mxlen[ty] = r-l+1;
        np.sum[ty^1] = np.llen[ty^1] = np.rlen[ty^1] = np.mxlen[ty^1] = 0;
        np.lzt = true;
        np.lza = ty==1;
        np.lzi = false; //抹平后取反操作无意义
        return;
    }
    int mid((l+r)>>1);
    tag(l,r,p);
    if(ml<=mid) {
        mdfa(l,mid,ml,mr,ty,p<<1);
    }
    if(mr>mid) {
        mdfa(mid+1,r,ml,mr,ty,p<<1|1);
    }
    upd(l,r,p);
}
void mdfi(int l,int r,int ml,int mr,int p) {    //修改取反
    Sgn &np(t[p]),&ls(t[p<<1]),&rs(t[p<<1|1]);
    if(ml<=l && mr>=r) {
        m_swap(np.sum[0],np.sum[1]);
        m_swap(np.llen[0],np.llen[1]);
        m_swap(np.rlen[0],np.rlen[1]);
        m_swap(np.mxlen[0],np.mxlen[1]);
        np.lzi = !np.lzi;   
        return;
    }
    int mid((l+r)>>1);
    tag(l,r,p);
    if(ml<=mid) {
        mdfi(l,mid,ml,mr,p<<1);
    }
    if(mr>mid) {
        mdfi(mid+1,r,ml,mr,p<<1|1);
    }
    upd(l,r,p);
}
Sgn qry(int l,int r,int ql,int qr,int p) {  //查询, 结果直接用结构体表示
    Sgn &np(t[p]),&ls(t[p<<1]),&rs(t[p<<1|1]);
    int mid((l+r)>>1);
    if(ql==l && qr==r) {
        return np;
    }
    tag(l,r,p);
    if(qr<=mid) {
        return qry(l,mid,ql,qr,p<<1);
    } else if(ql>mid) {
        return qry(mid+1,r,ql,qr,p<<1|1);
    } else {
        /*冗长的合并OuO*/
        Sgn ret = (Sgn){};
        Sgn tl = qry(l,mid,ql,mid,p<<1),tr = qry(mid+1,r,mid+1,qr,p<<1|1);
        ret.sum[0] = tl.sum[0] + tr.sum[0];
        ret.sum[1] = tl.sum[1] + tr.sum[1];
        ret.llen[0] = tl.llen[0] == mid-ql+1 ? mid-ql+1+tr.llen[0] : tl.llen[0];
        ret.llen[1] = tl.llen[1] == mid-ql+1 ? mid-ql+1+tr.llen[1] : tl.llen[1];
        ret.rlen[0] = tr.rlen[0] == qr-mid ? qr-mid+tl.rlen[0] : tr.rlen[0];
        ret.rlen[1] = tr.rlen[1] == qr-mid ? qr-mid+tl.rlen[1] : tr.rlen[1];
        ret.mxlen[0] = m_max(tl.mxlen[0],tr.mxlen[0]);
        ret.mxlen[0] = m_max(ret.mxlen[0],tl.rlen[0]+tr.llen[0]);
        ret.mxlen[1] = m_max(tl.mxlen[1],tr.mxlen[1]);
        ret.mxlen[1] = m_max(ret.mxlen[1],tl.rlen[1]+tr.llen[1]);
        ret.lzt = ret.lza = ret.lzi = false;
        return ret;
    }
}

int main() {
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i(1);i<=n;++i) {
        scanf("%d",a+i);
    }
    bud(1,n,1);
    while(m--) {
        int opt,l,r;
        scanf("%d %d %d",&opt,&l,&r);
        ++l, ++r;
        switch(opt) {
            case 0:
                mdfa(1,n,l,r,0,1);
                break;
            case 1:
                mdfa(1,n,l,r,1,1);
                break;
            case 2:
                mdfi(1,n,l,r,1);
                break;
            case 3:
                printf("%d\n",qry(1,n,l,r,1).sum[1]);
                break;
            default:
                printf("%d\n",qry(1,n,l,r,1).mxlen[1]);
                break;
        }
    }
    return 0;
}