「BZOJ1858」[SCOI2010] 序列操作

2014年4月29日5,2470

Description

lxhgww最近收到了一个01序列，序列里面包含了n个数，这些数要么是0，要么是1，现在对于这个序列有五种变换操作和询问操作： 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 对于每一种询问操作，lxhgww都需要给出回答，聪明的程序员们，你们能帮助他吗？

Input

输入数据第一行包括2个数，n和m，分别表示序列的长度和操作数目第二行包括n个数，表示序列的初始状态接下来m行，每行3个数，op, a, b，（0<=op<=4，0<=a<=b<n）表示对于区间[a, b]执行标号为op的操作=”” <=”” div=””>

Output

对于每一个询问操作，输出一行，包括1个数，表示其对应的答案

Sample Input

10 10
0 0 0 1 1 0 1 0 1 1
1 0 2
3 0 5
2 2 2
4 0 4
0 3 6
2 3 7
4 2 8
1 0 5
0 5 6
3 3 9

Sample Output

5
2
6
5

HINT

对于30%的数据，1<=n, m<=1000
对于100%的数据，1<=n, m<=100000

题解

本来想随便练练手的，以为就是处理多个标记的问题。。。结果坑进去了。。。

不过1A还是极好的

一开始看错题目了斯巴达，没看到操作4以为很水

后来突然意识到不仅上传很麻烦而且要写个合并。。。

然后乱改。。这样搞的常数很大

#include<iostream>
#include<cstdio>
#define N 100005
using namespace std;
int n,m; 
struct seg
{
    int l,r;
    int l0,l1,r0,r1,mx0,mx1,sum0,sum1;
    int rev,c,full;
    }t[N<<2];
