AC日记——开关灯 codevs 1690
2024-08-30 09:28:38
思路:
线段树;
bool懒标记维护;
更新区间时是区间总值减去当前值;
来,上代码:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; #define maxn 100005 struct TreeNodeType {
int l,r,dis,lit,mid,flag;
};
struct TreeNodeType tree[maxn<<]; int n,m; inline void in(int &now)
{
char Cget=getchar();now=;
while(Cget>''||Cget<'') Cget=getchar();
while(Cget>=''&&Cget<='')
{
now=now*+Cget-'';
Cget=getchar();
}
} void tree_build(int now,int l,int r)
{
tree[now].l=l,tree[now].r=r,tree[now].lit=r-l+;
if(l==r) return ;
tree[now].mid=l+r>>;
tree_build(now<<,l,tree[now].mid);
tree_build(now<<|,tree[now].mid+,r);
} inline void tree_down(int now)
{
tree[now<<].flag^=,tree[now<<|].flag^=;
tree[now<<].dis=tree[now<<].lit-tree[now<<].dis;
tree[now<<|].dis=tree[now<<|].lit-tree[now<<|].dis;
tree[now].flag=;
} 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^=;
return ;
}
if(tree[now].flag) tree_down(now);
if(l>tree[now].mid) tree_change(now<<|,l,r);
else if(r<=tree[now].mid) tree_change(now<<,l,r);
else
{
tree_change(now<<,l,tree[now].mid);
tree_change(now<<|,tree[now].mid+,r);
}
tree[now].dis=tree[now<<].dis+tree[now<<|].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<<|,l,r);
else if(r<=tree[now].mid) tree_query(now<<,l,r);
else return tree_query(now<<,l,tree[now].mid)+tree_query(now<<|,tree[now].mid+,r);
} int main()
{
in(n),in(m);int op,u,v;
tree_build(,,n);
for(;m--;)
{
in(op),in(u),in(v);
if(op) printf("%d\n",tree_query(,u,v));
else tree_change(,u,v);
}
return ;
}
最新文章
- Nodejs 饭店
- 浅谈学习掌握linux系统的优势
- HotSpot 自动内存管理笔记与实战
- hdu 1811 Rank of Tetris (并查集+拓扑排序)
- 368. Largest Divisible Subset -- 找出一个数组使得数组内的数能够两两整除
- c# 调用 ShellExecute
- Aliyun OSS SDK 异步分块上传导致应用异常退出
- asp.net MVC FileResult在IE下异常的解决办法
- linux可重入、异步信号安全和线程安全
- NIO和IO(转)
- OSI七层协议模型、TCP/IP四层模型和五层协议体系结构之间的关系
- petapoco 实体中字段去掉关联(类似于EF中的NotMap)
- 使用javaWeb的二大(Listener、Filter)组件实现分IP统计访问次数
- rsync 远程同步 实时同步备份 两种免交互的方式实现实时备份
- Db2性能:系统CPU高问题分析的一些思路
- hdu 6041 I Curse Myself 无向图找环+优先队列
- Mysql 视图使用
- yum 安装报错:Could not retrieve mirrorlist http://mirrorlist.centos.org/?release=7&;arch=x86_64&;repo=os&;infra=stock error was 14: curl#6 - ";Could not resolve host: mirrorlist.centos.org; Unknown error";
- JDBC之 连接池
- Mysql5.6主从复制-基于binlog