【转】poj 1823

#include<iostream>

#include<fstream>
 
using namespace std;
 
struct e{
    int l,r,cnt,cntl,cntr;
    int state;
};
 
e tree[48001];
 
 
int n,m;
 
void build(int s,int t,int p){
    int i,j,k;
    tree[p].l=s;tree[p].r=t;
    tree[p].state=-1;
    tree[p].cnt=tree[p].cntl=tree[p].cntr=t-s+1;
    if(s==t) return;
    else
    {
        k=(s+t)>>1;
        build(s,k,2*p);
        build(k+1,t,2*p+1);
    }
}
 
void godown(int p,int value){
    tree[p].state=0;
    tree[2*p].state=tree[2*p+1].state=value;
    if(value==-1)
    {
        tree[2*p].cnt=tree[2*p].cntl=tree[2*p].cntr=tree[2*p].r-tree[2*p].l+1;
        tree[2*p+1].cnt=tree[2*p+1].cntl=tree[2*p+1].cntr=tree[2*p+1].r-tree[2*p+1].l+1;
    }
    else
    {
        tree[2*p].cnt=tree[2*p].cntl=tree[2*p].cntr=0;
        tree[2*p+1].cnt=tree[2*p+1].cntl=tree[2*p+1].cntr=0;
    }
}
 
 
void update(int s,int t,int p,int value){
    int i,j,k;
    if(s<=tree[p].l&&tree[p].r<=t)
    {
        tree[p].state=value;
        if(value==-1)
        {
            i=tree[p].r-tree[p].l+1;
            tree[p].cnt=tree[p].cntl=tree[p].cntr=i;
        }
        else
            tree[p].cnt=tree[p].cntl=tree[p].cntr=0;
        return;
    }
    if(tree[p].state==value) return;
    if(tree[p].state==-value) godown(p,-value);
     
    if(t<=tree[p*2].r) update(s,t,2*p,value);
    else
        if(s>=tree[2*p+1].l) update(s,t,2*p+1,value);
        else
        {
            update(s,t,2*p,value);
            update(s,t,2*p+1,value);
        }
 
    if(tree[2*p].state==-1)
        tree[p].cntl=tree[2*p].cnt+tree[2*p+1].cntl;
    else
        tree[p].cntl=tree[2*p].cntl;
     
    if(tree[2*p+1].state==-1)
        tree[p].cntr=tree[2*p+1].cnt+tree[2*p].cntr;
    else
        tree[p].cntr=tree[2*p+1].cntr;
     
    if(tree[2*p+1].state==tree[2*p].state)
        tree[p].state=tree[2*p].state;
     
    i=tree[2*p].cntr+tree[2*p+1].cntl;
    j=max(tree[2*p].cnt,tree[2*p+1].cnt);
    tree[p].cnt=max(max(i,j),k);
}
 
void read(){
//  ifstream cin("in.txt");
    int i,j,k,s,t;
//  cin>>n>>m;
    scanf("%d%d",&n,&m);
    build(1,n,1);
    for(i=1;i<=m;i++)
    {
    //  cin>>j;
        scanf("%d",&j);
        if(j==1)
        {
        //  cin>>s>>t;
            scanf("%d%d",&s,&t);
            update(s,s+t-1,1,1);
        }
        else
            if(j==2)
            {
            //  cin>>s>>t;
                scanf("%d%d",&s,&t);
                update(s,s+t-1,1,-1);
            }
            else
                cout<<tree[1].cnt<<endl;
    }
}
 
int main(){
    read();
    return 0;
}
原文地址:https://www.cnblogs.com/lzhitian/p/2606314.html