void rev(int k)
{
    swap(t[k].l0,t[k].l1);
    swap(t[k].r0,t[k].r1);
    swap(t[k].mx0,t[k].mx1);
    swap(t[k].sum0,t[k].sum1);
    if(t[k].full!=-1)t[k].full^=1;
}
void color(int k,int v)
{
    t[k].rev=0;
    int s=t[k].r-t[k].l+1;
    if(v==0)
    {
       t[k].sum0=t[k].l0=t[k].r0=t[k].mx0=s;
       t[k].sum1=t[k].l1=t[k].r1=t[k].mx1=0;
    }
    else
    {
       t[k].sum0=t[k].l0=t[k].r0=t[k].mx0=0;
       t[k].sum1=t[k].l1=t[k].r1=t[k].mx1=s;
    }
    t[k].full=v;
}
seg merge(seg a,seg b) 
{
    seg tmp;tmp.l=a.l;tmp.r=b.r;
    tmp.rev=0;tmp.c=-1;
    tmp.l0=a.l0;tmp.l1=a.l1;
    tmp.r0=b.r0;tmp.r1=b.r1;
    tmp.mx0=max(a.mx0,b.mx0);
    tmp.mx1=max(a.mx1,b.mx1);
    tmp.mx0=max(tmp.mx0,a.r0+b.l0);
    tmp.mx1=max(tmp.mx1,a.r1+b.l1);
    tmp.sum0=a.sum0+b.sum0;
    tmp.sum1=a.sum1+b.sum1;
    if(a.full==0)tmp.l0=a.mx0+b.l0;
    else if(a.full==1)tmp.l1=a.mx1+b.l1;
    if(b.full==0)tmp.r0=b.mx0+a.r0;
    else if(b.full==1)tmp.r1=b.mx1+a.r1;
    if(a.full==b.full)
       tmp.full=a.full;
    else tmp.full=-1;
    return tmp;
}
void pushup(int k)
{
    t[k]=merge(t[k<<1],t[k<<1|1]);
}
void pushdown(int k)
{
    if(t[k].l==t[k].r)return;
    if(t[k].c!=-1)
    {
        t[k<<1].c=t[k<<1|1].c=t[k].c;
        color(k<<1,t[k].c);color(k<<1|1,t[k].c);
        t[k].c=-1;
    }
    if(t[k].rev)
    {
        t[k<<1].rev^=1;
        t[k<<1|1].rev^=1;
        rev(k<<1);rev(k<<1|1);
        t[k].rev=0;
    }
}
void build(int k,int l,int r)
{
    t[k].l=l;t[k].r=r;
    t[k].c=-1;
    if(l==r)
    {
        scanf("%d",&t[k].full);
        if(t[k].full)
        {t[k].l1=t[k].r1=t[k].mx1=t[k].sum1=1;}
        else
        {t[k].l0=t[k].r0=t[k].mx0=t[k].sum0=1;}
        return;
    }
    int mid=(l+r)>>1;
    build(k<<1,l,mid);build(k<<1|1,mid+1,r);
    pushup(k);
}
void change(int k,int x,int y,int v)
{
    pushdown(k);
    int l=t[k].l,r=t[k].r;
    if(l==x&&r==y)
    {
        color(k,v);
        t[k].c=v;
        return;
    }
    int mid=(l+r)>>1;
    if(mid>=y)change(k<<1,x,y,v);
    else if(mid<x)change(k<<1|1,x,y,v);
    else
    {
        change(k<<1,x,mid,v);
        change(k<<1|1,mid+1,y,v);
    }
    pushup(k);
}
void rever(int k,int x,int y)
{
    pushdown(k);
    int l=t[k].l,r=t[k].r;
    if(l==x&&r==y)
    {
        rev(k);
        t[k].rev=1;
        return;
    }
    int mid=(l+r)>>1;
    if(mid>=y)rever(k<<1,x,y);
    else if(mid<x)rever(k<<1|1,x,y);
    else
    {
        rever(k<<1,x,mid);
        rever(k<<1|1,mid+1,y);
    }
    pushup(k);
}
seg ask(int k,int x,int y)
{
    pushdown(k);
    int l=t[k].l,r=t[k].r;
    if(l==x&&y==r)return t[k];
    int mid=(l+r)>>1;
    if(mid>=y)return ask(k<<1,x,y);
    else if(mid<x)return ask(k<<1|1,x,y);
    else return merge(ask(k<<1,x,mid),ask(k<<1|1,mid+1,y));
}
int asksum(int k,int x,int y)
{
    pushdown(k);
    int l=t[k].l,r=t[k].r;
    if(l==x&&y==r)return t[k].sum1;
    int mid=(l+r)>>1;
    if(mid>=y)return asksum(k<<1,x,y);
    else if(mid<x)return asksum(k<<1|1,x,y);
    else return asksum(k<<1,x,mid)+asksum(k<<1|1,mid+1,y);
}
int main()
{
    scanf("%d%d",&n,&m);
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int f,x,y;
        scanf("%d%d%d",&f,&x,&y);
        x++;y++;
        switch(f)
        {
            case 0:change(1,x,y,0);break;
            case 1:change(1,x,y,1);break;
            case 2:rever(1,x,y);break;
            case 3:printf("%d\n",asksum(1,x,y));break;
            case 4:printf("%d\n",ask(1,x,y).mx1);break;
        }
    }
    return 0;
}

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

#include<iostream>

#include<cstdio>

#define N 100005

using namespace std;

int n,m;

struct seg

{

int l,r;

int l0,l1,r0,r1,mx0,mx1,sum0,sum1;

int rev,c,full;

}t[N<<2];

void rev(int k)

{

swap(t[k].l0,t[k].l1);

swap(t[k].r0,t[k].r1);

swap(t[k].mx0,t[k].mx1);

swap(t[k].sum0,t[k].sum1);

if(t[k].full!=-1)t[k].full^=1;

}

void color(int k,int v)

{

t[k].rev=0;

int s=t[k].r-t[k].l+1;

if(v==0)

{

t[k].sum0=t[k].l0=t[k].r0=t[k].mx0=s;

t[k].sum1=t[k].l1=t[k].r1=t[k].mx1=0;

}

else

{

t[k].sum0=t[k].l0=t[k].r0=t[k].mx0=0;

t[k].sum1=t[k].l1=t[k].r1=t[k].mx1=s;

}

t[k].full=v;

}

seg merge(seg a,seg b)

