首页 > 代码库 > AC日记——开关灯 codevs 1690
AC日记——开关灯 codevs 1690
开关灯
思路:
线段树;
bool懒标记维护;
更新区间时是区间总值减去当前值;
来,上代码:
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;#define maxn 100005struct TreeNodeType { int l,r,dis,lit,mid,flag;};struct TreeNodeType tree[maxn<<2];int n,m;inline void in(int &now){ char Cget=getchar();now=0; while(Cget>‘9‘||Cget<‘0‘) Cget=getchar(); while(Cget>=‘0‘&&Cget<=‘9‘) { now=now*10+Cget-‘0‘; Cget=getchar(); }}void tree_build(int now,int l,int r){ tree[now].l=l,tree[now].r=r,tree[now].lit=r-l+1; if(l==r) return ; tree[now].mid=l+r>>1; tree_build(now<<1,l,tree[now].mid); tree_build(now<<1|1,tree[now].mid+1,r);}inline void tree_down(int now){ tree[now<<1].flag^=1,tree[now<<1|1].flag^=1; tree[now<<1].dis=tree[now<<1].lit-tree[now<<1].dis; tree[now<<1|1].dis=tree[now<<1|1].lit-tree[now<<1|1].dis; tree[now].flag=0;}void tree_change(int now,int l,int r){ if(tree[now].l==l&&tree[now].r==r) { tree[now].dis=tree[now].lit-tree[now].dis; tree[now].flag^=1; return ; } if(tree[now].flag) tree_down(now); if(l>tree[now].mid) tree_change(now<<1|1,l,r); else if(r<=tree[now].mid) tree_change(now<<1,l,r); else { tree_change(now<<1,l,tree[now].mid); tree_change(now<<1|1,tree[now].mid+1,r); } tree[now].dis=tree[now<<1].dis+tree[now<<1|1].dis;}int tree_query(int now,int l,int r){ if(tree[now].l==l&&tree[now].r==r) return tree[now].dis; if(tree[now].flag) tree_down(now); if(l>tree[now].mid) tree_query(now<<1|1,l,r); else if(r<=tree[now].mid) tree_query(now<<1,l,r); else return tree_query(now<<1,l,tree[now].mid)+tree_query(now<<1|1,tree[now].mid+1,r);}int main(){ in(n),in(m);int op,u,v; tree_build(1,1,n); for(;m--;) { in(op),in(u),in(v); if(op) printf("%d\n",tree_query(1,u,v)); else tree_change(1,u,v); } return 0;}
AC日记——开关灯 codevs 1690
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。