2014
03-23

# Sequence operation

lxhgww got a sequence contains n characters which are all ’0′s or ’1′s.
We have five operations here:
Change operations:
0 a b change all characters into ’0′s in [a , b]
1 a b change all characters into ’1′s in [a , b]
2 a b change all ’0′s into ’1′s and change all ’1′s into ’0′s in [a, b]
Output operations:
3 a b output the number of ’1′s in [a, b]
4 a b output the length of the longest continuous ’1′ string in [a , b]

T(T<=10) in the first line is the case number.
Each case has two integers in the first line: n and m (1 <= n , m <= 100000).
The next line contains n characters, ’0′ or ’1′ separated by spaces.
Then m lines are the operations:
op a b: 0 <= op <= 4 , 0 <= a <= b < n.

T(T<=10) in the first line is the case number.
Each case has two integers in the first line: n and m (1 <= n , m <= 100000).
The next line contains n characters, ’0′ or ’1′ separated by spaces.
Then m lines are the operations:
op a b: 0 <= op <= 4 , 0 <= a <= b < n.

1
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

5
2
6
5

printf和scanf明显节省很多时间。

#include <iostream>

using namespace std;

#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define delf int m=(l+r)>>1
int sum[444444];
int len[2][3][444444];
int op[2][444444];

int max(int a,int b)
{
return a>b?a:b;
}

void pushup(int l,int r,int rt)
{
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
for (int i=0;i<2;i++)
{
if (len[i][0][rt<<1]==(r-l+2)/2)
len[i][0][rt]=len[i][0][rt<<1]+len[i][0][rt<<1|1];
else
len[i][0][rt]=len[i][0][rt<<1];
if (len[i][2][rt<<1|1]==(r-l+1)/2)
len[i][2][rt]=len[i][2][rt<<1]+len[i][2][rt<<1|1];
else
len[i][2][rt]=len[i][2][rt<<1|1];
len[i][1][rt]=max(len[i][2][rt<<1]+len[i][0][rt<<1|1],max(len[i][1][rt<<1],len[i][1][rt<<1|1]));
}
}

void build(int l,int r,int rt)
{
op[0][rt]=-1;
op[1][rt]=0;
if (l==r)
{
scanf("%d",&sum[rt]);
len[1][0][rt]=len[1][1][rt]=len[1][2][rt]=sum[rt];
len[0][0][rt]=len[0][1][rt]=len[0][2][rt]=1-sum[rt];
return ;
}
delf;
build(lson);
build(rson);
pushup(l,r,rt);
}

void opea(int l,int r,int rt)
{
if (op[0][rt]!=-1)
op[0][rt]=1-op[0][rt];
else
{
if (op[1][rt]==1)
op[1][rt]=0;
else
op[1][rt]=1;
}
sum[rt]=r-l+1-sum[rt];
for (int i=0;i<3;i++)
{
int t=len[0][i][rt];
len[0][i][rt]=len[1][i][rt];
len[1][i][rt]=t;
}
}

void setupdate(int v,int l,int r,int rt)
{
sum[rt]=(r-l+1)*v;
op[1][rt]=0;
op[0][rt]=v;
for (int i=0;i<3;i++)
{
len[0][i][rt]=(r-l+1)*(1-op[0][rt]);
len[1][i][rt]=(r-l+1)*op[0][rt];
}
}

void pushdown(int l,int r,int rt)
{
if (op[0][rt]>=0)
{
delf;
setupdate(op[0][rt],lson);
setupdate(op[0][rt],rson);
op[0][rt]=-1;
}
if(op[1][rt])
{
delf;
opea(lson);
opea(rson);
op[1][rt]=0;
}
}

void update(int L,int R,int k,int l,int r,int rt)
{
if (L<=l&&r<=R)
{
if (k==0||k==1)
setupdate(k,l,r,rt);
else
opea(l,r,rt);
return ;
}
pushdown(l,r,rt);
delf;
if (m>=L)
update(L,R,k,lson);
if (R>m)
update(L,R,k,rson);
pushup(l,r,rt);
}

int query(int L,int R,int l,int r,int rt)
{
if (L==l&&r==R)
return len[1][1][rt];
pushdown(l,r,rt);
delf;
if (L>m)
return query(L,R,rson);
if (R<=m)
return query(L,R,lson);
if (L<=m&&R>m)
{
int lr = query(L,m,lson);//左子树
int rr = query(m+1,R,rson);//右子树
//中间
int a = len[1][2][rt<<1];//左子树右边最长连续1，注意它的个数不应该大于区间[l,tree[rt<<1].r]的个数
if (a>m-L+1)
a=m-L+1;
int b = len[1][0][rt<<1|1];//右子树左边最长连续1，注意它的个数不应该大于区间[tree[rt<<1|1].l,r]的个数
if (b>R-m)
b=R-m;
return max(max(lr,rr),a+b);//最后取左子树、右子树和中间三者的最大值
}
}

int Query(int L,int R,int l,int r,int rt)
{
if (L<=l&&r<=R)
return sum[rt];
pushdown(l,r,rt);
delf;
int s=0;
if (L<=m)
s=s+Query(L,R,lson);
if (R>m)
s=s+Query(L,R,rson);
pushup(l,r,rt);
return s;
}

int main()
{
int m,n;
int r;
scanf("%d",&r);
while (r--)
{
scanf("%d%d",&n,&m);
build(1,n,1);
while (m--)
{
int k,a,b;
scanf("%d%d%d",&k,&a,&b);
if (k<=2)
update(a+1,b+1,k,1,n,1);
if (k==3)
printf("%d\n",Query(a+1,b+1,1,n,1));
if (k==4)
printf("%d\n",query(a+1,b+1,1,n,1));
}
}
}

1. 我还有个问题想请教一下，就是感觉对于新手来说，递归理解起来有些困难，不知有没有什么好的方法或者什么好的建议？

2. 第23行：
hash = -1是否应该改成hash[s ] = -1

因为是要把从字符串s的start位到当前位在hash中重置

修改提交后能accept，但是不修改居然也能accept