{

seg tmp;tmp.l=a.l;tmp.r=b.r;

tmp.rev=0;tmp.c=-1;

tmp.l0=a.l0;tmp.l1=a.l1;

tmp.r0=b.r0;tmp.r1=b.r1;

tmp.mx0=max(a.mx0,b.mx0);

tmp.mx1=max(a.mx1,b.mx1);

tmp.mx0=max(tmp.mx0,a.r0+b.l0);

tmp.mx1=max(tmp.mx1,a.r1+b.l1);

tmp.sum0=a.sum0+b.sum0;

tmp.sum1=a.sum1+b.sum1;

if(a.full==0)tmp.l0=a.mx0+b.l0;

else if(a.full==1)tmp.l1=a.mx1+b.l1;

if(b.full==0)tmp.r0=b.mx0+a.r0;

else if(b.full==1)tmp.r1=b.mx1+a.r1;

if(a.full==b.full)

tmp.full=a.full;

else tmp.full=-1;

return tmp;

}

void pushup(int k)

{

t[k]=merge(t[k<<1],t[k<<1|1]);

}

void pushdown(int k)

{

if(t[k].l==t[k].r)return;

if(t[k].c!=-1)

{

t[k<<1].c=t[k<<1|1].c=t[k].c;

color(k<<1,t[k].c);color(k<<1|1,t[k].c);

t[k].c=-1;

}

if(t[k].rev)

{

t[k<<1].rev^=1;

t[k<<1|1].rev^=1;

rev(k<<1);rev(k<<1|1);

t[k].rev=0;

}

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

{

t[k].l=l;t[k].r=r;

t[k].c=-1;

if(l==r)

{

scanf("%d",&t[k].full);

if(t[k].full)

{t[k].l1=t[k].r1=t[k].mx1=t[k].sum1=1;}

else

{t[k].l0=t[k].r0=t[k].mx0=t[k].sum0=1;}

return;

}

int mid=(l+r)>>1;

build(k<<1,l,mid);build(k<<1|1,mid+1,r);

pushup(k);

}

void change(int k,int x,int y,int v)

{

pushdown(k);

int l=t[k].l,r=t[k].r;

if(l==x&&r==y)

{

color(k,v);

t[k].c=v;

return;

}

int mid=(l+r)>>1;

if(mid>=y)change(k<<1,x,y,v);

else if(mid<x)change(k<<1|1,x,y,v);

else

{

change(k<<1,x,mid,v);

change(k<<1|1,mid+1,y,v);

}

pushup(k);

}

void rever(int k,int x,int y)

{

pushdown(k);

int l=t[k].l,r=t[k].r;

if(l==x&&r==y)

{

rev(k);

t[k].rev=1;

return;

}

int mid=(l+r)>>1;

if(mid>=y)rever(k<<1,x,y);

else if(mid<x)rever(k<<1|1,x,y);

else

{

rever(k<<1,x,mid);

rever(k<<1|1,mid+1,y);

}

pushup(k);

}

seg ask(int k,int x,int y)

{

pushdown(k);

int l=t[k].l,r=t[k].r;

if(l==x&&y==r)return t[k];

int mid=(l+r)>>1;

if(mid>=y)return ask(k<<1,x,y);

else if(mid<x)return ask(k<<1|1,x,y);

else return merge(ask(k<<1,x,mid),ask(k<<1|1,mid+1,y));

}

int asksum(int k,int x,int y)

{

pushdown(k);

int l=t[k].l,r=t[k].r;

if(l==x&&y==r)return t[k].sum1;

int mid=(l+r)>>1;

if(mid>=y)return asksum(k<<1,x,y);

else if(mid<x)return asksum(k<<1|1,x,y);

else return asksum(k<<1,x,mid)+asksum(k<<1|1,mid+1,y);

}

int main()

{

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

build(1,1,n);

for(int i=1;i<=m;i++)

{

int f,x,y;

scanf("%d%d%d",&f,&x,&y);

x++;y++;

switch(f)

{

case 0:change(1,x,y,0);break;

case 1:change(1,x,y,1);break;

case 2:rever(1,x,y);break;

case 3:printf("%d\n",asksum(1,x,y));break;

case 4:printf("%d\n",ask(1,x,y).mx1);break;

}

return 0;

}

« 「BZOJ1984」月下“毛景树” 「BZOJ3212」Pku3468 A Simple Problem with Integers »

hzwer.com _ Home | http://hzwer.com

「BZOJ1858」[SCOI2010] 序列操作

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论