HDU 3397 Sequence operation (선분 트 리: 세그먼트 업데이트, 연속 대상 하위 문자열 길이 조회)

HDU 3397 Sequence operation (선분 트 리: 세그먼트 업데이트, 연속 대상 하위 문자열 길이 조회)
http://acm.hdu.edu.cn/showproblem.php?pid=3397
Problem Description
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]
 
Input
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.
분석:
전체 query 에 서 는 접두사 와 접 두 사 를 조회 하 는 함 수 를 만 들 지 않 아 도 됩 니 다. 특히 최적화 된 곳 에 주의 하 십시오.
       1. 이 문 제 는 POJ 3225 와 비슷 하 다.http://blog.csdn.net/u013480600/article/details/22284341또한 cover 작업 과 이 또는 작업 이 동시에 있 습 니 다. 그러나 여기 서 이 또는 표 시 를 사용 하면 특정한 노드 가 이 또는 이 되 어 아래로 돌아 가지 않 고 sub, pre, suf 의 정 보 를 계산 할 수 없습니다. 따라서 이 또는 위 치 를 설정 하지 않 습 니 다. 이 또는 작업 이 있 으 면 끝까지 돌아 가 PushUp 업데이트 합 니 다.
       2. 한 그루 의 선분 트 리 를 유지 합 니 다. 근본 적 인 정 보 는 cover (1 또는 0 은 1 또는 0 으로 덮어 졌 음 을 표시 합 니 다. - 1 은 하위 노드 의 cover 값 이 일치 하지 않 음 을 표시 합 니 다) 입 니 다. 보조 조회 정 보 는 sum (노드 중 1 의 개수), sub (노드 가 가리 키 는 구간 내 최 장 연속 1 의 개수), pre (노드 가 가리 키 는 구간 최 장 접두사 연속 1 의 개수), suf (노드 가 가리 키 는 구간 최 장 접두사 연속 1 의 개수) 입 니 다.이 라인 트 리 는 update 작업 2 개, query 작업 4 개가 있 습 니 다. 여기 서 는 HDU 3308 과 유사 합 니 다.http://blog.csdn.net/u013480600/article/details/22421981.HDU 3308 의 약간 강화 판 으로 볼 수 있 습 니 다.
       3. 선분 트 리 조작:
