洛谷P3870 [TJOI2009] 开关 (线段树)
2024-09-08 11:42:41
简单的省选题......
打异或标记即可。
1 #include<bits/stdc++.h>
2 const int N=2e5+10;
3 using namespace std;
4 int n,m,a,b,c;
5 struct node{
6 int l,r,num,lazy;
7 }t[N<<2];
8 int read(){
9 int x=0,f=1;char c=getchar();
10 while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
11 while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
12 return x*f;
13 }
14
15 void pushup(int k){
16 t[k].num=t[k<<1].num+t[k<<1|1].num;
17 }
18
19 void pushdown(int k){
20 if(t[k].lazy){
21 t[k<<1].num=t[k<<1].r-t[k<<1].l+1-t[k<<1].num;
22 t[k<<1|1].num=t[k<<1|1].r-t[k<<1|1].l+1-t[k<<1|1].num;
23 t[k<<1].lazy^=1;
24 t[k<<1|1].lazy^=1;
25 t[k].lazy=0;
26 }
27 }
28
29 void build(int k,int l,int r){
30 t[k].l=l,t[k].r=r;
31 if(l==r) return ;
32 int mid=(l+r)>>1;
33 build(k<<1,l,mid);build(k<<1|1,mid+1,r);
34 }
35
36 void change(int k,int l,int r){
37 if(t[k].l>=l && t[k].r<=r){
38 t[k].lazy^=1;
39 t[k].num=t[k].r-t[k].l+1-t[k].num;
40 return ;
41 }
42 pushdown(k);
43 int mid=(t[k].l+t[k].r)>>1;
44 if(l<=mid) change(k<<1,l,r);
45 if(r>mid) change(k<<1|1,l,r);
46 pushup(k);
47 }
48
49 int query(int k,int l,int r){
50 if(t[k].l>=l && t[k].r<=r) return t[k].num;
51 pushdown(k);
52 int ans=0;
53 int mid=(t[k].l+t[k].r)>>1;
54 if(l<=mid) ans+=query(k<<1,l,r);
55 if(r>mid) ans+=query(k<<1|1,l,r);
56 return ans;
57 }
58
59 int main(){
60 n=read(),m=read();
61 build(1,1,n);
62 while(m--){
63 c=read(),a=read(),b=read();
64 if(c==0) change(1,a,b);
65 else cout<<query(1,a,b)<<endl;
66 }
67 }
最新文章
- Android四大组件之—— BroadcastReceiver的使用
- 08.03 js _oop
- 【zz】Matlab 二值图像形态学函数 bwmorph
- OKhttp初步
- 使用logrotate管理nginx日志文件
- 关于在VS 上发布网站
- 一些常用的html/CSS效果---小技巧
- 2W/月和1W/月的工作,你会怎么选?
- python中的buildin函数详解(第一篇)
- laravel框架——学习笔记
- WMware VMX格式转换成OVF
- java各种概念 Core Java总结
- react-native 组件整理
- JavaScript BOM和DOM
- es6的正则扩展笔记之修饰符
- Liferay7 BPM门户开发之1:Liferay7开发环境准备
- vue播放video插件vue-video-player实现hls, rtmp播放全过程
- 【剑指offer】合并两个排序的链表
- Android------------------ListVIew学习
- matlab 图像Mat类型矩阵中的值(uint8)类型转换,防止溢出
热门文章
- 基于Docker在Win10平台搭建Ruby on Rails 6.0框架开发环境
- Vue 搭建脚手架 &;&; 脚手架的文件结构 &;&; 关于不同版本的Vue
- Odoo14 js 怎么获取图片url链接
- BZOJ3295/Luogu3157 [CQOI2011]动态逆序对 (CDQ or 树套树 )
- Luogu1099 树网的核 (暴力?,floyd?)(还未想正解,暴力就A了)
- 新一代分布式实时流处理引擎Flink入门实战操作篇
- 修改窗体的Title
- 记录一次数据库CPU被打满的排查过程
- 综合布线 子网掩码 IP地址 子网划分
- spark 解决 java.util.Date is not a valid external type for schema of Date