posts - 74,  comments - 33,  trackbacks - 0
Light Switching
这道题目昨天的时候没写,今天中午开始写,先囧下自己中午就是因为这道题目,结果上体育课的时候洗完澡一看自己没带泳裤。。。。
Faint!无语,跟老师说补课还是不让走(说什么洗澡了就不能走)。。。。结果在那里看着别人游泳我自己站在岸边还不敢坐下(全是水)又累又无聊。想了下这道题目,而那时想的优化也没能是我的程序逃脱TLE。。。。
偶然间看到网上一牛的结题报告说惰性跟新,对啊相当于我的标记数组mark,最后一只改,改,在WA有TLE之间徘徊。
终于再改了查找时候有更新mark的代码后AC。代码如下(感觉代码还是比较容易看懂):
#include<cstdio>
#include
<cstring>
#define MAXN 300000
using namespace std;
struct NODE{
    
int sum,l,r;
    
bool mark;    
}
ST[MAXN];
void SST(int x,int l,int r){
    ST[x].l
=l,ST[x].r=r;
    ST[x].sum
=0,ST[x].mark=false;
    
if(l<r){
        
int mid=(l+r)>>1;
        SST(
2*x,l,mid);
        SST(
2*x+1,mid+1,r);    
    }

    
return ;
}

int Find(int x,int l,int r){
    
int mid=(ST[x].l+ST[x].r)>>1;
    
if(ST[x].l==l&&ST[x].r==r)return ST[x].sum;
    
if(ST[x].mark){
        ST[x].mark
=false;
        
if(ST[x].l<ST[x].r){
            ST[
2*x+1].mark^=1,ST[2*x].mark^=1;
            ST[
2*x].sum=(ST[2*x].r-ST[2*x].l+1)-ST[2*x].sum;
            ST[
2*x+1].sum=(ST[2*x+1].r-ST[2*x+1].l+1)-ST[2*x+1].sum;
        }
    
    }

    
if(l>mid)return Find(2*x+1,l,r);
    
if(r<mid+1)return Find(2*x,l,r);
    
return Find(2*x,l,mid)+Find(2*x+1,mid+1,r);
}

void Insert(int x,int l,int r){
    
int mid=(ST[x].l+ST[x].r)>>1;
    
if(ST[x].l==l&&ST[x].r==r){
        ST[x].mark
^=1;
        ST[x].sum
=(r-l+1)-ST[x].sum;
    }

    
else{
        
if(ST[x].mark){
            ST[x].mark
=false;
            
if(ST[x].l<ST[x].r){
                ST[
2*x+1].mark^=1,ST[2*x].mark^=1;
                ST[
2*x].sum=(ST[2*x].r-ST[2*x].l+1)-ST[2*x].sum;
                ST[
2*x+1].sum=(ST[2*x+1].r-ST[2*x+1].l+1)-ST[2*x+1].sum;
            }
    
        }

        
if(l>mid)Insert(2*x+1,l,r);
        
else if(r<mid+1)Insert(2*x,l,r);
        
else {
            Insert(
2*x,l,mid);
            Insert(
2*x+1,mid+1,r);    
        }

        ST[x].sum
=ST[x*2].sum+ST[2*x+1].sum;
    }

}

int main(){
    
int n,m,i,k,a,b;
    
while(scanf("%d %d",&n,&m)!=EOF){
        
for(SST(1,1,n),i=0;i<m;i++){
            scanf(
"%d %d %d",&k,&a,&b);
            
if(k)printf("%d\n",Find(1,a,b));
            
else Insert(1,a,b);    
        }
    
    }
    
}

posted on 2009-05-18 17:50 KNIGHT 阅读(128) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2009年5月>
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

常用链接

留言簿(8)

随笔档案

文章档案

Friends

OJ

搜索

  •  

最新评论

阅读排行榜

评论排行榜