PushUp (i, l, r): 아들 노드 의 cover 와 sub, sum suf, pre 에 따라 부모 노드 의 모든 정 보 를 업데이트 합 니 다. 주도면밀 하 게 고려 하면 됩 니 다.
PushDown (i, l, r): 부모 노드 의 cover, sub, suf, sum, pre 에 따라 하위 노드 의 모든 대응 정 보 를 업데이트 합 니 다.
build (i, l, r): 트 리 를 재 귀적 으로 만 들 고 PushUp 은 부모 노드 정 보 를 업데이트 합 니 다.
update 1 (ql, qr, v, i, l, r): [ql, qr] 와 [l, r] 구간 을 겹 치 는 부분 을 v 값 으로 설정 합 니 다.
만약 ql < = l 및 r < = qr 가 cover, sub, sum, suf, pre 의 정 보 를 직접 업데이트 합 니 다. 그렇지 않 으 면 PushDown 을 먼저 한 다음 update 1 정도 의 아들 에 게 돌아 간 다음 PushUp 에 있 습 니 다.
update 2 (ql, qr, i, l, r): [ql, qr] 와 [l, r] 구간 이 겹 치 는 부분 에서 이 또는 작업 을 수행 하 겠 다 는 뜻 입 니 다. l = = r 면 잎 노드 가 다 르 거나 모든 정 보 를 업데이트 합 니 다. 그렇지 않 으 면 PushDown 다음 에 세그먼트 update 2 를 나 눈 다음 PushUp.
query sum (ql, qr, i, l, r): 쿼 리 [ql, qr] 와 [l, r] 가 겹 치 는 부분의 1 개 수 를 표시 합 니 다. 만약 ql < = l 및 r < = qr 가 sum [i] 를 직접 되 돌려 주지 않 으 면 PushDown, 세그먼트 쿼 리. 총 화 를 되 돌려 줍 니 다.
query pre (ql, qr, i, l, r): [ql, qr] 와 [l, r] 의 겹 치 는 부분의 최 장 접두사 연속 1 개 수 를 조회 합 니 다. 만약 ql < = l & r < = qr 가 pre [i] 로 직접 돌아 갑 니 다. 그렇지 않 으 면 PushDown 을 먼저 하고 공공 부분 이 [l, r] 에 만 있 으 면왼쪽 아들 은 왼쪽 아들 로 돌아 갑 니 다. 오른쪽 에 만 있 으 면 오른쪽 아들 로 돌아 갑 니 다. 양쪽 에 모두 공공 부분 이 있다 면 왼쪽 아들 로 계산 하 세 요. 오른쪽 아들 의 접두사 공공 부분 도 추가 할 필요 가 있 는 지 고려 하고 있 습 니 다.
query suf (ql, qr, i, l, r): [ql, qr] 와 [l, r] 의 겹 치 는 부분의 최 장 접미사 연속 1 개 수 를 조회 합 니 다. 만약 ql < = l & r < = qr 가 suf [i] 로 직접 돌아 갑 니 다. 그렇지 않 으 면 PushDown 을 먼저 하고 공공 부분 이 [l, r] 에 만 있 으 면왼쪽 아들 은 왼쪽 아들 로 돌아 갑 니 다. 오른쪽 에 만 있 으 면 오른쪽 아들 로 돌아 갑 니 다. 양쪽 에 모두 공공 부분 이 있다 면 오른쪽 아들 로 계산 합 니 다. 왼쪽 아들 의 접미사 공공 부분 도 추가 할 필요 가 있 는 지 고려 하고 있 습 니 다.
query (ql, qr, i, l, r): [ql, qr] 와 [l, r] 의 겹 치 는 부분의 최 장 연속 1 시퀀스 길 이 를 조회 합 니 다.
ql & l & r < = qr 가 있 으 면 sub [i] 로 바로 돌아 갑 니 다. 그렇지 않 으 면 PushDown 을 먼저 하고 왼쪽 아들 의 sub (공공 부분 이 있 으 면) 와 오른쪽 아들 의 sub (공공 부분 이 있 으 면) 를 비교 해 야 합 니 다. 그리고 왼쪽 아들 의 접미사 에 오른쪽 아들 의 접두사 (즉 [ql, qr] yu [l, r] 의 좌우 아들 은 모두 공공 부분 이 있 습 니 다) 를 비교 해 야 합 니 다.
... 결국 결 과 를 되 돌려 줍 니 다.
먼저 제출 한 코드 가 시간 을 초 과 했 습 니 다. update 2 의 업데이트 작업 이 최적화 되면 AC 가 됩 니 다.
AC 코드: 1062 ms.

