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) 编辑 收藏 引用