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 閱讀(134)
評論(0) 編輯 收藏 引用