<span style="font-size:18px;">#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define lson i*2,l,m
#define rson i*2+1,m+1,r
#define root 1,0,n-1
const int MAXN = 100000+100;
int cover[MAXN*4];//    
int sum[MAXN*4],sub[MAXN*4],pre[MAXN*4],suf[MAXN*4];//    
void PushDown(int i,int l,int r)
{
    int m=(l+r)/2;
    if(cover[i]!=-1)
    {
        cover[i*2]=cover[i*2+1]=cover[i];
        if(cover[i]==0)
        {
            sum[i*2]=sum[i*2+1]=0;
            sub[i*2]=sub[i*2+1]=0;
            pre[i*2]=pre[i*2+1]=0;
            suf[i*2]=suf[i*2+1]=0;
        }
        else if(cover[i]==1)
        {
            sum[i*2]=sub[i*2]=pre[i*2]=suf[i*2]=m-l+1;
            sum[i*2+1]=sub[i*2+1]=pre[i*2+1]=suf[i*2+1]=r-m;
        }
    }
}
void PushUp(int i,int l,int r)
{
    int m=(l+r)/2;
    //cover
    if(cover[i*2]==-1 || cover[i*2+1]==-1)
        cover[i]=-1;
    else if(cover[i*2] != cover[i*2+1])
        cover[i]=-1;
    else
        cover[i]=cover[i*2];

    //sum
    sum[i]=sum[i*2]+sum[i*2+1];

    //sub
    sub[i]=max(suf[i*2]+pre[i*2+1] , max(sub[i*2] , sub[i*2+1]));

    //pre
    pre[i]=pre[i*2];
    if(pre[i] == m-l+1) pre[i] += pre[i*2+1];

    //suf
    suf[i]=suf[i*2+1];
    if(suf[i]==r-m) suf[i] += suf[i*2];
}
void build(int i,int l,int r)
{
    if(l==r)
    {
        scanf("%d",&sum[i]);
        sub[i]=suf[i]=pre[i]=cover[i]=sum[i];
        return ;
    }
    int m=(l+r)/2;
    build(lson);
    build(rson);
    PushUp(i,l,r);
}
void update_1(int ql,int qr,int v,int i,int l,int r)
{
    if(ql<=l && r<=qr)
    {
        cover[i]=v;
        sum[i]=(r-l+1)*v;
        sub[i]=pre[i]=suf[i]= (v?r-l+1:0);
        return ;
    }
    PushDown(i,l,r);
    int m=(l+r)/2;
    if(ql<=m) update_1(ql,qr,v,lson);
    if(m<qr) update_1(ql,qr,v,rson);
    PushUp(i,l,r);
}
void update_2(int ql,int qr,int i,int l,int r)
{
    if(ql<=l && r<=qr)//   ,        
    {
        if(cover[i]!=-1)
        {
            cover[i] ^=1;
            sum[i]=sub[i]=pre[i]=suf[i]= (cover[i]?(r-l+1):0) ;
            return ;
        }
    }
    PushDown(i,l,r);
    int m=(l+r)/2;
    if(ql<=m) update_2(ql,qr,lson);
    if(m<qr) update_2(ql,qr,rson);
    PushUp(i,l,r);
}
int query_sum(int ql,int qr,int i,int l,int r)
{
    if(ql<=l && r<=qr)
        return sum[i];
    PushDown(i,l,r);
    int m=(l+r)/2;
    int res=0;
    if(ql<=m) res += query_sum(ql,qr,lson);
    if(m<qr) res += query_sum(ql,qr,rson);
    return res;
}
/*
int query_pre(int ql,int qr,int i,int l,int r)
{
    if(ql<=l && r<=qr)
        return pre[i];
    PushDown(i,l,r);
    int m=(l+r)/2;
    if(qr<=m) return query_pre(ql,qr,lson);
    if(m<ql) return query_pre(ql,qr,rson);
    int L = query_pre(ql,qr,lson);
    if(L==m-l+1) L += query_pre(ql,qr,rson);
    return L;
}
int query_suf(int ql,int qr,int i,int l,int r)
{
    if(ql<=l && r<=qr)
        return suf[i];
    PushDown(i,l,r);
    int m=(r+l)/2;
    if(qr<=m) return query_suf(ql,qr,lson);
    if(m<ql) return query_suf(ql,qr,rson);
    int R = query_suf(ql,qr,rson);
    if(R == r-m) R += query_suf(ql,qr,lson);
    return R;
}
*/
int query(int ql,int qr,int i,int l,int r)
{
    if(ql<=l && r<=qr)
        return sub[i];
    PushDown(i,l,r);
    int m=(l+r)/2;
    int len1=0,len2=0,len3=0;
    if(ql<=m) len1 = query(ql,qr,lson);
    if(m<qr) len2=query(ql,qr,rson);
    if(ql<=m && m<qr)
        len3 = min(m-ql+1,suf[i*2])+min(qr-m,pre[i*2+1]);//   
        //len3 = query_suf(ql,qr,lson)+query_pre(ql,qr,rson);
    //printf("l==%d,r==%d,len1=%d len2=%d len3=%d suf[i*2]=%d,pre[i*2+1]=%d
",l,r,len1,len2,len3,suf[i*2],pre[i*2+1]);
    return max(len3,max(len1,len2));
}
int main()
{
    int T,n,m;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        build(root);
        while(m--)
        {
            int op,a,b;
            scanf("%d%d%d",&op,&a,&b);
            if(op==0)
                update_1(a,b,0,root);
            else if(op==1)
                update_1(a,b,1,root);
            else if(op==2)
                update_2(a,b,root);
            else if(op==3)
                printf("%d
",query_sum(a,b,root));
            else if(op==4)
                printf("%d
",query(a,b,root));
        }
    }
    return 0;
}
</span>